✦ LIBER ✦

On induced subgraphs of trees, with restricted degrees

✍ Scribed by Y. Caro; I. Krasikov; Y. Roditty

Publisher: Elsevier Science
Year: 1994
Tongue: English
Weight: 313 KB
Volume: 125
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(94)90149-x

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

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

Subgraphs with Restricted Degrees of the

Subgraphs with Restricted Degrees of their Vertices in Large Polyhedral Maps on Compact Two-manifolds

✍ S. Jendrol’; H.-J. Voss 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 276 KB

Let k ≥ 2, be an integer and M be a closed two-manifold with Euler characteristic χ(M) ≤ 0. We prove that each polyhedral map G on M, which has at least (8k 2 + 6k -6)|χ (M)| vertices, contains a connected subgraph H of order k such that every vertex of this subgraph has, in G, the degree at most 4k

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.

Packing k-edge trees in graphs of restri

Packing k-edge trees in graphs of restricted vertex degrees

✍ A.K. Kelmans 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 368 KB 👁 1 views

## Abstract Let ${\cal G}^{s}\_{r}$ denote the set of graphs with each vertex of degree at least __r__ and at most __s__, __v__(__G__) the number of vertices, and τ~__k__~ (__G__) the maximum number of disjoint __k__‐edge trees in __G__. In this paper we show that if __G__ ∈ ${\cal G}^{s}\_{2}$ a

A result on Hamiltonian line graphs invo

A result on Hamiltonian line graphs involving restrictions on induced subgraphs

✍ H. J. Veldman 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 384 KB

It is shown that the existence of a Hamilton cycle in the line graph of a graph G can be ensured by imposing certain restrictions on certain induced subgraphs of G. Thereby a number of known results on hamiltonian line graphs are improved, including the earliest results in terms of vertex degrees. O