[1] Xu Xinping**,. Neighborhood Union of Essential Sets and Hamiltonicityof Claw-Free Graphs* [J]. Journal of Southeast University (English Edition), 2002, 18 (2): 184-187. [doi:10.3969/j.issn.1003-7985.2002.02.017]

Copy

Neighborhood Union of Essential Sets and Hamiltonicityof Claw-Free Graphs^*()

Share：

Journal of Southeast University (English Edition)[ISSN:1003-7985/CN:32-1325/N]

Volumn:

18

Issue:

2002 2

Page:

184-187

Research Field:

Mathematics, Physics, Mechanics

Publishing date:

2002-06-30

Info

Title:

Neighborhood Union of Essential Sets and Hamiltonicityof Claw-Free Graphs^*

Author(s):

Xu Xinping^**

School of Mathematics and Computer Science, Nanjing Normal University, Nanjing 210097, China
Department of Mathematics and Computer Science, Jiangsu Institute of Education, Nanjing 210013, China

Keywords:

hamiltonicity;  claw-free graph;  neighborhood union;  vertex insertion;  essential set

PACS:

O157.5

DOI:

10.3969/j.issn.1003-7985.2002.02.017

Abstract:

Let G be a graph, an independent set Y in G is called an essential independent set(or essential set for simplicity), if there is {y₁, y₂}⊆Y such that dist (y₁, y₂)=2. In this paper, we will use the technique of the vertex insertion on l-connected(l=k or k+1, k≥2)claw-free graphs to provide a unified proof for G to be hamiltonian or 1-hamiltonian, the sufficient conditions are expressed by the inequality concerning ∑^k_i=0|N(Y_i)| and n(Y) for each essential set Y={y₀, y₁, …, y_k} of G, where Y_i={y_i, y_i-1, …, y_i-(b-1)}⊆Y for i∈{0, 1, …, k}(the subscriptions of y_j’s will be taken modulo k+1), b(0<b<k+1)is an integer, and n(Y)=|{v∈V(G): dist (v, Y)≤2}|.

References:

[1] Bondy J A, Murty U S R. Graph theory with applications[M]. New York: Macmillan, London and Elsevier, 1976.
[2] Schiermeyer I. Neighborhood intersections and hamiltonicity [A]. In: Alavi Y, ed. Proceedings in Applied Mathematics 54, Graph Theory, Combinatories, Algorithms and Applications, SIAM[C]. 1991, 79-95.
[3] Wu Z, Xu X, Zhou X. The neighborhood intersections of essential sets and hamiltonicity of graphs[J]. Sys Sci and Math Scis, 1998, 11(3):230-237.
[4] Liu Y, Tian F and Wu Z. Sequence concerning hamiltonicity of graphs[J]. J of Nanjing Normal University (Natural Science), 1995, 18(1): 19-28.
[5] Wu Z, Xu X, Zhang X, Zhou X. Hamiltonian cycles in K_{1, r-}1free graphs[J]. Advances in Mathematics, to appear.

Memo

Memo:

* The project partially supported by the National Natural Science Foundation of China(19971043).
** Born in 1964, female, associate professor.

Common functions