論文

査読有り
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)
  • Toru Hasunuma

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.

リンク情報
DOI
https://doi.org/10.1007/978-3-319-29516-9_22
URL
http://dblp.uni-trier.de/db/conf/iwoca/iwoca2015.html#conf/iwoca/Hasunuma15

エクスポート
BibTeX RIS