✦ LIBER ✦

Subdivisions of graphs with large minimum degree

✍ Scribed by Carsten Thomassen

Publisher: John Wiley and Sons
Year: 1984
Tongue: English
Weight: 257 KB
Volume: 8
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190080103

No coin nor oath required. For personal study only.

📜 SIMILAR VOLUMES

Cycle lengths in graphs with large minim

Cycle lengths in graphs with large minimum degree

✍ V. Nikiforov; R. H. Schelp 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 114 KB 👁 1 views

## Abstract Our main result is the following theorem. Let __k__ ≥ 2 be an integer, __G__ be a graph of sufficiently large order __n__, and __δ__(__G__) ≥ __n__/__k__. Then: __G__ contains a cycle of length __t__ for every even integer __t__ ∈ [4, __δ__(__G__) + 1]. If __G__ is nonbipartite then

Total domination in graphs with minimum

Total domination in graphs with minimum degree three

✍ Favaron, Odile; Henning, Michael A.; Mynhart, Christina M.; Puech, Jo�l 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 132 KB 👁 3 views

A set S of vertices of a graph G is a total dominating set, if every vertex of V (G) is adjacent to some vertex in S. The total domination number of G, denoted by γ t (G), is the minimum cardinality of a total dominating set of G. We prove that, if G is a graph of order n with minimum degree at leas

Overfull conjecture for graphs with high

Overfull conjecture for graphs with high minimum degree

✍ Michael Plantholt 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 79 KB

## Abstract Chetwynd and Hilton showed that any regular graph __G__ of even order __n__ which has relatively high degree $\Delta (G)\,\ge\,((\sqrt{7}- 1)/2)\, n$ has a 1‐factorization. This is equivalent to saying that under these conditions __G__ has chromatic index equal to its maximum degree $\D

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

The minimum degree of Ramsey-minimal gra

The minimum degree of Ramsey-minimal graphs

✍ Jacob Fox; Kathy Lin 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 144 KB 👁 1 views

## Abstract We write __H__ → __G__ if every 2‐coloring of the edges of graph __H__ contains a monochromatic copy of graph __G__. A graph __H__ is __G__‐__minimal__ if __H__ → __G__, but for every proper subgraph __H__′ of __H__, __H__′ ↛ __G__. We define __s__(__G__) to be the minimum __s__ such th

Large P4-free graphs with bounded degree

✍ Myung S. Chung; Douglas B. West 📂 Article 📅 1993 🏛 John Wiley and Sons 🌐 English ⚖ 424 KB

## 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.