A Preliminary Study of the Completely Independent Spanning Trees Problem
| Autor: | Hung-Yi Chang, 張弘毅 |
|---|---|
| Rok vydání: | 2015 |
| Druh dokumentu: | 學位論文 ; thesis |
| Popis: | 103 In a graph G, a set of spanning trees are said to be completely independent if for any vertices u and v, the paths connecting them on the spanning trees have neither vertex nor edge in common, except u and v. In this thesis, we prove that for graphs of order n, with n ≥ 6, if the minimum degree is at least n - 2, then there are ⌊ n/3 ⌋ completely independent spanning trees. Also, we show that there are two completely independent spanning trees on chordal rings CR(N,d), where N ≥ 5 and d = ⌈ N/2 ⌉ -1 or both N and d are even integers. |
| Databáze: | Networked Digital Library of Theses & Dissertations |
| Externí odkaz: |
|