✦ LIBER ✦

Large P4-free graphs with bounded degree

✍ Scribed by Myung S. Chung; Douglas B. West

Publisher: John Wiley and Sons
Year: 1993
Tongue: English
Weight: 424 KB
Volume: 17
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190170111

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Let ex * (D; H) denote the maximum number of edges in a connected graph with maximum degree D and no induced subgraph isomorphic to H. We prove that this is finite only when H is a disjoint union of paths,m in which case we provide crude upper and lower bounds. When H is the four‐vertex path P~4~, we prove that the complete bipartite graph K~D,D~ is the unique extremal graph. Furthermore, if G is a connected P~4~‐free graph with maximum degree D and clique number ω, then G has at most D^2^ − D(ω − 2)/2 edges. © 1993 John Wiley & Sons, Inc.

📜 SIMILAR VOLUMES

Total interval number for graphs with bo

Total interval number for graphs with bounded degree

✍ Kostochka, Alexander V.; West, Douglas B. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 90 KB 👁 2 views

The total interval number of an n-vertex graph with maximum degree ∆ is at most (∆+1/∆)n/2, with equality if and only if every component of the graph is K ∆,∆ . If the graph is also required to be connected, then the maximum is ∆n/2 + 1 when ∆ is even, but when ∆ is odd it exceeds [∆ + 1/(2.5∆ + 7.7

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

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

Subdivisions of graphs with large minimu

Subdivisions of graphs with large minimum degree

✍ Carsten Thomassen 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 257 KB 👁 1 views

On Induced Ramsey Numbers for Graphs wit

On Induced Ramsey Numbers for Graphs with Bounded Maximum Degree

✍ Tomasz Łuczak; Vojtěch Rödl 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 435 KB

For graphs G and H we write G wÄ ind H if every 2-edge colouring of G yields an induced monochromatic copy of H. The induced Ramsey number for H is defined as r ind (H)=min[ |V(G)|: G wÄ ind H]. We show that for every d 1 there exists an absolute constant c d such that r ind (H n, d ) n cd for every

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