کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4649986 1342471 2008 4 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A note on the dominating circuit conjecture and subgraphs of essentially 4-edge-connected cubic graphs
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
A note on the dominating circuit conjecture and subgraphs of essentially 4-edge-connected cubic graphs
چکیده انگلیسی

The well-known dominating circuit conjecture has several interesting reformulations, for example conjectures of Fleischner, Matthews and Sumner, and Thomassen. We present another equivalent version of the dominating circuit conjecture considering subgraphs of essentially 4-edge-connected cubic graphs.Let S={u1,u2,u3,u4}S={u1,u2,u3,u4} be a set of four distinct vertices of a graph GG and V2(G)V2(G) be a set of all vertices of degree 2 of a graph GG. We say that GG is SS-strongly dominating if the graph arising from GG after adding two new edges e1=xye1=xy and e2=wze2=wz such that {x,y,w,z}=S{x,y,w,z}=S has a dominating closed trail containing e1e1 and e2e2. We show that the dominating circuit conjecture is equivalent to the statement that any subgraph HH of an essentially 4-edge-connected cubic graph with |V2(H)|=4|V2(H)|=4 and minimum degree δ(H)=2δ(H)=2 is strongly V2(H)V2(H)-dominating.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Mathematics - Volume 308, Issue 23, 6 December 2008, Pages 5801–5804
نویسندگان
,