A result on quasi k-connected graphs

详细信息    查看全文

• 作者：Ying-qiu Yang
• 关键词：05C40 ; Component ; k ; connected graph ; quasi k ; connected graph
• 刊名：Applied Mathematics - A Journal of Chinese Universities
• 出版年：2015
• 出版时间：June 2015
• 年：2015
• 卷：30
• 期：2
• 页码：245-252
• 全文大小：164 KB
• 参考文献：[1]J A Bondy, U S RMurty. Graph Theory with Applications, London, MacMillan, 1976.MATH
  [2]Y Egawa. Contractible edges in n-connected graphs with minimum degree greater than or equal to [ \(\frac{{5n}}{4}]\) ] , Graphs Combin, 1991, 7: 15-1.MATH MathSciNet
  [3]H Jiang, J Su. Some properties of quasi (k +1)-connected graphs, J Guangxi Normal Univ, 2001, 19(4): 26-9. (in Chinese)
  [4]H Jiang, J Su. Minimum degree of minimally quasi (k+1)-connected graphs, J Math Study, 2002, 35(2): 187-93. (in Chinese)MATH MathSciNet
  [5]K Kawarabayashi. Note on k-contractible edges in k-connected graphs, Australas J Combin, 2001, 24: 165-68.
  [6]T Politof, A Satyanarayana. Minors of quasi 4-connected graphs, Discrete Math, 1994, 126: 245-56.MATH MathSciNet
  [7]T Politof, A Satyanarayana. The structure of quasi 4-connected graphs, Discrete Math, 1996, 161: 217-28.MATH MathSciNet
  [8]J Su, X Guo, L Xu. Removable edges in a k-connected graph and a construction method for kconnected graphs, Discrete Math, 2009, 309: 3161-165.MATH MathSciNet
  [9]C Thomassen. Non-separating cycles in k-connected graphs, J Graph Theory, 1981, 5: 351-54.MATH MathSciNet
  [10]L Xu, X Guo. Removable edges in a 5-connected graph and a construction method of 5-connected graphs, Discrete Math, 2008, 308: 1726-731.MATH MathSciNet
  
• 作者单位：Ying-qiu Yang (1) (2)
  
  1. School of Mathematics, Beijing Institute of Technology, Beijing, 100081, China
  2. School of Mathematics and Physics, Anshun University, Anshun, 561000, China
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Mathematics
  Applications of Mathematics
  Chinese Library of Science
  
• 出版者：Editorial Committee of Applied Mathematics - A Journal of Chinese Universities
• ISSN：1993-0445

文摘

Let G be a k-connected graph, and T be a subset of V (G). If G-T is not connected, then T is said to be a cut-set of G. A k-cut-set T of G is a cut-set of G with |T| = k. Let T be a k-cut-set of a k-connected graph G. If G - T can be partitioned into subgraphs G ₁ and G ₂ such that |G ₁| ?2, |G ₂| ?2, then we call T a nontrivial k-cut-set of G. Suppose that G is a (k -1)-connected graph without nontrivial (k -1)-cut-set. Then we call G a quasi k-connected graph. In this paper, we prove that for any integer k ?5, if G is a k-connected graph without K ?/sup> ₄, then every vertex of G is incident with an edge whose contraction yields a quasi k-connected graph, and so there are at least \(\frac{{|V(G)|}}{2}\) edges of G such that the contraction of every member of them results in a quasi k-connected graph.