Hostname: page-component-cd9895bd7-7cvxr Total loading time: 0 Render date: 2024-12-23T14:04:03.649Z Has data issue: false hasContentIssue false
  • English
  • Français

Weakly 3-Connected Graphs

Published online by Cambridge University Press:  07 June 2006

DONALD K. WAGNER
DONALD K. WAGNER
Affiliation:
Mathematical, Computer, and Information Sciences Division, Office of Naval Research, Arlington, VA 22203, USA (e-mail: [email protected])
Get access Rights & Permissions [Opens in a new window]

Abstract

A 3-connected graph $G$ is weakly 3-connected if, for every edge $e$ of $G$, at most one of $G\backslash e$ and $G/e$ is 3-connected. The main result of this paper is that any weakly 3-connected graph can be reduced to $K_4$ by a sequence of simple operations. This extends a result of Dawes [5] on minimally 3-connected graphs.

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 15 , Issue 4 , July 2006 , pp. 605 - 617
Copyright
2006 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)