Structural results on maximal k-degenerate graphs

Allan Bickle

Discussiones Mathematicae Graph Theory (2012)

  • Volume: 32, Issue: 4, page 659-676
  • ISSN: 2083-5892

Abstract

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

How to cite

top

Allan Bickle. "Structural results on maximal k-degenerate graphs." Discussiones Mathematicae Graph Theory 32.4 (2012): 659-676. <http://eudml.org/doc/270959>.

@article{AllanBickle2012,
abstract = {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.},
author = {Allan Bickle},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {k-degenerate; k-core; k-tree; degree sequence; Ramsey number; -degenerate; -core; -tree},
language = {eng},
number = {4},
pages = {659-676},
title = {Structural results on maximal k-degenerate graphs},
url = {http://eudml.org/doc/270959},
volume = {32},
year = {2012},
}

TY - JOUR
AU - Allan Bickle
TI - Structural results on maximal k-degenerate graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2012
VL - 32
IS - 4
SP - 659
EP - 676
AB - 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.
LA - eng
KW - k-degenerate; k-core; k-tree; degree sequence; Ramsey number; -degenerate; -core; -tree
UR - http://eudml.org/doc/270959
ER -

References

top
  1. [1] A. Bickle, The k-Cores of a graph. Ph.D. Dissertation, Western Michigan University, 2010. 
  2. [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. Zbl0813.05061
  3. [3] G. Chartrand and L. Lesniak, Graphs and Digraphs, (4th ed.) (CRC Press, 2005). Zbl1057.05001
  4. [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. Zbl0798.05042
  5. [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. [6] G.A. Dirac, Homomorphism theorems for graphs, Math. Ann. 153 (1964) 69-80, doi: 10.1007/BF01361708. Zbl0115.41005
  7. [7] Z. Filáková, P. Mihók and G. Semanišin, A note on maximal k-degenerate graphs, Math. Slovaca 47 (1997) 489-498. Zbl0937.05040
  8. [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. [9] S. Hakimi, J. Mitchem and E. Schmeichel, Short proofs of theorems of Nash-Williams and Tutte, Ars Combin. 50 (1998) 257-266. Zbl0963.05110
  10. [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. [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. Zbl0202.23502
  12. [12] W. Mader, 3n-5 edges do force a subdivision of K₅, Combinatorica 18 (1998) 569-595, doi: 10.1007/s004930050041. Zbl0924.05039
  13. [13] J. Mitchem, Maximal k-degenerate graphs, Util. Math. 11 (1977) 101-106. Zbl0348.05109
  14. [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. Zbl0119.38805
  15. [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. [16] S.B. Seidman, Network structure and minimum degree, Social Networks 5 (1983) 269-287, doi: 10.1016/0378-8733(83)90028-X. 
  17. [17] J.M.S. Simões-Pereira, A survey of k-degenerate graphs, Graph Theory Newsletter 5 (1976) 1-7. Zbl0331.05135
  18. [18] West D., Introduction to Graph Theory, (2nd ed.) (Prentice Hall, 2001). 

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.