𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the length of longest dominating cycles in graphs

✍ Scribed by Hoa Vu Dinh

Publisher
Elsevier Science
Year
1993
Tongue
English
Weight
719 KB
Volume
121
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

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 of a longest cycle and of a longest dominating cycle in a l-tough cycle-dominable graph may be made arbitrarily large. Some lower bounds for the length of dominating cycles in cycle-dominable graph are given. These results generalize and strengthen some well-known theorems of Jung and Fraisse (1989) and Bauer and Veldman et al. (1988).

πŸ“œ SIMILAR VOLUMES

Relative length of longest paths and cyc
Relative length of longest paths and cycles in 3-connected graphs
✍ Rao Li; Akira Saito; R.H. Schelp πŸ“‚ Article πŸ“… 2001 πŸ› John Wiley and Sons 🌐 English βš– 184 KB πŸ‘ 2 views

## Abstract For a graph __G__, let __p(G)__ denote the order of a longest path in __G__ and __c(G)__ the order of a longest cycle in __G__, respectively. We show that if __G__ is a 3‐connected graph of order __n__ such that $\textstyle{\sum^{4}\_{i=1}\,{\rm deg}\_{G}\,x\_{i} \ge {3\over2}\,n + 1}$

On relative length of longest paths and
On relative length of longest paths and cycles
✍ Kenta Ozeki; Masao Tsugaki; Tomoki Yamashita πŸ“‚ Article πŸ“… 2009 πŸ› John Wiley and Sons 🌐 English βš– 144 KB πŸ‘ 1 views

## Abstract For a graph __G__, __p__(__G__) and __c__(__G__) denote the order of a longest path and a longest cycle of __G__, respectively. In this paper, we prove that if __G__ is a 3 ‐connected graph of order __n__ such that the minimum degree sum of four independent vertices is at least __n__+ 6

Intersections of longest cycles in grid
Intersections of longest cycles in grid graphs
✍ Menke, B.; Zamfirescu, T.; Zamfirescu, C. πŸ“‚ Article πŸ“… 1997 πŸ› John Wiley and Sons 🌐 English βš– 292 KB πŸ‘ 3 views

It is well-known that the largest cycles of a graph may have empty intersection. This is the case, for example, for any hypohamiltonian graph. In the literature, several important classes of graphs have been shown to contain examples with the above property. This paper investigates a (nontrivial) cl

Chords of Longest Cycles in Cubic Graphs
Chords of Longest Cycles in Cubic Graphs
✍ Carsten Thomassen πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 213 KB

We describe a general sufficient condition for a Hamiltonian graph to contain another Hamiltonian cycle. We apply it to prove that every longest cycle in a 3-connected cubic graph has a chord. We also verify special cases of an old conjecture of Sheehan on Hamiltonian cycles in 4-regular graphs and