Paper Info

Title | ||
---|---|---|

The Existence of a 2-Factor in a Graph Satisfying the Local Chvátal-Erdös Condition. |

Abstract | ||
---|---|---|

The well-known Chvatal-Erdos theorem states that every graph G of order at least three with alpha(G) <= kappa(G) has a Hamiltonian cycle, where alpha(G) and kappa(G) are the independence number and the connectivity of G, respectively. Oberly and Sumner [J. Graph Theory, 3 (1979), pp. 351356] have proved that every connected, locally connected claw-free graph of order at least three has a Hamiltonian cycle. We study the connection of these two theorems. For x is an element of V(G), let B(x) denote the subgraph of G induced by the closed neighborhood of x. Then the theorem by Oberly and Sumner says that a connected graph G of order at least three satisfying alpha(B(x)) <= 2 <= kappa(B(x)) for every vertex x has a Hamiltonian cycle. The comparison of this theorem with the Chvatal-Erdos theorem leads us to suspect that the threshold 2 between alpha(B(x)) and kappa(B(x)) is not necessary. We say that G satisfies the local Chvatal-Erdos condition if alpha(B(x)) <= kappa(B(x)) holds for every vertex x in G. The second author conjectured that if the order of a connected graph G is at least three and satisfies the local Chvatal-Erdos condition, then G has a Hamiltonian cycle. In this paper, we support this conjecture by proving that under this assumption, G is 1-tough and has a 2-factor. |

Year | DOI | Venue |
---|---|---|

2013 | 10.1137/12090037X | SIAM JOURNAL ON DISCRETE MATHEMATICS |

Keywords | Field | DocType |

Chvatal-Erdos theorem,Hamiltonian cycle,2-factor,toughness,independence number,connectivity | Discrete mathematics,Graph,Combinatorics,Independence number,Kappa,Hamiltonian path,Mathematics | Journal |

Volume | Issue | ISSN |

27 | 4 | 0895-4801 |

Citations | PageRank | References |

4 | 0.50 | 3 |

Authors | ||

3 |

Authors (3 rows)

Cited by (4 rows)

References (3 rows)

Name | Order | Citations | PageRank |
---|---|---|---|

G. Chen | 1 | 32 | 8.36 |

Akira Saito | 2 | 361 | 64.55 |

Songling Shan | 3 | 20 | 9.16 |