✦ LIBER ✦

Long path connectivity of regular graphs

✍ Scribed by Cun-Quan Zhang; Yong-Jin Zhu

Publisher: Elsevier Science
Year: 1991
Tongue: English
Weight: 842 KB
Volume: 96
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(91)90231-p

No coin nor oath required. For personal study only.

✦ Synopsis

Zhang, C.-Q. and Y.-J. Zhu, Long path connectivity of regular graphs, Discrete Mathematics 96 (1991) 151-160. Any pair of vertices in a 4-connected path or a path of length at least 3k-6. non-bipartite k-regular graph are joined bY a Hamilton * This research was partially supported by AFOSR under grant 89-0068.

📜 SIMILAR VOLUMES

Path-connectivity in graphs

✍ Michael Hager 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 420 KB

Regular path decompositions of odd regul

Regular path decompositions of odd regular graphs

✍ Odile Favaron; François Genest; Mekkia Kouider 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 197 KB

## Abstract Kotzig asked in 1979 what are necessary and sufficient conditions for a __d__‐regular simple graph to admit a decomposition into paths of length __d__ for odd __d__>3. For cubic graphs, the existence of a 1‐factor is both necessary and sufficient. Even more, each 1‐factor is extendable

Long paths through four vertices in a 2-

Long paths through four vertices in a 2-connected graph

✍ Barovich, Mark V. 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 252 KB 👁 2 views

Let G be a 2-connected graph, let u and v be distinct vertices in V (G), and let X be a set of at most four vertices lying on a common (u

Subdivisions of large complete bipartite

Subdivisions of large complete bipartite graphs and long induced paths in k-connected graphs

✍ Thomas Böhme; Bojan Mohar; Riste Škrekovski; Michael Stiebitz 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 67 KB 👁 1 views

## Abstract It is proved that for every positive integers __k__, __r__ and __s__ there exists an integer __n__ = __n__(__k__,__r__,__s__) such that every __k__‐connected graph of order at least __n__ contains either an induced path of length __s__ or a subdivision of the complete bipartite graph __

On Hamiltonian-connected regular graphs

✍ Ioan Tomescu 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 360 KB

In this paper it is shown that any rn-regular graph of order 2rn (rn 3 3), not isomorphic to K, , , , or of order 2rn + 1 (rn even, rn 3 4), is Hamiltonian connected, which extends a previous result of Nash-Williams. As a corollary, it is derived that any such graph contains at least rn Hamiltonian

Hamiltonicity of regular 2-connected gra

Hamiltonicity of regular 2-connected graphs

✍ Broersma, H. J.; van den Heuvel, J.; Jackson, B.; Veldman, H. J. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 832 KB

Let G be a k-regular 2-connected graph of order n. Jackson proved that G is hamiltonian if n 5 3k. Zhu and Li showed that the upper bound 3k on n can be relaxed to q k if G is 3-connected and k 2 63. We improve both results by showing that G is hamiltonian if n 5 gk -7 and G does not belong to a res