𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Reconstructing degree sequences from k-vertex-deleted subgraphs

✍ Scribed by Richard Taylor

Publisher
Elsevier Science
Year
1990
Tongue
English
Weight
362 KB
Volume
79
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

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.

πŸ“œ SIMILAR VOLUMES

Recognizing connectedness from vertex-de
Recognizing connectedness from vertex-deleted subgraphs
✍ Andrew Bowler; Paul Brown; Trevor Fenner; Wendy Myrvold πŸ“‚ Article πŸ“… 2010 πŸ› John Wiley and Sons 🌐 English βš– 248 KB

Let G be a graph of order n. The vertex-deleted subgraph G -v, obtained from G by deleting the vertex v and all edges incident to v, is called a card of G. Let H be another graph of order n, disjoint from G. Then the number of common cards of G and H is the maximum number of disjoint pairs (v, w), w

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