𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On Induced Subgraphs with All Degrees Odd

✍ Scribed by A.D. Scott

Publisher
Springer Japan
Year
2001
Tongue
English
Weight
156 KB
Volume
17
Category
Article
ISSN
0911-0119

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

On induced subgraphs with odd degrees
On induced subgraphs with odd degrees
✍ Yair Caro πŸ“‚ Article πŸ“… 1994 πŸ› Elsevier Science 🌐 English βš– 336 KB

Solving a problem of Alon, we prove that every graph G on n vertices with 6(G) 2 1 contains an induced subgraph H such that all the degrees in H are odd and 1 V(H)\ >(l -o(l))Jn/6.

Every tree contains a large induced subg
Every tree contains a large induced subgraph with all degrees odd
✍ A.J. Radclife; A.D. Scott πŸ“‚ Article πŸ“… 1995 πŸ› Elsevier Science 🌐 English βš– 222 KB

Caro et al. proved that every tree of order n contains an induced subgraph of order at least rn/2] with all degrees odd, and conjectured a better bound. In this note we prove that every tree of order n contains an induced subgraph of order at least 2L(n + 1)/3 .] with all degrees odd; this bound is

All trees contain a large induced subgra
All trees contain a large induced subgraph having all degrees 1 (mod k)
✍ David M. Berman; A.J. Radcliffe; A.D. Scott; Hong Wang; Larry Wargo πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 260 KB

We prove that, for integers n/>2 and k~>2, every tree with n vertices contains an induced subgraph of order at least 2/(n + 2k -3)/(2k -1)j with all degrees congruent to 1 modulo k. This extends a result of Radcliffe and Scott, and answers a question of Caro et al.

Sizes of graphs with induced subgraphs o
Sizes of graphs with induced subgraphs of large maximum degree
✍ Paul ErdΕ‘s; Talmage James Reid; Richard Schelp; William Staton πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 249 KB

Graphs with n + k vertices in which every set of n +j vertices induce a subgraph of maximum degree at least n are considered. For j = 1 and for k fairly small compared to n, we determine the minimum number of edges in such graphs.