|
|
- 2016
k-连通图中生成树和完美匹配上的可收缩边
|
Abstract:
摘要： 给出了k-连通图生成树和完美匹配上的可收缩边数目,得到如下结果:任意断片的阶都大于「k/2的k-连通图中生成树上至少有4条可收缩边;若该k-连通图中存在完美匹配,则完美匹配上至少有「k/2+1条可收缩边。
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
| [1] | MARTIONV N. Uncontractible 4-connected graphs[J]. Graph Theory, 1982, 6(3):343-344. |
| [2] | 王珊珊.<i>k</i>-连通图中最长圈上可收缩边的数目[J].山东大学学报(理学版),2015,50(10):27-31. WANG Shanshan. On the number of contractible edges of longest cycles in <i>k</i>-connected graphs[J]. Journal of Shandong University(Natural Science), 2015, 50(10):27-31. |
| [3] | BONDY J A, MURTY U S R. Graph theory with applications [M]. London: The Macmillan Press Ltd, 1976. |
| [4] | 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. |
| [5] | EGAWA Y. Contractible edges in n-connected graphs with minimum degree greater than or equal to[5<i>n</i>/4] [J]. Graphs Comb, 1990, 7:15-21. |
| [6] | KRIESELL M. A survey on contractible edges in graph of a prescribed vertex connectivity[J]. Graphs and Combinatorics, 2002, 18(1):1-30. |
| [7] | 杨朝霞.某些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. |
| [8] | TUTTE W T.A theory of 3-connected graphs[J]. Indag Math, 1961, 23:441-455. |
| [9] | DEAN N. Distribution of contractible edges in <i>k</i>-connected graphs[J]. Comb. Theory, Ser.B, 1990, 48:1-5. |
