✦ LIBER ✦

Hamiltonian graphs with neighborhood intersections

✍ Scribed by G. Chen; R. H. Schelp

Publisher: John Wiley and Sons
Year: 1994
Tongue: English
Weight: 577 KB
Volume: 18
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190180508

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

In this paper, k + 1 real numbers c~1~, c~2~, ⃛, c~k+1~ are found such that the following condition is sufficient for a k‐connected graph of order n to be hamiltonian: for each independent vertex set of k + 1 vertices in G.

magnified image where S~i~ = {v ≅ V:|N(v) ∩ S| = i} for 0 ≦ i ≦ k + 1. Such a set of k + 1 numbers is called an Hk‐sequence. A sufficient condition for the existence of Hk‐sequences is obtained that generalizes many known results involving sum of degrees, neighborhood unions, and/or neighborhood intersections.

📜 SIMILAR VOLUMES

Hamiltonian graphs involving neighborhoo

Hamiltonian graphs involving neighborhood intersections

✍ Guantao Chen 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 270 KB

Chen, G., Hamiltonian graphs involving neighborhood intersections, Discrete Mathematics 112 (1993) 253-257. Let G be a graph of order n and a the independence number of G. We show that if G is a 2connected graph and max {d(u), d(v)} > n/2 for each pair of non-adjacent vertices u, u with 1 QIN(u)nN(o

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

20-relative neighborhood graphs are hami

20-relative neighborhood graphs are hamiltonian

✍ M. S. Chang; C. Y. Tang; R. C. T. Lee 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 548 KB

## Abstract For any two points __p__ and __q__ in the Euclidean plane, define LUN~__pq__~ = {__v__|__v__ ∈ __R__^2^, __d__~__pv__~ < __d__~__pq__~ and __d__~__qv__~ < __d__~__pq__~}, where __d__~__uv__~ is the Euclidean distance between two points __u__ and __v__. Given a set of points __V__ in the

Neighborhood unions and hamiltonian prop

Neighborhood unions and hamiltonian properties in graphs

✍ R.J Faudree; Ronald J Gould; Michael S Jacobson; R.H Schelp 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 617 KB

Dense Graphs with Cycle Neighborhoods

✍ A. Seress; T. Szabo 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 420 KB

For all $\varepsilon>0$, we construct graphs with $n$ vertices and $>n^{2-n}$ edges, for arbitrarily large $n$, such that the neighborhood of each vertex is a cycle. This result is asymptotically best possible. "1995 Academic Press. Inc.