Title of article :
Splitting and contractible edges in 4-connected graphs
Author/Authors :
Saito، نويسنده , , Akira، نويسنده ,
Issue Information :
روزنامه با شماره پیاپی سال 2003
Pages :
9
From page :
227
To page :
235
Abstract :
Let G be a graph and let x be a vertex of degree four with NG(x)={a,b,c,d}. Then the operation of deleting x and adding the edges ab and cd is called splitting at x. An edge e of a graph G is said to be k-contractible if contraction of e yields a k-connected graph. Splitting has been studied as a reduction method to preserve edge-connectivity. In this paper, we consider splitting and 4-contractible edges as tools for reduction of 4-connected graphs. We prove that for a 4-connected graph G of order at least six, there exists either a 4-contractible edge or a vertex eligible for splitting preserving 4-connectedness near every vertex in G.
Keywords :
4-Connected graphs , contraction , splitting
Journal title :
Journal of Combinatorial Theory Series B
Serial Year :
2003
Journal title :
Journal of Combinatorial Theory Series B
Record number :
1527236
Link To Document :
بازگشت