کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4653127 | 1632607 | 2006 | 4 صفحه PDF | دانلود رایگان |

The well-known Dominating circuit conjecture has several interesting reformulation, for example conjectures of Fleischner, Matthews-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} be a set of four distinct vertices of a graph G and V2(G) be a set of all vertices of degree 2 of a graph G. We say that G is S-strongly dominating if the graph arising from G after adding two new edges e1=xy and e2=wz such that {x,y,w,z}=S has a dominating circuit containing e1 and e2. We show, that the dominating circuit conjecture is equivalent with the statement that any subgraph H of essentially 4-edge-connected cubic graph with |V2(H)|=4 and minimum degree δ(H)=2 is strongly V2(H)-dominating.
Journal: Electronic Notes in Discrete Mathematics - Volume 24, 15 July 2006, Pages 101-104