PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Czasopismo
2014 | 12 | 12 | 1882-1889
Tytuł artykułu

A maximum degree theorem for diameter-2-critical graphs

Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
A graph is diameter-2-critical if its diameter is two and the deletion of any edge increases the diameter. Let G be a diameter-2-critical graph of order n. Murty and Simon conjectured that the number of edges in G is at most ⌊n 2/4⌋ and that the extremal graphs are the complete bipartite graphs K ⌊n/2⌋,⌊n/2⌉. Fan [Discrete Math. 67 (1987), 235–240] proved the conjecture for n ≤ 24 and for n = 26, while Füredi [J. Graph Theory 16 (1992), 81–98] proved the conjecture for n > n 0 where n 0 is a tower of 2’s of height about 1014. The conjecture has yet to be proven for other values of n. Let Δ denote the maximum degree of G. We prove the following maximum degree theorems for diameter-2-critical graphs. If Δ ≥ 0.7 n, then the Murty-Simon Conjecture is true. If n ≥ 2000 and Δ ≥ 0.6789 n, then the Murty-Simon Conjecture is true.
Kategorie tematyczne
Wydawca
Czasopismo
Rocznik
Tom
12
Numer
12
Strony
1882-1889
Opis fizyczny
Daty
wydano
2014-12-01
online
2014-07-20
Twórcy
autor
Bibliografia
  • [1] J. A. Bondy and U. S. R. Murty, Extremal graphs of diameter two with prescribed minimum degree. Studia Sci. Math. Hungar. 7 (1972), 239–241.
  • [2] L. Caccetta and R. Häggkvist, On diameter critical graphs. Discrete Math. 28 (1979), no. 3, 223–229. http://dx.doi.org/10.1016/0012-365X(79)90129-8
  • [3] Ya-Chen Chen and Z. Füredi, Minimum vertex-diameter-2-critical graphs. J. Graph Theory 50 (2005), no. 4, 293–315. http://dx.doi.org/10.1002/jgt.20111
  • [4] P. Erdös and A. Hajnal, Ramsey-type theorems. Discrete Appl. Math. 25 (1989), 37–52. http://dx.doi.org/10.1016/0166-218X(89)90045-0
  • [5] G. Fan, On diameter 2-critical graphs. Discrete Math. 67 (1987), 235–240. http://dx.doi.org/10.1016/0012-365X(87)90174-9
  • [6] Z. Füredi, The maximum number of edges in a minimal graph of diameter 2. J. Graph Theory 16 (1992), 81–98. http://dx.doi.org/10.1002/jgt.3190160110
  • [7] D. Hanson and P. Wang, A note on extremal total domination edge critical graphs. Util. Math. 63 (2003), 89–96.
  • [8] T. W. Haynes, S. T. Hedetniemi and P. J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, Inc., New York (1998).
  • [9] T. W. Haynes and M. A. Henning, A characterization of diameter-2-critical graphs with no antihole of length four. Cent. Eur. J. Math. 10(3) (2012), 1125–1132. http://dx.doi.org/10.2478/s11533-012-0022-x
  • [10] T. W. Haynes, M. A. Henning, L. C. van der Merwe and A. Yeo, On a conjecture of Murty and Simon on diameter two critical graphs. Discrete Math. 311 (2011), 1918–1924. http://dx.doi.org/10.1016/j.disc.2011.05.007
  • [11] T. W. Haynes, M. A. Henning and A. Yeo, A proof of a conjecture on diameter two critical graphs whose complements are claw-free. Discrete Optim. 8 (2011), 495–501. http://dx.doi.org/10.1016/j.disopt.2011.04.003
  • [12] T. W. Haynes, M. A. Henning, and A. Yeo, On a conjecture of Murty and Simon on diameter two critical graphs II. Discrete Math. 312 (2012), 315–323. http://dx.doi.org/10.1016/j.disc.2011.09.022
  • [13] T. W. Haynes, C. M. Mynhardt and L. C. van der Merwe, Total domination edge critical graphs. Util. Math. 54 (1998), 229–240.
  • [14] M. A. Henning, Recent results on total domination in graphs: A survey. Discrete Math. 309 (2009), 32–63. http://dx.doi.org/10.1016/j.disc.2007.12.044
  • [15] W. Mantel, Wiskundige Opgaven 10 (1906), 60–61.
  • [16] U. S. R. Murty, On critical graphs of diameter 2. Math. Mag. 41 (1968), 138–140. http://dx.doi.org/10.2307/2688184
  • [17] J. Plesník, Critical graphs of given diameter. Acta F.R.N Univ Comen Math 30 (1975), 71–93.
  • [18] B. Reed and N. Sbihi, Recognizing bull-free perfect graphs. Graphs Combin. 11 (1995), 171–178. http://dx.doi.org/10.1007/BF01929485
  • [19] P. Turán, Eine Extremalaufgabe aus der Graphentheorie. Mat. Fiz. Lapok 48 (1941), 436–452.
  • [20] L. C. van der Merwe, Total Domination Critical Graphs, Ph.D. Dissertation, University of South Africa (1998).
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_2478_s11533-014-0449-3
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ć.