Minimally 3-Connected Graphs with Exactly k Non-Essential Edges
Received:November 03, 2005  
Key Words: minimally 3-connected graph   non-essential edge   fan   wheel.  
Fund Project:the National Natural Science of China (10171022)
Author NameAffiliation
LIU Yu-xing Dept. of Math., Ganzhou Teacher's College, Jiangxi 341000, China 
SU Jian-ji College of Math. & Comput. Sci., Guangxi Normal University, Guilin 541004, China 
Hits: 2990
Download times: 1495
Abstract:
      Let $G$ be a simple 3-connected graph. An edge $e$ of a simple 3-connected graph $G$ is essential if neither the deletion $G\backslash e$ nor the contraction $G/e$ is simple and 3-connected. For essential edges of a 3-connected graph, Tutte obtained the following theorem.\\[8pt]{\bf Theorem 1}\ \ {\sl Let $G$ be a simple 3-connected graph. Then every edge is essential if and only if $G$ is a wheel.} This theorem ensures the existence of at least one non-essential edge in every simple 3-connected graph that is not a wheel. The existence of non-essential edges has become a powerful induction tool. Oxley and Wu proved that if $G$ is a minimally 3-connected graph that is not a wheel, then there are at least three non-essential edges, and characterized the minimally 3-connected graphs with exactly three non-essential edges. Reid and Wu also determined all minimally 3-connected graphs with at most five non-essential edges. In this paper, we use a quite different way to solve this problem. We prove the result by constructing all of the minimally 3-connected graphs with exactly $k$ non-essential edges through several operations, starting with a wheel. That is, firstly, in a minimally 3-connected graph, we define the following three operations: {\bf Operation One}: Deletion of any deletable vertex. {\bf Operation Two}: If the hub of a non-trivial fan is incident to only one edge out of the fan, then all the inner-vertices of the fan and the hub of the non-trivial fan are contracted into a vertex. If the vertex is a deletable vertex, then it is deleted. {\bf Operation Three}: If the hub of a non-trivial fan is incident to two or more edges out of the fan, then the non-trivial fan is transformed into a triad (that is, in the non-trivial fan, we contract all arcs and delete loops and multi-edges). First, if the three edges of the triad are simple-contractible, the simple-contractible edge that is incident to the hub of the former non-trivial fan is contracted. All the generated deletable edges are deleted in turn, till there are no deletable edges in the graph. Secondly, if there are exactly two simple-contractible edges in the triad, then any one of them is contracted, and all the generated deletable edges are deleted in turn, till there are no deletable edges in the graph. For any non-trivial fan. Operation One is applied on any one of contractible edges chosen from the fan. Then by the above operations and the operation of adding edges, we can construct all minimally 3-connected graphs with exactly $k~(k\geq{3})$ non-essential edges, starting with a wheel. By induction, a minimally 3-connected graph with exactly $k~(k\geq{4})$ non-essential edges, can be transformed into a minimally 3-connected graph with much less non-essential edges by a series of these operations. According to the induction hypothesis, a minimally 3-connected graph with less than $k$ non-essential edges can be obtained from a wheel by the inverse of the used operations. Therefore, a minimally 3-connected graph with exactly $k$ non-essential edges can be obtained from a wheel by the inverse of the used operations. In this way, all minimally 3-connected graphs with exactly $k$ non-essential edges can be constructed completely. So, we obtain the following main result of the paper: \\[8pt]{\bf Theorem 2}\ \ {\sl $G_{k}~(k\geq{3})$ can be transformed into $W$ through a series of Operation One, Two, Three and the deletion of edges. Hence, $G_{k}~(k\geq{3})$ can be obtained from a wheel by the inverse of the used operations, where $G_{k}$ and $W$ are used to denote a minimally 3-connected graph with exactly $k$ non-essential edges and a wheel, respectively.
Citation:
DOI:10.3770/j.issn:1000-341X.2006.04.026
View Full Text  View/Add Comment