Hostname: page-component-cd9895bd7-jn8rn Total loading time: 0 Render date: 2024-12-26T12:54:27.853Z Has data issue: false hasContentIssue false
  • English
  • Français

Hamiltonicity in Partly claw-free graphs

Published online by Cambridge University Press:  28 January 2009

Moncef Abbas  and
Zineb Benmeziane
Moncef Abbas
Affiliation:
Université des Sciences et de la Technologie Houari Boumedienne Faculté de Mathématiques, BP 32, El Alia Alger 16111, Algérie; [email protected]
Zineb Benmeziane
Affiliation:
Université des Sciences et de la Technologie Houari Boumedienne Faculté de Mathématiques, BP 32, El Alia Alger 16111, Algérie; [email protected]
Get access

Abstract


Matthews and Sumner have proved in [10] that if G is a 2-connectedclaw-free graph of order n such that δ(G) ≥ (n-2)/3, then G isHamiltonian. We say that a graph is almost claw-free if for every vertexv of G, 〈N(v)〉 is 2-dominated and the set A of centers of claws of G isan independent set. Broersma et al. [5] have proved that if G isa 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 resultsby considering the graphs satisfying the following property: for everyvertex v ∈ A, there exist exactly two vertices x and y of V\A such that N(v) ⊆ N[x] ∪ N[y]. We extend some other knownresults on claw-free graphs to this new class of graphs.

Keywords

Graph theoryclaw-free graphsalmost claw-freegraphsHamiltonicitymatching.
Type
Research Article
Information
RAIRO - Operations Research , Volume 43 , Issue 1 , January 2009 , pp. 103 - 113
Copyright
© EDP Sciences, ROADEF, SMAI, 2009

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

D. Bauer et al., Long cycles in graphs with large degree sums. Discrete Math. 79 (1989/90) 59–70.
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).
H.J. Broersma, Hamilton cycles in graphs and related topics. Ph.D. Thesis, University of Twente (1988).
Broersma, H.J., Ryjacek, Z. and Schiermeyer, E.F., Toughness and Hamiltonicity in almost claw-free graphs. J. Graph theory 21 (1996) 431–439. 3.0.CO;2-Q>CrossRef
Chvatal, V., Tough graphs and Hamiltonian circuits. Discrete Math. 5 (1973) 215–228. CrossRef
Faudree, R.J., Flandrin, E. and Ryjácek, Z., Claw-free graphs – A survey. Discrete Math. 164 (1997) 87–147. CrossRef
Flandrin, E. and Hamiltonism, H. Li and claws. Ars Combinatoria 29C (1990) 77–89.
Li, H., Lu, M. and Sun, Z., Hamiltonicity in 2-connected graphs with claws. Discrete Math. 183 (1998) 223–236. CrossRef
Matthews, M. and Sumner, D.P., Hamiltonian results in K1,3 -free graphs. J. Graph Theory 8 (1984) 139–146. CrossRef
Matthews, M. and Sumner, D.P., Longest paths and cycles in K1,3-free graphs. J. Graph Theory 9 (1985) 269–277. CrossRef
0. Ore, Hamilton, connected graphs. J. Math. Pure Appl. 42 (1963) 21–27.
Ryjacek, Z., Almost claw-free graphs. J. Graph Theory 18 (1994) 469–477. CrossRef
Ryjácek, Z., On a closure concept in claw-free graphs. J. Combinat. Theory B70 (1997) 217–224. CrossRef
D.P. Sumner, Graphs with 1-factors. Proceeding of the American Mathematical Society (1974) 8–12.
Sumner, D.P., 1-factors and antifactors sets. J. London Math. Soc. 213 (1976) 351–359. CrossRef
Thomassen, C., Reflections on graph theory. J Graph Theory 10 (1986) 309–324. CrossRef
Zhang, C.Q., Hamilton cycles in claw-free graphs. J. Graph Theory 12 (1988) 209–216. CrossRef