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

Teresa Haynes; Michael Henning

Open Mathematics (2012)

- Volume: 10, Issue: 3, page 1125-1132
- ISSN: 2391-5455

## Access Full Article

top## Abstract

top## How to cite

topTeresa Haynes, and Michael Henning. "A characterization of diameter-2-critical graphs with no antihole of length four." Open Mathematics 10.3 (2012): 1125-1132. <http://eudml.org/doc/269790>.

@article{TeresaHaynes2012,

abstract = {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.},

author = {Teresa Haynes, Michael Henning},

journal = {Open Mathematics},

keywords = {Diameter critical; Diameter-2-critical; Antihole; Total domination critical; diameter critical; diameter-2-critical; antihole; total domination critical},

language = {eng},

number = {3},

pages = {1125-1132},

title = {A characterization of diameter-2-critical graphs with no antihole of length four},

url = {http://eudml.org/doc/269790},

volume = {10},

year = {2012},

}

TY - JOUR

AU - Teresa Haynes

AU - Michael Henning

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

JO - Open Mathematics

PY - 2012

VL - 10

IS - 3

SP - 1125

EP - 1132

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

LA - eng

KW - Diameter critical; Diameter-2-critical; Antihole; Total domination critical; diameter critical; diameter-2-critical; antihole; total domination critical

UR - http://eudml.org/doc/269790

ER -

## References

top- [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 Zbl0277.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 Zbl0421.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 Zbl1076.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 Zbl0773.05063
- [6] Hanson D., Wang P., A note on extremal total domination edge critical graphs, Util. Math., 2003, 63, 89–96 Zbl1035.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 Zbl0890.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 Zbl1223.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 Zbl1236.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 Zbl1219.05121
- [11] van der Merwe L.C., Total Domination Critical Graphs, PhD thesis, University of South Africa, 1998 Zbl0918.05069
- [12] van der Merwe L.C., Mynhardt C.M., Haynes T.W., Total domination edge critical graphs, Util. Math., 1998, 54, 229–240 Zbl0918.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 Zbl0167.22102
- [14] Plesník J., Critical graphs of given diameter, Acta Fac. Rerum Natur. Univ. Comenian. Math., 1975, 30, 71–93 (in Slovak) Zbl0318.05115
- [15] Xu J.M., Proof of a conjecture of Simon and Murty, J. Math. Res. Exposition, 1984, 4, 85–86 (in Chinese) Zbl0569.05031

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.