Discussiones Mathematicae Graph Theory (Aug 2015)

Completely Independent Spanning Trees in (Partial) k-Trees

  • Matsushita Masayoshi,
  • Otachi Yota,
  • Araki Toru

DOI
https://doi.org/10.7151/dmgt.1806
Journal volume & issue
Vol. 35, no. 3
pp. 427 – 437

Abstract

Read online

Two spanning trees T1 and T2 of a graph G are completely independent if, for any two vertices u and v, the paths from u to v in T1 and T2 are internally disjoint. For a graph G, we denote the maximum number of pairwise completely independent spanning trees by cist(G). In this paper, we consider cist(G) when G is a partial k-tree.

Keywords