✦ LIBER ✦

Parity theorems for paths and cycles in graphs

✍ Scribed by J. A. Bondy; F. Y. Halberstam

Publisher: John Wiley and Sons
Year: 1986
Tongue: English
Weight: 294 KB
Volume: 10
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190100113

No coin nor oath required. For personal study only.

✦ Synopsis

We extend an elegant proof technique of A . G . Thomason, and deduce several parity theorems for paths and cycles in graphs. For example, a graph in which each vertex is of even degree has an even number of paths if and only if it is of even order, and a graph in which each vertex is of odd degree has an even number of paths if and only if its order is a multiple of four. Our results have implications for generalized friendship graphs and their conjectured nonexistence.

📜 SIMILAR VOLUMES

Longest paths and cycles in bipartite or

Longest paths and cycles in bipartite oriented graphs

✍ Zhang Ke Min 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 430 KB 👁 1 views

In this paper we obtain two sufficient conditions, Ore type (Theorem 1) and Dirac type (Theorem 2). on the degrees of a bipartite oriented graph for ensuring the existence of long paths and cycles. These conditions are shown to be the best possible in a sense. An oriented graph is a digraph without

Cycles and paths in graphs with large mi

Cycles and paths in graphs with large minimal degree

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

## Abstract Let __G__ be a simple graph of order __n__ and minimal degree > cn (0 < c < 1/2). We prove that (1) There exist __n__~0~ = __n__~0~(__c__) and __k__ = __k__(__c__) such that if __n__ > __n__~0~ and __G__ contains a cycle __C__~__t__~ for some __t__ > 2__k__, then __G__ contains a cycle

Longest paths and cycles in K1,3-free gr

Longest paths and cycles in K1,3-free graphs

✍ Manton M. Matthews; David P. Sumner 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 383 KB 👁 2 views

In this article w e show that the standard results concerning longest paths and cycles in graphs can be improved for K,,,-free graphs. We obtain as a consequence of these results conditions for the existence of a hamiltonian path and cycle in K,,,-free graphs.

Infinite paths in planar graphs IV, divi

Infinite paths in planar graphs IV, dividing cycles

✍ Xingxing Yu 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 285 KB 👁 1 views

Nash-Williams conjectured that a 4-connected infinite planar graph contains a spanning 2-way infinite path if, and only if, the deletion of any finite set of vertices results in at most two infinite components. In this article, we prove this conjecture for graphs with no dividing cycles and for grap

Cycles and paths in edge-colored graphs

Cycles and paths in edge-colored graphs with given degrees

✍ A. Abouelaoualim,; K. Ch. Das; W. Fernandez de la Vega; M. Karpinski; Y. Manouss 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 203 KB 👁 1 views

## Abstract Sufficient degree conditions for the existence of properly edge‐colored cycles and paths in edge‐colored graphs, multigraphs and random graphs are investigated. In particular, we prove that an edge‐colored multigraph of order __n__ on at least three colors and with minimum colored degre

A theorem on paths in planar graphs

✍ Norishige Chiba; Takao Nishizeki 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 108 KB 👁 1 views

C. Thomassen extended Tutte's theorem on cycles in planar graphs in the paper "A Theorem on Paths in Planar Graphs". This note corrects a flaw in his proof.