کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4648993 1632436 2010 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
The Chvátal–Erdös condition for supereulerian graphs and the Hamiltonian index
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
The Chvátal–Erdös condition for supereulerian graphs and the Hamiltonian index
چکیده انگلیسی

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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 310, Issues 15–16, 28 August 2010, Pages 2082–2090
نویسندگان
, , , ,