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

Abstract

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

How to cite

top

Teresa 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. [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. [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. [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. [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. [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. [6] Hanson D., Wang P., A note on extremal total domination edge critical graphs, Util. Math., 2003, 63, 89–96 Zbl1035.05063
  7. [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. [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. [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. [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. [11] van der Merwe L.C., Total Domination Critical Graphs, PhD thesis, University of South Africa, 1998 Zbl0918.05069
  12. [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. [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. [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. [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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.