✦ LIBER ✦

On induced subgraphs with odd degrees

✍ Scribed by Yair Caro

Publisher: Elsevier Science
Year: 1994
Tongue: English
Weight: 336 KB
Volume: 132
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(92)00563-7

No coin nor oath required. For personal study only.

✦ Synopsis

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.

📜 SIMILAR VOLUMES

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

On induced subgraphs of trees, with rest

On induced subgraphs of trees, with restricted degrees

✍ Y. Caro; I. Krasikov; Y. Roditty 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 313 KB

Graphs with unavoidable subgraphs with l

Graphs with unavoidable subgraphs with large degrees

✍ L. Caccetta; P. Erdös; K. Vijayan 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 360 KB

Let %(n, rn) denote the class of simple graphs on n vertices and rn edges and let G E %(n, rn). There are many results in graph theory giving conditions under which G contains certain types of subgraphs, such as cycles of given lengths, complete graphs, etc. For example, Turan's theorem gives a suff

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.

Complete subgraphs with large degree sum

Complete subgraphs with large degree sums

✍ Ralph J. Faudree 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 368 KB

## Abstract Let __t__(__n, k__) denote the Turán number—the maximum number of edges in a graph on __n__ vertices that does not contain a complete graph __K__~k+1~. It is shown that if __G__ is a graph on __n__ vertices with __n__ ≥ __k__^2^(__k__ – 1)/4 and __m__ < __t__(__n, k__) edges, then __G__

On 2-Connected Spanning Subgraphs with L

On 2-Connected Spanning Subgraphs with Low Maximum Degree

✍ Daniel P Sanders; Yue Zhao 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 408 KB

Given a graph G, let a k-trestle of G be a 2-connected spanning subgraph of G of maximum degree at most k. Also, let /(G) be the Euler characteristic of G. This paper shows that every 3-connected graph G has a (10&2/(G))-trestle. If /(G) &5, this is improved to 8&2/(G), and for /(G) &10, this is fur