A graph G is diameter-2-critical if its diameter is two and the deletion of any edge increases the diameter. In this paper we characterize the diameter-2-critical graphs with no antihole of length four, that is, the diameter-2-critical graphs whose complements have no induced 4-cycle. Murty and Simon conjectured that the number of edges in a diameter-2-critical graph of order n is at most n 2/4 and that the extremal graphs are complete bipartite graphs with equal size partite sets. As a consequence of our characterization, we prove the Murty-Simon Conjecture for graphs with no antihole of length four.
@article{bwmeta1.element.doi-10_2478_s11533-012-0022-x,
author = {Teresa Haynes and Michael Henning},
title = {A characterization of diameter-2-critical graphs with no antihole of length four},
journal = {Open Mathematics},
volume = {10},
year = {2012},
pages = {1125-1132},
zbl = {1239.05055},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_2478_s11533-012-0022-x}
}
Teresa Haynes; Michael Henning. A characterization of diameter-2-critical graphs with no antihole of length four. Open Mathematics, Tome 10 (2012) pp. 1125-1132. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_2478_s11533-012-0022-x/
[1] Bondy J.A., Murty U.S.R., Extremal graphs of diameter two with prescribed minimum degree, Studia Sci. Math. Hungar., 1972, 7, 239–241 | Zbl 0277.05132
[2] Caccetta L., Häggkvist R., On diameter critical graphs, Discrete Math., 1979, 28(3), 223–229 http://dx.doi.org/10.1016/0012-365X(79)90129-8 | Zbl 0421.05042
[3] Chen Y.-C., Füredi Z., Minimum vertex-diameter-2-critical graphs, J. Graph Theory, 2005, 50(4), 293–315 http://dx.doi.org/10.1002/jgt.20111 | Zbl 1076.05045
[4] Fan G., On diameter 2-critical graphs, Discrete Math., 1987, 67(3), 235–240 http://dx.doi.org/10.1016/0012-365X(87)90174-9
[5] Füredi Z., The maximum number of edges in a minimal graph of diameter 2, J. Graph Theory, 1992, 16(1), 81–98 http://dx.doi.org/10.1002/jgt.3190160110 | Zbl 0773.05063
[6] Hanson D., Wang P., A note on extremal total domination edge critical graphs, Util. Math., 2003, 63, 89–96 | Zbl 1035.05063
[7] Haynes T.W., Hedetniemi S.T., Slater P.J., Fundamentals of Domination in Graphs, Monogr. Textbooks Pure Appl. Math., 208, Marcel Dekker, New York, 1998 | Zbl 0890.05002
[8] Haynes T.W., Henning M.A., van der Merwe L.C., Yeo A., On a conjecture of Murty and Simon on diameter 2-critical graphs, Discrete Math., 2011, 311(17), 1918–1924 http://dx.doi.org/10.1016/j.disc.2011.05.007 | Zbl 1223.05050
[9] Haynes T.W., Henning M.A., Yeo A., A proof of a conjecture on diameter 2-critical graphs whose complements are claw-free, Discrete Optim., 2011, 8(3), 495–501 http://dx.doi.org/10.1016/j.disopt.2011.04.003 | Zbl 1236.05147
[10] Henning M.A., A survey of selected recent results on total domination in graphs, Discrete Math., 2009, 309(1), 32–63 http://dx.doi.org/10.1016/j.disc.2007.12.044 | Zbl 1219.05121
[11] van der Merwe L.C., Total Domination Critical Graphs, PhD thesis, University of South Africa, 1998 | Zbl 0918.05069
[12] van der Merwe L.C., Mynhardt C.M., Haynes T.W., Total domination edge critical graphs, Util. Math., 1998, 54, 229–240 | Zbl 0918.05069
[13] Murty U.S.R., On critical graphs of diameter 2, Math. Mag., 1968, 41, 138–140 http://dx.doi.org/10.2307/2688184 | Zbl 0167.22102
[14] Plesník J., Critical graphs of given diameter, Acta Fac. Rerum Natur. Univ. Comenian. Math., 1975, 30, 71–93 (in Slovak) | Zbl 0318.05115
[15] Xu J.M., Proof of a conjecture of Simon and Murty, J. Math. Res. Exposition, 1984, 4, 85–86 (in Chinese) | Zbl 0569.05031