# Hamiltonicity in Partly claw-free graphs

Moncef Abbas; Zineb Benmeziane

RAIRO - Operations Research (2009)

- Volume: 43, Issue: 1, page 103-113
- ISSN: 0399-0559

## Access Full Article

top## Abstract

top## How to cite

topAbbas, Moncef, and Benmeziane, Zineb. "Hamiltonicity in Partly claw-free graphs." RAIRO - Operations Research 43.1 (2009): 103-113. <http://eudml.org/doc/250663>.

@article{Abbas2009,

abstract = {
Matthews and Sumner have proved in [10]
that if G is a 2-connected
claw-free graph of order n such that δ(G) ≥ (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 n such that δ(G) ≥ (n-2)/3, then G is Hamiltonian. We generalize these results
by considering the graphs satisfying the following property: for every
vertex v ∈ A, there exist exactly two vertices x and y of V such that N(v) ⊆ N[x] ∪ N[y]. We extend some other known
results on claw-free graphs to this new class of graphs.
},

author = {Abbas, Moncef, Benmeziane, Zineb},

journal = {RAIRO - Operations Research},

keywords = {Graph theory; claw-free graphs; almost claw-free
graphs; Hamiltonicity; matching.; graph theory; almost claw-free graphs; hamiltonicity; matching},

language = {eng},

month = {1},

number = {1},

pages = {103-113},

publisher = {EDP Sciences},

title = {Hamiltonicity in Partly claw-free graphs},

url = {http://eudml.org/doc/250663},

volume = {43},

year = {2009},

}

TY - JOUR

AU - Abbas, Moncef

AU - Benmeziane, Zineb

TI - Hamiltonicity in Partly claw-free graphs

JO - RAIRO - Operations Research

DA - 2009/1//

PB - EDP Sciences

VL - 43

IS - 1

SP - 103

EP - 113

AB -
Matthews and Sumner have proved in [10]
that if G is a 2-connected
claw-free graph of order n such that δ(G) ≥ (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 n such that δ(G) ≥ (n-2)/3, then G is Hamiltonian. We generalize these results
by considering the graphs satisfying the following property: for every
vertex v ∈ A, there exist exactly two vertices x and y of V such that N(v) ⊆ N[x] ∪ N[y]. We extend some other known
results on claw-free graphs to this new class of graphs.

LA - eng

KW - Graph theory; claw-free graphs; almost claw-free
graphs; Hamiltonicity; matching.; graph theory; almost claw-free graphs; hamiltonicity; matching

UR - http://eudml.org/doc/250663

ER -

## References

top- D. Bauer et al., Long cycles in graphs with large degree sums. Discrete Math.79 (1989/90) 59–70. Zbl0713.05041
- D. Bauer and E.F. Schmeichel, Long cycles in tough graphs. Technical Report 8612, Stevens Institute of Technology (1986).
- J.A. Bondy and U.S.R. Murty, Graph Theory with Applications. Macmillan, London and Elsevier, New York (1976). Zbl1226.05083
- H.J. Broersma, Hamilton cycles in graphs and related topics. Ph.D. Thesis, University of Twente (1988).
- H.J. Broersma, Z. Ryjacek and E.F. Schiermeyer, Toughness and Hamiltonicity in almost claw-free graphs. J. Graph theory21 (1996) 431–439. Zbl0847.05069
- V. Chvatal, Tough graphs and Hamiltonian circuits. Discrete Math.5 (1973) 215–228. Zbl0256.05122
- R.J. Faudree, E. Flandrin and Z. Ryjácek, Claw-free graphs – A survey. Discrete Math.164 (1997) 87–147. Zbl0879.05043
- E. Flandrin and H. Li, Hamiltonism and claws. Ars Combinatoria29C (1990) 77–89. Zbl0718.05037
- H. Li, M. Lu and Z. Sun, Hamiltonicity in 2-connected graphs with claws. Discrete Math.183 (1998) 223–236. Zbl0893.05009
- M. Matthews and D.P. Sumner, Hamiltonian results in K1,3 -free graphs. J. Graph Theory8 (1984) 139–146. Zbl0536.05047
- M. Matthews and D.P. Sumner, Longest paths and cycles in K1,3-free graphs. J. Graph Theory9 (1985) 269–277. Zbl0591.05041
- 0. Ore, Hamilton connected graphs. J. Math. Pure Appl.42 (1963) 21–27. Zbl0106.37103
- Z. Ryjacek, Almost claw-free graphs. J. Graph Theory18 (1994) 469–477. Zbl0808.05067
- Z. Ryjácek, On a closure concept in claw-free graphs. J. Combinat. TheoryB70 (1997) 217–224. Zbl0872.05032
- D.P. Sumner, Graphs with 1-factors. Proceeding of the American Mathematical Society (1974) 8–12. Zbl0293.05157
- D.P. Sumner, 1-factors and antifactors sets. J. London Math. Soc.213 (1976) 351–359. Zbl0338.05118
- C. Thomassen, Reflections on graph theory. J Graph Theory10 (1986) 309–324. Zbl0614.05050
- C.Q. Zhang, Hamilton cycles in claw-free graphs. J. Graph Theory12 (1988) 209–216. Zbl0642.05037