|Table of Contents|

[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 {y1, y2}⊆Y such that dist (y1, y2)=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 ∑ki=0|N(Yi)| and n(Y) for each essential set Y={y0, y1, …, yk} of G, where Yi={yi, yi-1, …, yi-(b-1)}⊆Y for i∈{0, 1, …, k}(the subscriptions of yj’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 K1, 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.
Last Update: 2002-06-20