| Removable Edges in a 5-Connected Graph |
| Received:July 08, 2009 Revised:January 18, 2010 |
| Key Words:
5-connected graph removable edge edge-vertex-atom.
|
| Fund Project:Supported by the National Natural Science Foundation of China (Grant No.10831001) and the Science-Technology Foundation for Young Scientists of Fujian Province (Grant No.2007F3070). |
|
| Hits: 2438 |
| Download times: 2500 |
| Abstract: |
| An edge $e$ of a $k$-connected graph $G$ is said to be a removable edge if $G\ominus e$ is still $k$-connected, where $G\ominus e$ denotes the graph obtained from $G$ by deleting $e$ to get $G-e$, and for any end vertex of $e$ with degree $k-1$ in $G-e$, say $x$, delete $x$, and then add edges between any pair of non-adjacent vertices in $N_{G-e}(x)$. The existence of removable edges of $k$-connected graphs and some properties of 3-connected and 4-connected graphs have been investigated [1,\,11,\,14,\,15]. In the present paper, we investigate some properties of 5-connected graphs and study the distribution of removable edges on a cycle and a spanning tree in a 5-connected graph. Based on the properties, we proved that for a 5-connected graph $G$ of order at least 10, if the edge-vertex-atom of $G$ contains at least three vertices, then $G$ has at least $(3|G| 2)/2$ removable edges. |
| Citation: |
| DOI:10.3770/j.issn:1000-341X.2011.04.005 |
| View Full Text View/Add Comment |
|
|
|
