PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Czasopismo
2012 | 10 | 3 | 1125-1132
Tytuł artykułu

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

Treść / Zawartość
Warianty tytułu
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.
Wydawca
Czasopismo
Rocznik
Tom
10
Numer
3
Strony
1125-1132
Opis fizyczny
Daty
wydano
2012-06-01
online
2012-03-24
Twórcy
  • East Tennessee State University
  • 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)
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_2478_s11533-012-0022-x
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.