Hamiltonicity in partly claw-free graphs

Abbas, Moncef; Benmeziane, Zineb

doi:10.1051/ro/2009007

Abbas, Moncef ; Benmeziane, Zineb

RAIRO - Operations Research - Recherche Opérationnelle, Tome 43 (2009) no. 1, pp. 103-113.

Résumé

Matthews and Sumner have proved in [10] that if $G$ is a 2-connected claw-free graph of order $n$ such that $δ (G) \geq (n - 2) / 3$ , then $G$ is hamiltonian. We say that a graph is almost claw-free if for every vertex $v$ of G, $〈 N (v) 〉$ is 2-dominated and the set $A$ of centers of claws of $G$ is an independent set. Broersma et al. [5] have proved that if $G$ is a 2-connected almost claw-free graph of order $n$ such that $δ (G) \geq (n - 2) / 3$ , then $G$ is hamiltonian. We generalize these results by considering the graphs satisfying the following property: for every vertex $v \in A$ , there exist exactly two vertices $x$ and $y$ of $V ∖ A$ such that $N (v) \subseteq N [x] \cup N [y]$ . We extend some other known results on claw-free graphs to this new class of graphs.

MR Zbl

DOI : 10.1051/ro/2009007

Classification : 05C45
Mots-clés : graph theory, claw-free graphs, almost claw-free graphs, hamiltonicity, matching

@article{RO_2009__43_1_103_0,
     author = {Abbas, Moncef and Benmeziane, Zineb},
     title = {Hamiltonicity in partly claw-free graphs},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {103--113},
     publisher = {EDP-Sciences},
     volume = {43},
     number = {1},
     year = {2009},
     doi = {10.1051/ro/2009007},
     mrnumber = {2502327},
     zbl = {1158.05324},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ro/2009007/}
}

TY  - JOUR
AU  - Abbas, Moncef
AU  - Benmeziane, Zineb
TI  - Hamiltonicity in partly claw-free graphs
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2009
SP  - 103
EP  - 113
VL  - 43
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ro/2009007/
DO  - 10.1051/ro/2009007
LA  - en
ID  - RO_2009__43_1_103_0
ER  -

%0 Journal Article
%A Abbas, Moncef
%A Benmeziane, Zineb
%T Hamiltonicity in partly claw-free graphs
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2009
%P 103-113
%V 43
%N 1
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ro/2009007/
%R 10.1051/ro/2009007
%G en
%F RO_2009__43_1_103_0

Abbas, Moncef; Benmeziane, Zineb. Hamiltonicity in partly claw-free graphs. RAIRO - Operations Research - Recherche Opérationnelle, Tome 43 (2009) no. 1, pp. 103-113. doi : 10.1051/ro/2009007. http://www.numdam.org/articles/10.1051/ro/2009007/

Bibliographie
Cité par

[1] D. Bauer et al., Long cycles in graphs with large degree sums. Discrete Math. 79 (1989/90) 59-70. | MR | Zbl

[2] D. Bauer and E.F. Schmeichel, Long cycles in tough graphs. Technical Report 8612, Stevens Institute of Technology (1986).

[3] J.A. Bondy and U.S.R. Murty, Graph Theory with Applications. Macmillan, London and Elsevier, New York (1976). | MR

[4] H.J. Broersma, Hamilton cycles in graphs and related topics. Ph.D. Thesis, University of Twente (1988).

[5] H.J. Broersma, Z. Ryjacek and E.F. Schiermeyer, Toughness and Hamiltonicity in almost claw-free graphs. J. Graph theory 21 (1996) 431-439. | MR | Zbl

[6] V. Chvatal, Tough graphs and Hamiltonian circuits. Discrete Math. 5 (1973) 215-228. | MR | Zbl

[7] R.J. Faudree, E. Flandrin and Z. Ryjácek, Claw-free graphs - A survey. Discrete Math. 164 (1997) 87-147. | MR | Zbl

[8] E. Flandrin and H. Li, Hamiltonism and claws. Ars Combinatoria 29C (1990) 77-89. | MR | Zbl

[9] H. Li, M. Lu and Z. Sun, Hamiltonicity in 2-connected graphs with claws. Discrete Math. 183 (1998) 223-236. | MR | Zbl

[10] M. Matthews and D.P. Sumner, Hamiltonian results in K $_{1, 3}$ -free graphs. J. Graph Theory 8 (1984) 139-146. | MR | Zbl

[11] M. Matthews and D.P. Sumner, Longest paths and cycles in K $_{1, 3}$ -free graphs. J. Graph Theory 9 (1985) 269-277. | MR | Zbl

[12] O. Ore, Hamilton connected graphs. J. Math. Pure Appl. 42 (1963) 21-27. | MR | Zbl

[13] Z. Ryjacek, Almost claw-free graphs. J. Graph Theory 18 (1994) 469-477. | MR | Zbl

[14] Z. Ryjácek, On a closure concept in claw-free graphs. J. Combinat. Theory B70 (1997) 217-224. | MR | Zbl

[15] D.P. Sumner, Graphs with 1-factors. Proceeding of the American Mathematical Society (1974) 8-12. | MR | Zbl

[16] D.P. Sumner, 1-factors and antifactors sets. J. London Math. Soc. 213 (1976) 351-359. | MR | Zbl

[17] C. Thomassen, Reflections on graph theory. J Graph Theory 10 (1986) 309-324. | MR | Zbl

[18] C.Q. Zhang, Hamilton cycles in claw-free graphs. J. Graph Theory 12 (1988) 209-216. | MR | Zbl

Cité par Sources :