Hamiltonicity in Partly claw-free graphs

Moncef Abbas; Zineb Benmeziane

RAIRO - Operations Research (2009)

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

Abstract

top

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.

How to cite

top

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

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.