𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Graphs with unavoidable subgraphs with large degrees

✍ Scribed by L. Caccetta; P. Erdös; K. Vijayan

Publisher
John Wiley and Sons
Year
1988
Tongue
English
Weight
360 KB
Volume
12
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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 sufficient condition for G to contain a K k b , in terms of the number of edges in G. In this paper we prove that, for rn = an2, a > ( k -1 ) / 2 k , G contains a Kk+,, each vertex of which has degree at least W n and determine the best possible f(a). For rn = Ln2/4J + 1 we establish that G contains cycles whose vertices have certain minimum degrees. Further, for rn = an2, a > 0 we establish that G contains a subgraph /-/ with 6 ( H ) 2 f(a, n) and determine the best possible value of f(a, n).

📜 SIMILAR VOLUMES

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 graphs with subgraphs having large in
On graphs with subgraphs having large independence numbers
✍ Noga Alon; Benny Sudakov 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 131 KB

## Abstract Let __G__ be a graph on __n__ vertices in which every induced subgraph on ${s}={\log}^{3}\, {n}$ vertices has an independent set of size at least ${t}={\log}\, {n}$. What is the largest ${q}={q}{(n)}$ so that every such __G__ must contain an independent set of size at least __q__? This

Almost-Spanning Subgraphs with Bounded D
Almost-Spanning Subgraphs with Bounded Degree in Dense Graphs
✍ Yoshiyasu Ishigami 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 330 KB

We present two extensions of a theorem by Alon and Yuster (1992, Graphs Comb., 8, 95-102) that give degree conditions guaranteeing an almost-spanning subgraph isomorphic to a given graph. The first extension gives a sharp degree condition when the desired subgraph consists of small connected compone

Connected subgraphs with small degree su
Connected subgraphs with small degree sums in 3-connected planar graphs
✍ Enomoto, Hikoe; Ota, Katsuhiro 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 213 KB 👁 2 views

It is well-known that every planar graph has a vertex of degree at most five. Kotzig proved that every 3-connected planar graph has an edge xy such that deg(x) + deg(y) ≤ 13. In this article, considering a similar problem for the case of three or more vertices that induce a connected subgraph, we sh

Some large graphs with given degree and
Some large graphs with given degree and diameter
✍ I. Alegre; M. A. Fiol; J. L. A. Yebra 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 196 KB 👁 1 views

This paper considers the (A, 0 ) problem: to maximize the order of graphs with given maximum degree A and diameter 0, of importance for its implications in the design of interconnection networks. Two cubic graphs of diameters 5 and 8 and orders 70 and 286, respectively, and a graph of degree 5, diam