Diameter-2-critical graphs with at most 13 nodes

Diameter-2-critical graphs (abbr. D2C) are diameter 2 graphs whose diameter increases by removing any edge. The procedure used to obtain the list of D2C graphs of the order at most 13 is described. This is achieved by incorporating the diameter 2 test and the criticality test into geng, the program from the package nauty that generates the list of all non-isomorphic connected graphs. Experiments with the two heuristics in diameter 2 test, which is intensively used during the search, show that it is slightly more efficient to start the test with the largest degree node using BFS algorithm. As an application of the obtained list, the three conjectures concerning the maximum number of edges in D2C graphs were checked for graphs of the order at most 13 and one counterexample was found. Index Terms: diameter-2-critical graphs, graph diameter, primitive graph.

diameter-2-critical graphs, graph diameter, primitive graph.

1. Bollobas, B. ”Graph Theory”, Springer-Verlag (1979).

2. Caccetta, L.; Haggkvist, R. ”On diameter critical graphs”, Discrete Math. 28(3) (1979), pp. 223– 229.

3. Plesnik, J. ”Critical graphs of given diameter”, Acta F.R.N. Univ. comenianae Math. 30 (1975), pp. 71–93.

4. Balbuena, C.; Hansberg, A.; Haynes, T.W.; Henning, M.A. ”Total domination edge critical graphs with total domination number three and many dominating pairs”, Graphs Combin. 31 (5) (2015), pp. 1163–1176.

5. Dailly, A.; Foucaud, F.; Hansberg, A. ”Strengthening the Murty-Simon conjecture on diameter- 2-critical graphs”, Discrete Mathematics, Elsevier 342 (11) (2019), pp. 3142–3159.

6. Fan, G. ”On diameter 2-critical graphs”, Discrete Math. 67 (3) (1987), pp. 235–240

7. McKay, B. D. ”Practical graph isomorphism”, Congr. Numer. (30) (1980), pp. 45—87.

8. McKay, B. D. and Piperno, A. ”Practical Graph Isomorphism, II”, J. Symbolic Computation (60) (2013), pp. 94–112.

9. Cormen, T. H.; Leiserson C. E.; Rivest R. L.; Stein C. ”Introduction to Algorithms Third Edition”, The MIT Press (2009), pp. 594–602.

10. Radosavljevi´c, J.; Zivkovi ˇ ´c, M. ”The List of Diameter-2-Critical Graphs with at Most 10 Nodes”, IPSI Transactions (2020).

...