✦ LIBER ✦

Neighborhood unions and hamiltonicity of graphs

✍ Scribed by Ruqun Shen; Feng Tian

Publisher: Elsevier Science
Year: 1995
Tongue: English
Weight: 530 KB
Volume: 141
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(93)00181-4

No coin nor oath required. For personal study only.

✦ Synopsis

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.

As a corollary, we get that if G is a 3-connected graph of order n such that for all u, ve V(G), n+3 dist(u,v)=2 ~ IN(u)wN(v)i>>-----, 2 then G is hamiltonian.

📜 SIMILAR VOLUMES

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

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

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.

Insertible vertices, neighborhood inters

Insertible vertices, neighborhood intersections, and hamiltonicity

✍ A. Ainouche; I. Schiermeyer 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 475 KB

## Abstract Let __G__ be a simple undirected graph of order __n__. For an independent set __S__ ⊂ __V__(__G__) of __k__ vertices, we define the __k__ neighborhood intersections __S__~__i__~ = {__v__ ϵ __V__(__G__)\__S__|__N__(__v__) ∩ S| = __i__}, 1 ≦ __i__ ≦ __k__, with __s__~__i__~ = |__S__~__i__