JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2016, Vol. 51 ›› Issue (8): 29-34.doi: 10.6040/j.issn.1671-9352.0.2016.148

Previous Articles     Next Articles

The contractible edges of a spanning tree and a perfect matching in k-connected graphs

WANG Qian   

  1. School of Mathematics, Shandong University, Jinan 250100, Shandong, China
  • Received:2016-04-06 Online:2016-08-20 Published:2016-08-08

PDF (PC)

1059

Abstract: The numbers of contractible edges of a spanning tree and a perfect matching in k-connected graphs are given. The conclusions are that if every fragment of a k-connected graph has an order more than 「k/2, then there exist at least four contractible edges on the spanning tree of this graph. Furthermore, if this graph has a perfect matching, then there exist at least 「k/2+1 contractible edges on the perfect matching.

Key words: contractible edge, perfect matching, k-connect graph, spanning tree

CLC Number: 

  • O157
[1] BONDY J A, MURTY U S R. Graph theory with applications [M]. London: The Macmillan Press Ltd, 1976.
[2] MARTIONV N. Uncontractible 4-connected graphs[J]. Graph Theory, 1982, 6(3):343-344.
[3] KRIESELL M. A degree sum condition for the existence of a contractible edge in a k-connected graph[J]. Comb Theory Ser, 2001, B82:81-101.
[4] 王珊珊.k-连通图中最长圈上可收缩边的数目[J].山东大学学报(理学版),2015,50(10):27-31. WANG Shanshan. On the number of contractible edges of longest cycles in k-connected graphs[J]. Journal of Shandong University(Natural Science), 2015, 50(10):27-31.
[5] KRIESELL M. A survey on contractible edges in graph of a prescribed vertex connectivity[J]. Graphs and Combinatorics, 2002, 18(1):1-30.
[6] TUTTE W T.A theory of 3-connected graphs[J]. Indag Math, 1961, 23:441-455.
[7] DEAN N. Distribution of contractible edges in k-connected graphs[J]. Comb. Theory, Ser.B, 1990, 48:1-5.
[8] EGAWA Y. Contractible edges in n-connected graphs with minimum degree greater than or equal to[5n/4] [J]. Graphs Comb, 1990, 7:15-21.
[9] 杨朝霞.某些5-连通图中最长圈上的可收缩边[J].山东大学学报(理学版),2008,43(6):12-14. YANG Zhaoxia. The contractible edges of the longest cycle in some 5-connected graphs[J]. Journal of Shandong University(Natural Science), 2008, 43(6):12-14.
[1] XU Zhengquan, DENG Kai. Degree of freedom and anti-degree of freedom of a hexagonal system generated by seven benzene rings [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2026, 61(2): 115-126.
[2] YAN Li, HU Hailin, WANG Gaozhou, ZHANG Wenbin, PAN Fading, ZHANG Xiao, ZHENG Yanwei. Topology construction and control based on long short-term prediction [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2025, 60(9): 41-51.
[3] Hui HAN,Yutong LIU,Haiyuan YAO. Recursive solving of di-forcing polynomials for ladder graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2023, 58(11): 127-134, 146.
[4] SUN Xiao-ling, GAO Yu-bin, DU Jian-wei, REN Jian-bin. Zeroth-order general Randic index of quasi-tree graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2022, 57(12): 96-102.
[5] YANG Rui, LIU Cheng-li, WU Nan-nan. The number of perfect matchings and k-resonance in n-prism [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2022, 57(11): 37-41.
[6] LAI Jin-hua, LIU Meng-meng. On minimum Steiner k-Wiener index of trees with perfect matching [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2022, 57(10): 66-71.
[7] WANG Xia, BIAN Hong, YU Hai-zheng. Inverse of Kronecker product of integrally invertible graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2021, 56(11): 87-92.
[8] WANG Shan-shan, QI En-feng. On the number of contractible edges of longest cycles in k-connected graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2015, 50(10): 27-31.
[9] YAO Ming1, YAO Bing2*， CHEN Xiang-en2. On complete chromatic numbers of cubic Halin graphs [J]. J4, 2012, 47(2): 65-70.
[10] . On the spectrum of matching forcing numbers for bipartite graphs [J]. J4, 2009, 44(12): 30-35.
[11] YANG Zhao-xia . The contractible edges of the longest cycle in some 5-connected graphs [J]. J4, 2008, 43(6): 12-14 .
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd