View PDF Cite this article

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.

Open Access: CC-BY-NC-ND

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).

...