A characterization of diameter-2-critical graphs with no antihole of length four

• Autorzy: Teresa Haynes , Michael Henning
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

Diameter critical; Diameter-2-critical; Antihole; Total domination critical

Kategorie tematyczne

• 05C12: Distance in graphs
• 05C35: Extremal problems
• 05C69: Dominating sets, independent sets, cliques

• Wydawca: De Gruyter Open
• Czasopismo: Open Mathematics
• Rocznik: 2012
• Tom: 10
• Numer: 3
• Strony: 1125-1132

Daty

wydano

2012-06-01

online

2012-03-24

Twórcy

autor

Teresa Haynes

• East Tennessee State University

autor

Michael Henning

• University of Johannesburg

Bibliografia

• [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
• [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
• [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
• [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
• [6] Hanson D., Wang P., A note on extremal total domination edge critical graphs, Util. Math., 2003, 63, 89–96
• [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
• [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
• [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
• [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
• [11] van der Merwe L.C., Total Domination Critical Graphs, PhD thesis, University of South Africa, 1998
• [12] van der Merwe L.C., Mynhardt C.M., Haynes T.W., Total domination edge critical graphs, Util. Math., 1998, 54, 229–240
• [13] Murty U.S.R., On critical graphs of diameter 2, Math. Mag., 1968, 41, 138–140 http://dx.doi.org/10.2307/2688184
• [14] Plesník J., Critical graphs of given diameter, Acta Fac. Rerum Natur. Univ. Comenian. Math., 1975, 30, 71–93 (in Slovak)
• [15] Xu J.M., Proof of a conjecture of Simon and Murty, J. Math. Res. Exposition, 1984, 4, 85–86 (in Chinese)

Identyfikatory

DOI

10.2478/s11533-012-0022-x