کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4648993 | 1632436 | 2010 | 9 صفحه PDF | دانلود رایگان |

A classical result of Chvátal and Erdös says that the graph GG with connectivity κ(G)κ(G) not less than its independence number α(G)α(G) (i.e. κ(G)≥α(G)κ(G)≥α(G)) is Hamiltonian. In this paper, we show that the 2-connected graph GG with κ(G)≥α(G)−1κ(G)≥α(G)−1 is one of the following: supereulerian, the Petersen graph, the 2-connected graph with three vertices of degree two obtained from K2,3K2,3 by replacing a vertex of degree three with a triangle, one of the 2-connected graphs obtained from K2,3K2,3 by replacing a vertex of degree two with a complete graph of order at least three and by replacing at most one branch of length two in the resulting graph with a branch of length three, or one of the graphs obtained from K2,3K2,3 by replacing at most two branches of K2,3K2,3 with a branch of length three. We also show that the Hamiltonian index of the simple 2-connected graph GG with κ(G)≥α(G)−tκ(G)≥α(G)−t is at most ⌊2t+23⌋ for every nonnegative integer tt. The upper bound is sharp.
Journal: Discrete Mathematics - Volume 310, Issues 15–16, 28 August 2010, Pages 2082–2090