TR-2003-08

A characterisation of weakly four-connected graphs

Tibor Jordán

Published in:
J. Graph Theory, Vol. 52, Issue 3, 217-229, 2006.

A graph G=(V,E) is called weakly four-connected if G is 4-edge-connected and G-x is 2-edge-connected for all x \in V. We give sufficient conditions for the existence of `splittable' vertices of degree four in weakly four-connected graphs. By using these results we prove that every minimally weakly four-connected graph on at least four vertices contains at least three `splittable' vertices of degree four, which gives rise to an inductive construction of weakly four-connected graphs. Our results can also be applied in the problem of finding 2-connected orientations of graphs.

Bibtex entry:

@techreport{egres-03-08,

AUTHOR	=	{Jord{\'a}n, Tibor},
TITLE	=	{A characterisation of weakly four-connected graphs},
NOTE	=	{{\tt egres.elte.hu}},
INSTITUTION	=	{Egerv{\'a}ry Research Group, Budapest},
YEAR	=	{2003},
NUMBER	=	{TR-2003-08}

}