𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Subgraphs of minimal degree k

✍ Scribed by P. Erdős; R.J. Faudree; C.C. Rousseau; R.H. Schelp

Book ID
103060956
Publisher
Elsevier Science
Year
1990
Tongue
English
Weight
392 KB
Volume
85
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

For k 2 2, any graph G with n vertices and (k -1) (n -k + 2) + (" 1') edges has a subgraph of minimum degree at least k; however, this subgraph need not be proper. It is shown that if G has at least (k -1) (n -k + 2) + (e ;') + 1 edges, then there is a subgraph H of minimal degree

k that has at most n -fi/@ vertices. Also, conditions that insure the existence of smaller subgraphs of minimum degree k are given.

πŸ“œ SIMILAR VOLUMES

Degree constrained subgraphs
Degree constrained subgraphs
✍ L. Addario-Berry; K. Dalal; B.A. Reed πŸ“‚ Article πŸ“… 2008 πŸ› Elsevier Science 🌐 English βš– 163 KB
Reconstructing degree sequences from k-v
Reconstructing degree sequences from k-vertex-deleted subgraphs
✍ Richard Taylor πŸ“‚ Article πŸ“… 1990 πŸ› Elsevier Science 🌐 English βš– 362 KB

Let k 23 be an integer. We show that the degree sequences of all sufficiently large graphs are determined by their k-vertex-deleted subgraphs. In particular, this is shown for all graphs on at least f(k) vertices, where f(k) IS a certain function which is asymptotic to ke.

Vertex decompositions of sparse graphs i
Vertex decompositions of sparse graphs into an edgeless subgraph and a subgraph of maximum degree at most k
✍ O. V. Borodin; A. O. Ivanova; M. Montassier; P. Ochem; A. Raspaud πŸ“‚ Article πŸ“… 2009 πŸ› John Wiley and Sons 🌐 English βš– 127 KB

## Abstract A graph __G__ is (__k__,0)‐colorable if its vertices can be partitioned into subsets __V__~1~ and __V__~2~ such that in __G__[__V__~1~] every vertex has degree at most __k__, while __G__[__V__~2~] is edgeless. For every integer __k__β©Ύ0, we prove that every graph with the maximum average