✦ LIBER ✦

Neighborhood unions and Hamiltonian properties

✍ Scribed by Min Song Zeng; Zhang Ke Min

Publisher: Elsevier Science
Year: 1994
Tongue: English
Weight: 380 KB
Volume: 133
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(94)90041-8

No coin nor oath required. For personal study only.

✦ Synopsis

Let G be a simple graph of order n with connectivity k 3 2, independence number cc We prove that if for each independent set S of cardinality k+ 1, one of the following condition holds:

(1) there exist u # v in S such that d(u) +d(v) > n or ) N(u)nN(v) I> cr; (2) for any distinct pair u and u in S, )N(u)uN(v)J>,n-max{d(x))x~S}, then G is Hamiltonian. Many known results on Hamiltonian graphs are corollaries of this result. * The project supported by NSFC * Corresponding author.

📜 SIMILAR VOLUMES

The effects of distance and neighborhood

The effects of distance and neighborhood union conditions on hamiltonian properties in graphs

✍ Terri England Lindquester 📂 Article 📅 1989 🏛 John Wiley and Sons 🌐 English ⚖ 773 KB

Hamiltonian graphs involving neighborhoo

Hamiltonian graphs involving neighborhood unions

✍ Guantao Chen; Warren E. Shreve; Bing Wei 📂 Article 📅 2006 🏛 John Wiley and Sons 🌐 English ⚖ 214 KB

## 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

Hamiltonian properties of graphs with la

Hamiltonian properties of graphs with large neighborhood unions

✍ Douglas Bauer; Genghua Fan; Henk Jan Veldman 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 768 KB

Bauer, D., G. Fan and H.J. Veldman, Hamiltonian properties of graphs with large neighborhood unions, Discrete Mathematics 96 (1991) 33-49. Let G be a graph of order n, a k =min{~ki=ld(vi): {V 1 ..... Vn} is an independent set of vertices in G}, NC=min{IN(u) 13N(v)l:uv~E(G)} and NC2=min{IN(u) t3 wh

Neighborhood unions and hamilton cycles

✍ Bill Jackson 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 392 KB

## Abstract Let __G__ be a graph on __n__ vertices and __N__~2~(__G__) denote the minimum size of __N__(__u__) ∪ __N__(__v__) taken over all pairs of independent vertices __u, v__ of __G__. We show that if __G__ is 3‐connected and __N__~2~(__G__) ⩾ ½(__n__ + 1), then __G__ has a Hamilton cycle. We

Neighborhood unions and regular factors

✍ Thomas Niessen 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 737 KB

We examine bounds on the size of the neighborhood union for two (independent) vertices of a graph that imply the existence of regular factors.

Neighborhood unions and hamiltonicity of

Neighborhood unions and hamiltonicity of graphs

✍ Ruqun Shen; Feng Tian 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 530 KB

Let G be a graph of order n. In this paper, we prove that if G is a 2-connected graph of order n such that for all u, ve V(G), 2 where dist(u,v) is the distance between u and v in G, then either G is hamiltonian, or G is a spanning subgraph of a graph in one of three families of exceptional graphs.