A well-equalized 3-CIST partition of alternating group graphs

A set of k (>= 2) spanning trees in a graph is called completely independent spanning trees (CISTs for short) if they are pairwise edge-disjoint and internally vertex-disjoint. Although the problem of determining whether a graph G admits k CISTs is NP-complete even for k = 2, there exists a characterization called k-CIST partition for which the instances can easily be verified. A k-CIST partition of a graph G = (V, E) is a partition of V into V-1, V-2, ..., V-k such that the subgraph of G induced by V-1, denoted by G[V,], is connected for i is an element of {1, 2, , k}, and the bipartite graph induced by the edge set {(x, y) is an element of E : x is an element of V-i, y is an element of V-j}, denoted by B(V-i, V-j, G), has no tree component for i, j is an element of {1, 2, ..., k} with i not equal j. Moreover, a k-CIST partition is well-equalized provided all G[V-i] are isomorphic for i is an element of (1,2, ..., k} and all B(V-i, V-j, G) are isomorphic for distinct i, j is an element of {1, 2, ... , k}. The class of alternating group graphs is a kind of well-studied interconnection networks, which forms a famous subclass of Cayley graphs and possesses a large number of desirable properties of networks. Let AG(n) denote the n-dimensional alternating group graph. In this paper, we show that AG(n) admits a well-equalized 3-CIST partition. As a by-product, we obtain a constructing scheme of three CISTs for AG(n). (C) 2019 Elsevier B.V. All rights reserved.