Article ID Journal Published Year Pages File Type
4653127 Electronic Notes in Discrete Mathematics 2006 4 Pages PDF
Abstract

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.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics