𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Closures, cycles, and paths

✍ Scribed by Jochen Harant; Arnfried Kemnitz; Akira Saito; Ingo Schiermeyer

Publisher
John Wiley and Sons
Year
2011
Tongue
English
Weight
104 KB
Volume
69
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

In 1960 Ore proved the following theorem: Let G be a graph of order n. If d(u) + d(v)≥n for every pair of nonadjacent vertices u and v, then G is hamiltonian. Since then for several other graph properties similar sufficient degree conditions have been obtained, so‐called “Ore‐type degree conditions”. In [R. J. Faudree, R. H. Schelp, A. Saito, and I. Schiermeyer, Discrete Math 307 (2007), 873–877], Faudree et al. strengthened Ore's theorem as follows: They determined the maximum number of pairs of nonadjacent vertices that can have degree sum less than n (i.e. violate Ore's condition) but still imply that the graph is hamiltonian. In this article we prove that for some other graph properties the corresponding Ore‐type degree conditions can be strengthened as well. These graph properties include traceable graphs, hamiltonian‐connected graphs, k‐leaf‐connected graphs, pancyclic graphs, and graphs having a 2‐factor with two components. Graph closures are computed to show these results. © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 314–323, 2012

📜 SIMILAR VOLUMES

Paths extendable to cycles
Paths extendable to cycles
✍ T. D. Parsons 📂 Article 📅 1978 🏛 John Wiley and Sons 🌐 English ⚖ 128 KB

## Abstract Let __k__ be a positive integer, and __S__ a nonempty set of positive integers. Suppose that __G__ is a connected graph containing a path of length __k__, and that each path __P__ of length __k__ in __G__ is contained in some cycle __C__(__P__) of length s ∈ __S__. We prove that every p

Hamiltonian paths and cycles in hypertou
Hamiltonian paths and cycles in hypertournaments
✍ Gutin, Gregory; Yeo, Anders 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 138 KB

Given two integers n and k, n ≥ k > 1, a k-hypertournament T on n vertices is a pair (V, A), where V is a set of vertices, |V | = n and A is a set of k-tuples of vertices, called arcs, so that for any k-subset S of V, A contains exactly one of the k! k-tuples whose entries belong to S. A 2-hypertour

The Square of Paths and Cycles
The Square of Paths and Cycles
✍ G.H. Fan; H.A. Kierstead 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 388 KB

The square of a path (cycle) is the graph obtained by joining every pair of vertices of distance two in the path (cycle). Let \(G\) be a graph on \(n\) vertices with minimum degree \(\delta(G)\). Posa conjectured that if \(\delta(G) \geqslant \frac{2}{3} n\), then \(G\) contains the square of a hami

Vertex coverings by monochromatic paths
Vertex coverings by monochromatic paths and cycles
✍ A. Gyárfás 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 254 KB

We survey some results on covering the vertices of 2-colored complete graphs by t w o paths or by t w o cycles Qf different color. W e show the role of these results i n determining path Ramsey numbers and in algorithms for finding long monochromatic paths or cycles in 2-colored complete graphs. ##