✦ LIBER ✦

Dominating cycles in bipartite biclaw-free graphs

✍ Scribed by Daniel Barraez; Evelyne Flandrin; Hao Li; Oscar Ordaz

Publisher: Elsevier Science
Year: 1995
Tongue: English
Weight: 354 KB
Volume: 146
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(94)00153-6

No coin nor oath required. For personal study only.

✦ Synopsis

Flandrin et ai. (to appear) define a simple bipartite graph to be biclaw-free if it contains no induced subgraph isomorphic to H, where H could be obtained from two copies of K1.3 by adding an edge joining the two vertices of degree 3. They have shown that if G is a bipartite, balanced, biclaw-free connected graph of order at most 66-10, then G is hamiltonian. In this paper we show that if G is a bipartite, balanced, biclaw-free connected graph of order at most 86-69, where 6 >1 24, then every longest cycle in G is dominating, i.e., every edge has at least one end-vertex on the cycle.

📜 SIMILAR VOLUMES

Dominating cycles in halin graphs

✍ Mirosława Skowrońska; Maciej M. Sysło 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 676 KB

A cycle in a graph is dominating if every vertex lies at distance at most one from the cycle and a cycle is D-cycle if every edge is incident with a vertex of the cycle. In this paper, first we provide recursive formulae for finding a shortest dominating cycle in a Hahn graph; minor modifications ca

Dominating cycles in regular 3-connected

Dominating cycles in regular 3-connected graphs

✍ Bill Jackson; Hao Li; Yongjin Zhu 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 744 KB

Jackson, B., H. Li and Y. Zhu, Dominating cycles in regular 3-connected graphs, Discrete Mathematics 102 (1992) 163-176. Let G be a 3-connected, k-regular graph on at most 4k vertices. We show that, for k > 63, every longest cycle of G is a dominating cycle. We conjecture that G is in fact hamilton

On the length of longest dominating cycl

On the length of longest dominating cycles in graphs

✍ Hoa Vu Dinh 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 719 KB

Vu Dinh, H., On the length of longest dominating cycles in graphs, Discrete Mathematics 121 (1993) 21 l-222. ## A cycle C in an undirected and simple graph if G contains a dominating cycle. There exists l-tough graph in which no longest cycle is dominating. Moreover, the difference of the length

A note on dominating cycles in 2-connect

A note on dominating cycles in 2-connected graphs

✍ D. Bauer; E. Schmeichel; H.J. Veldman 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 277 KB

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

Spanning Cycles Through Specified Edges

Spanning Cycles Through Specified Edges in Bipartite Graphs

✍ Reza Zamani; Douglas B. West 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 284 KB

P ósa proved that if G is an n-vertex graph in which any two nonadjacent vertices have degree-sum at least n+k, then G has a spanning cycle containing any specified family of disjoint paths with a total of k edges. We consider the analogous problem for a bipartite graph G with n vertices and parts o