|
|
|
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:
| AUTHOR | = | {Jord{\'a}n, Tibor}, |
| TITLE | = | {A characterisation of weakly four-connected graphs}, |
| NOTE | = | {{\tt www.cs.elte.hu/egres}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2003}, |
| NUMBER | = | {TR-2003-08} |