کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
420674 683968 2009 9 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Hamiltonian connectedness in 3-connected line graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Hamiltonian connectedness in 3-connected line graphs
چکیده انگلیسی

We investigate graphs GG such that the line graph L(G)L(G) is hamiltonian connected if and only if L(G)L(G) is 3-connected, and prove that if each 3-edge-cut contains an edge lying in a short cycle of GG, then L(G)L(G) has the above mentioned property. Our result extends Kriesell’s recent result in [M. Kriesell, All 4-connected line graphs of claw free graphs are hamiltonian-connected, J. Combin. Theory Ser. B 82 (2001) 306–315] that every 4-connected line graph of a claw free graph is hamiltonian connected. Another application of our main result shows that if L(G)L(G) does not have an hourglass (a graph isomorphic to K5−E(C4)K5−E(C4), where C4C4 is an cycle of length 4 in K5K5) as an induced subgraph, and if every 3-cut of L(G)L(G) is not independent, then L(G)L(G) is hamiltonian connected if and only if κ(L(G))≥3κ(L(G))≥3, which extends a recent result by Kriesell [M. Kriesell, All 4-connected line graphs of claw free graphs are hamiltonian-connected, J. Combin. Theory Ser. B 82 (2001) 306–315] that every 4-connected hourglass free line graph is hamiltonian connected.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 157, Issue 5, 6 March 2009, Pages 982–990
نویسندگان
, , , ,