2016年

# Minimum degree conditions and optimal graphs for completely independent spanning trees

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

- 巻
- 9538
- 号
- 開始ページ
- 260
- 終了ページ
- 273
- 記述言語
- 英語
- 掲載種別
- 研究論文（国際会議プロシーディングス）
- DOI
- 10.1007/978-3-319-29516-9_22
- 出版者・発行元
- Springer Verlag

Completely independent spanning trees T1 T2, . . . , Tk in a graph G are spanning trees in G such that for any pair of distinct vertices u and v, the k paths in the spanning trees between u and v mutually have no common edge and no common vertex except for u and v. The concept finds applications in fault-tolerant communication problems in a network. Recently, it was shown that Dirac’s condition for a graph to be hamiltonian is also a sufficient condition for a graph to have two completely independent spanning trees. In this paper, we generalize this result to three or more completely independent spanning trees. Namely, we show that for any graph G with n ≥ 7 vertices, if the minimum degree of a vertex in G is at least n − k, where 3 ≤ k ≤ n/2 , then there are (Formula presented.) completely independent spanning trees in G. Besides, we improve the lower bound of n/2 on the Dirac’s condition for completely independent spanning trees to n-1/2 except for some specific graph. Our results are theoretical ones, since these minimum degree conditions can be applied only to a very dense graph. We then present constructions of symmetric regular graphs which include optimal graphs with respect to the number of completely independent spanning trees.

- リンク情報