Hamiltonian graphs involving neighborhood intersections

✍ Scribed by Guantao Chen

• Publisher: Elsevier Science
• Year: 1993
• Tongue: English
• Weight: 270 KB
• Volume: 112
• Category: Article
• ISSN: 0012-365X
• DOI: 10.1016/0012-365x(93)90238-o

✦ Synopsis

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)l <a-1, then G is hamiltonian. This result generalizes Fan's (1984) result on hamiltonian graphs. Introduction. We use Bondy and Murty [l] for terminology and notation not defined here and consider only simple graphs. Let G be a graph of order n. If G has a Hamilton cycle, then G is called hamiltonian. The independence number of G is denoted by c(. If G is connected, the distance, denoted d(u, V) between two distinct vertices u and v is the minimum length of all u-u paths. The neighborhood of a vertex u is denoted by N(u) and d(v)=IN(u)l is the degree of the vertex u. If A, B are subgraphs of G, we define N(A)= U"E"(A) N(u) and N,(A)=N(A)n V(B).