PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2012 | 32 | 4 | 659-676
Tytuł artykułu

Structural results on maximal k-degenerate graphs

Autorzy
Treść / Zawartość
Warianty tytułu
Języki publikacji
EN
Abstrakty
EN
A graph is k-degenerate if its vertices can be successively deleted so that when deleted, each has degree at most k. These graphs were introduced by Lick and White in 1970 and have been studied in several subsequent papers. We present sharp bounds on the diameter of maximal k-degenerate graphs and characterize the extremal graphs for the upper bound. We present a simple characterization of the degree sequences of these graphs and consider related results. Considering edge coloring, we conjecture that a maximal k-degenerate graph is class two if and only if it is overfull, and prove this in some special cases. We present some results on decompositions and arboricity of maximal k-degenerate graphs and provide two characterizations of the subclass of k-trees as maximal k-degenerate graphs. Finally, we define and prove a formula for the Ramsey core numbers.
Słowa kluczowe
Wydawca
Rocznik
Tom
32
Numer
4
Strony
659-676
Opis fizyczny
Daty
wydano
2012
otrzymano
2011-06-09
poprawiono
2011-12-13
zaakceptowano
2011-12-13
Twórcy
autor
  • Department of Mathematics, Western Michigan University, 1903 W. Michigan, Kalamazoo, MI 49008
Bibliografia
  • [1] A. Bickle, The k-Cores of a graph. Ph.D. Dissertation, Western Michigan University, 2010.
  • [2] M. Borowiecki, J. Ivančo, P. Mihók and G. Semanišin, Sequences realizable by maximal k-degenerate graphs, J. Graph Theory 19 (1995) 117-124, doi: 10.1002/jgt.3190190112.
  • [3] G. Chartrand and L. Lesniak, Graphs and Digraphs, (4th ed.) (CRC Press, 2005).
  • [4] B. Chen, M. Matsumoto, J. Wang, Z. Zhang and J. Zhang, A short proof of Nash-Williams' Theorem for the arboricity of a graph, Graphs Combin. 10 (1994) 27-28, doi: 10.1007/BF01202467.
  • [5] A.G. Chetwynd and A.J.W. Hilton, Star multigraphs with 3 vertices of maximum degree, Math. Proc. Cambridge Math. Soc. 100 (1986) 303-317, doi: 10.1017/S030500410006610X.
  • [6] G.A. Dirac, Homomorphism theorems for graphs, Math. Ann. 153 (1964) 69-80, doi: 10.1007/BF01361708.
  • [7] Z. Filáková, P. Mihók and G. Semanišin, A note on maximal k-degenerate graphs, Math. Slovaca 47 (1997) 489-498.
  • [8] Z. Goufei, A note on graphs of class 1, Discrete Math. 263 (2003) 339-345, doi: 10.1016/S0012-365X(02)00793-8.
  • [9] S. Hakimi, J. Mitchem and E. Schmeichel, Short proofs of theorems of Nash-Williams and Tutte, Ars Combin. 50 (1998) 257-266.
  • [10] R. Klein and J. Schonheim, Decomposition of Kₙ into degenerate graphs, Combinatorics and Graph Theory Hefei 6-27, World Scientific. Singapore (New Jersey, London, Hong Kong, April 1992) 141-155.
  • [11] D.R. Lick and A.T. White, k-degenerate graphs, Canad. J. Math. 22 (1970) 1082-1096, doi: 10.4153/CJM-1970-125-1.
  • [12] W. Mader, 3n-5 edges do force a subdivision of K₅, Combinatorica 18 (1998) 569-595, doi: 10.1007/s004930050041.
  • [13] J. Mitchem, Maximal k-degenerate graphs, Util. Math. 11 (1977) 101-106.
  • [14] C.St.J.A. Nash-Williams, Decomposition of finite graphs into forests, J. London Math. Soc. 39 (1964) 12, doi: 10.1112/jlms/s1-39.1.12.
  • [15] H.P. Patil, A note on the edge-arboricity of maximal k-degenerate graphs, Bull. Malays. Math Sci. Soc.(2) 7 (1984) 57-59.
  • [16] S.B. Seidman, Network structure and minimum degree, Social Networks 5 (1983) 269-287, doi: 10.1016/0378-8733(83)90028-X.
  • [17] J.M.S. Simões-Pereira, A survey of k-degenerate graphs, Graph Theory Newsletter 5 (1976) 1-7.
  • [18] West D., Introduction to Graph Theory, (2nd ed.) (Prentice Hall, 2001).
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.bwnjournal-article-doi-10_7151_dmgt_1637
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ć.