Removable edges in a 5-connected graph and a construction method of 5-connected graphs |
| |
Authors: | Liqiong Xu Xiaofeng Guo |
| |
Institution: | a School of Mathematical Sciences, Xiamen University, Xiamen, Fujian 361005, China b School of Sciences, Jimei University, Xiamen 361021, China |
| |
Abstract: | An edge e of a k-connected graph G is said to be a removable edge if G?e is still k-connected. A k-connected graph G is said to be a quasi (k+1)-connected if G has no nontrivial k-separator. The existence of removable edges of 3-connected and 4-connected graphs and some properties of quasi k-connected graphs have been investigated D.A. Holton, B. Jackson, A. Saito, N.C. Wormale, Removable edges in 3-connected graphs, J. Graph Theory 14(4) (1990) 465-473; H. Jiang, J. Su, Minimum degree of minimally quasi (k+1)-connected graphs, J. Math. Study 35 (2002) 187-193; T. Politof, A. Satyanarayana, Minors of quasi 4-connected graphs, Discrete Math. 126 (1994) 245-256; T. Politof, A. Satyanarayana, The structure of quasi 4-connected graphs, Discrete Math. 161 (1996) 217-228; J. Su, The number of removable edges in 3-connected graphs, J. Combin. Theory Ser. B 75(1) (1999) 74-87; J. Yin, Removable edges and constructions of 4-connected graphs, J. Systems Sci. Math. Sci. 19(4) (1999) 434-438]. In this paper, we first investigate the relation between quasi connectivity and removable edges. Based on the relation, the existence of removable edges in k-connected graphs (k?5) is investigated. It is proved that a 5-connected graph has no removable edge if and only if it is isomorphic to K6. For a k-connected graph G such that end vertices of any edge of G have at most k-3 common adjacent vertices, it is also proved that G has a removable edge. Consequently, a recursive construction method of 5-connected graphs is established, that is, any 5-connected graph can be obtained from K6 by a number of θ+-operations. We conjecture that, if k is even, a k-connected graph G without removable edge is isomorphic to either Kk+1 or the graph Hk/2+1 obtained from Kk+2 by removing k/2+1 disjoint edges, and, if k is odd, G is isomorphic to Kk+1. |
| |
Keywords: | Removable edge Contractible edge Quasi connectivity _method=retrieve& _eid=1-s2 0-S0012365X07002464& _mathId=si14 gif& _pii=S0012365X07002464& _issn=0012365X& _acct=C000053510& _version=1& _userid=1524097& md5=803f7a6ae7facff24c8909634b6ad71d')" style="cursor:pointer θ+-Operation" target="_blank">" alt="Click to view the MathML source" title="Click to view the MathML source">θ+-Operation |
本文献已被 ScienceDirect 等数据库收录! |
|