[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

徐新萍

江苏教育学院数学系, 南京 210013

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 G² of G is a graph satisfying V(G²)=V(G) and E(G²)=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 ∑^k_i=0|N(Y_i)| and n(Y) in G for each independent set Y={y₀, y₁, …, y_k} of the square graph of G, where b(0<b<k+1)is an integer, Y_i={y_i, y_i-1, …, y_i-(b-1)}⊆Y for i∈{0, 1, …, k}, where subscriptions of y_j’s will be taken modulo k+1, and n(Y)=|{v∈ V(G): dist(v, Y)≤2}|.

设G是一个图, G的平方图G²满足V(G²)=V(G), E(G²)=E(G)∪{uv: dist_G(u, v)=2}. 本文利用插点方法, 给出了关于 k或(k+1)-连通(k≥2)无爪图G是哈密尔顿的、 1-哈密尔顿的或哈密尔顿连通的统一证明.其充分条件是G中关于∑^k_i=0|N(Y_i)|与n(Y)的不等式, 这里Y={y₀, y₁, …, y_k} 是图G²的任一独立集, 对于i∈{0, 1, …, k}, Y_i={y_i, y_i-1, …, y_i-(b-1)}⊆Y(y_j的下标将取模k+1); b 是一个整数, 且0<b<k+1; 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 K_{1, r}1-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.

Common functions