|Table of Contents|

[1] Xu Xinping,. Hamiltonicity, neighborhood unionand square graphs of claw-free graphs [J]. Journal of Southeast University (English Edition), 2004, 20 (2): 251-255. [doi:10.3969/j.issn.1003-7985.2004.02.026]
Copy

Hamiltonicity, neighborhood unionand square graphs of claw-free graphs()
Share:

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

Volumn:
20
Issue:
2004 2
Page:
251-255
Research Field:
Mathematics, Physics, Mechanics
Publishing date:
2004-06-30

Info

Title:
Hamiltonicity, neighborhood unionand square graphs of claw-free graphs
Author(s):
Xu Xinping
Department of Mathematics, Jiangsu Institute of Education, Nanjing 210013, China
Keywords:
Hamiltonicity claw-free graph neighborhood union vertex insertion square graph
PACS:
O157.5
DOI:
10.3969/j.issn.1003-7985.2004.02.026
Abstract:
Let G be a graph, the square graph G2 of G is a graph satisfying V(G2)=V(G) and E(G2)=E(G)∪{uv: distG(u, v)=2}. In this paper, we use the technique of 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, 1-Hamiltonian or Hamiltonian-connected. The sufficient conditions are expressed by the inequality concerning ∑ki=0|N(Yi)| and n(Y) in G for each independent set Y={y0, y1, …, yk} of the square graph of G, where b(0<b<k+1)is an integer, Yi={yi, yi-1, …, yi-(b-1)}⊆Y for i∈{0, 1, …, k}, where subscriptions of yj’s will be taken modulo k+1, and n(Y)=|{v∈ V(G): dist(v, Y)≤2}|.

References:

[1] Bondy J A, Murty U S R. Graph theory with applications [M].London: Macmillan, 1976.
[2] Zhang C Q. Hamilton cycle in claw-free graphs [J]. J Graph Theory, 1988, 12(2): 209-216.
[3] Ainouche A, Kouider M. Cycles in square graphs, Preprint, 1995.
[4] Wu Z S, Jin Y H, Zha Q Z. Hamiltonian-path and Hamiltonian-connected in k-connected claw-free graphs [J]. Chinese Science Bulletin, 1991, 36(2): 154.(in Chinese)
[5] Ainouche A, Kouider M. Hamiltonism and partially square graphs [J]. Graphs and Combinatorics, 1999, 15(3): 257-265.
[6] Liu Y P, Tian F, Wu Z S. Sequence concerning Hamiltonicity of graphs [J].Journal of Nanjing Normal University(Natural Science Edition), 1995, 18(1): 19-28.(in Chinese)
[7] Wu Z S, Xu X P, Zhang X R, et al. Hamiltonian cycles in K1, r1-free graphs [J]. Advances in Mathematics, 2002, 31(3): 261-270.
[8] Wu Z S, Zhang X R, Zhou X H. Hamiltonicity, neighborhood intersections and partially squared graphs [J]. Discrete Mathematics, 2002, 242(1-3): 245-254.

Memo

Memo:
Biography: Xu Xinping(1964—), female, doctor, associate professor.
Last Update: 2004-06-20