✦ LIBER ✦

Complete subgraphs with large degree sums

✍ Scribed by Ralph J. Faudree

Publisher: John Wiley and Sons
Year: 1992
Tongue: English
Weight: 368 KB
Volume: 16
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190160406

No coin nor oath required. For personal study only.

✦ Synopsis

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 contains a complete subgraph K~k~ such that the sum of the degrees of the vertices is at least 2__km/n__. This result is sharp in an asymptotic sense in that the sum of the degrees of the vertices of K~k~ is not in general larger, and if the number of edges in G is at most t(n, k) – ϵ (for an appropriate ϵ), then the conclusion is not in general true. © 1992 John Wiley & Sons, Inc.

📜 SIMILAR VOLUMES

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

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

Long cycles in graphs with large degree

Long cycles in graphs with large degree sums and neighborhood unions

✍ Van den Heuvel, J. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 801 KB

We present and prove several results concerning the length of longest cycles in 2connected or I-tough graphs with large degree sums. These results improve many known results on long cycles in these graphs. We also consider the sharpness of the results and discuss some possible strengthenings.

Subgraphs with a large cochromatic numbe

Subgraphs with a large cochromatic number

✍ Alon, Noga; Krivelevich, Michael; Sundakov, Benny 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 66 KB

The cochromatic number of a graph G = (V, E) is the smallest number of parts in a partition of V in which each part is either an independent set or induces a complete subgraph. We show that if the chromatic number of G is n, then G contains a subgraph with cochromatic number at least Ω( n ln n ). Th

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

A sharp lower bound for the circumferenc

A sharp lower bound for the circumference of 1-tough graphs with large degree sums

✍ Vu Dinh Hoa 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 207 KB 👁 1 views

## Abstract We show that every 1‐tough graph __G__ on __n__ ≥ 3 vertices with σ~3~≧ __n__ has a cycle of length at least min{__n, n__ + (σ~3~/3 ) − α + 1}, where σ~3~ denotes the minimum value of the degree sum of any 3 pairwise nonadjacent vertices and α the cardinality of a miximum independent se