✦ LIBER ✦

Hamiltonian graphs involving neighborhood unions

✍ Scribed by Guantao Chen; Warren E. Shreve; Bing Wei

Publisher: John Wiley and Sons
Year: 2006
Tongue: English
Weight: 214 KB
Volume: 53
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20168

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Dirac proved that a graph G is hamiltonian if the minimum degree $\delta(G) \geq n/2$, where n is the order of G. Let G be a graph and $A \subseteq V(G)$. The neighborhood of A is $N(A)={ b: ab \in E(G)$ for some $a \in A}$. For any positive integer k, we show that every (2__k__ − 1)‐connected graph of order n ≥ 16__k__^3^ is hamiltonian if |N(A)| ≥ n/2 for every independent vertex set A of k vertices. The result contains a few known results as special cases. The case of k = 1 is the classic result of Dirac when n is large and the case of k = 2 is a result of Broersma, Van den Heuvel, and Veldman when n is large. For general k, this result improves a result of Chen and Liu. The lower bound 2__k__ − 1 on connectivity is best possible in general while the lower bound 16__k__^3^ for n is conjectured to be unnecessary. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 83–100, 2006

📜 SIMILAR VOLUMES

Extremal problems involving neighborhood

Extremal problems involving neighborhood unions

✍ Ralph J. Faudree; Ronald J. Gould; Michael S. Jacobson; Richard H. Schelp 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 393 KB

We examine several extremal problems for graphs satisfying the property JN(x) u N(y)l ? s f o r every pair of nonadjacent vertices x , y E V ( G ) . In particular, values for s are found that ensure that the graph contains an s-matching, a 1-factor, a path of a specific length, or a cycle of a spec

Hamiltonian graphs involving distances

✍ Guantao Chen; R. H. Schelp 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 368 KB

## Abstract Let __G__ be a graph of order __n__. We show that if __G__ is a 2‐connected graph and max{__d(u), d(v)__} + |__N(u)__ U __N(v)__| ≥ __n__ for each pair of vertices __u, v__ at distance two, then either __G__ is hamiltonian or G 3K~n/3~ U T~1~ U T~2~, where n  O (mod 3), and __T__~1~ a

Long dominating cycles and paths in grap

Long dominating cycles and paths in graphs with large neighborhood unions

✍ H. J. Broersma; H. J. Veldman 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 413 KB 👁 1 views

## Abstract Let __G__ be a graph of order __n__ and define __NC(G)__ = min{|__N__(__u__) ∪ __N__(__v__)| |__uv__ ∉ __E__(__G__)}. A cycle __C__ of __G__ is called a __dominating cycle__ or __D__‐__cycle__ if __V__(__G__) ‐ __V__(__C__) is an independent set. A __D__‐__path__ is defined analogously.

Long cycles in graphs with large degree

Long cycles in graphs with large degree sums and neighborhood unions

✍ Van den Heuvel, J. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 801 KB

We present and prove several results concerning the length of longest cycles in 2connected or I-tough graphs with large degree sums. These results improve many known results on long cycles in these graphs. We also consider the sharpness of the results and discuss some possible strengthenings.

Neighborhood unions and the cycle cover

Neighborhood unions and the cycle cover number of a graph

✍ Guantao Chen; Ronald J. Gould; Michael S. Jacobson; Richard H. Schelp 📂 Article 📅 1994 🏛 John Wiley and Sons 🌐 English ⚖ 413 KB

## Abstract For several years, the study of neighborhood unions of graphs has given rise to important structural consequences of graphs. In particular, neighborhood conditions that give rise to hamiltonian cycles have been considered in depth. In this paper we generalize these approaches to give a

A result on Hamiltonian line graphs invo

A result on Hamiltonian line graphs involving restrictions on induced subgraphs

✍ H. J. Veldman 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 384 KB

It is shown that the existence of a Hamilton cycle in the line graph of a graph G can be ensured by imposing certain restrictions on certain induced subgraphs of G. Thereby a number of known results on hamiltonian line graphs are improved, including the earliest results in terms of vertex degrees. O