3-正则3-连通图的圈上的可去边分布

Distribution of Removable Edges in the Cycles of 3-Regular 3-Connected Graphs

设G是k-连通图,e是G的一条边,由G-e经过删除度为k-1的顶点u,并用完全图K_(k-1)代替导出子图(G-e)[N(u)]得到的图记为G■e.若G■e仍是k-连通的,则称e是可去边.该文证明了3-正则3-连通图的最长圈至少有4条可去边,且有无穷多的例子说明这个界可达到.

Let G be a k-connected graph and e an edge of G.Denote by G■e the graph obtained from G-e by deleting each vertex u of degree k-1 in G-e and replacing the induced subgraph(G-e)[N(u)]with the complete graph K_(k-1).An edge e is said to be removable if G■e is also k-connected.We show that each longest cycle of a 3-connected cubic graph has at least four removable edges,and there are infinitely many graphs that attain this bound.