A set of spanning trees of a graphs G are called completely independent spanning trees (CISTs for short) if for every pair of vertices x, y∈V(G), the paths joining x and y in any two trees have neither vertex nor edge in common, except x and y. Constructing CISTs has applications on interconnection networks such as fault-tolerant routing and secure message transmission. In this paper, we investigate the problem of constructing two CISTs in the balanced hypercube BHn, which is a hypercube-variant network and is superior to hypercube due to having a smaller diameter. As a result, the diameter of CISTs we constructed equals to 9 for BH2 and 6n-2 for BHn when n≥3.

Given a graph G, a set of spanning trees of G are completely independent spanning trees (CISTs for short) if for any vertices x and y, the paths connecting them on these trees have neither vertex nor edge in common, except x and y. Hasunuma (2001, 2002) first introduced the concept of CISTs and conjectured that there are k CISTs in any 2k-connected graph. Later on, this conjecture was unfortunately disproved by Péterfalvi (2012). In this note, we show that Hasunuma's conjecture holds for graphs restricted in the class of 4-regular chordal rings CR(n,d), where both n and d are even integers.

Two spanning trees T1,T2 of a graph G = (V,E) are independent if they are rooted at the same vertex, say r, and for each vertex v ∈ V, the path from r to v in T1 and the path from r to v in T2 have no common vertices and no common edges except for r and v. In general, spanning trees T1,T2,…,Tk of a graph G = (V,E) are independent if they are pairwise independent. A graph G = (V,E) is called a 2-chordal ring and denoted by CR(N,d1,d2), if V = {0,1,…,N-1} and E = {(u,v)|[v-u]N = 1 or [v-u]N = d1 or [v-u]N = d2, 2 ≤ d1 < d2 ≤ N/2}. CR(N,d1,N/2) is 5-connected if N ≥ 8 is even and d1 ≠ N/2-1. We give an algorithm to construct 5 independent spanning trees of CR(N,d1,N/2),N ≥ 8 is even and 2 ≤ d1 ≤ ⌈N/4⌉.

Let T1,T2,...,Tk be spanning trees in a graph G. If, for any two vertices u,v of G, the paths joining u and v on the k trees are mutually vertex-disjoint, then T1,T2,...,Tk are called completely independent spanning trees (CISTs for short) of G. The construction of CISTs can be applied in fault-tolerant broadcasting and secure message distribution on interconnection networks. Hasunuma (2001) first introduced the concept of CISTs and conjectured that there are k CISTs in any 2k-connected graph. Unfortunately, this conjecture was disproved by Péterfalvi recently. In this note, we give a necessary condition for k-connected k-regular graphs with ⌊k/2⌋ CISTs. Based on this condition, we provide more counterexamples for Hasunuma's conjecture. By contrast, we show that there are two CISTs in 4-regular chordal rings CR(N,d) with N=k(d-1)+j under the condition that k ≥ 4 is even and 0 ≤ j ≤ 4. In particular, the diameter of each constructed CIST is derived.

Consider an undirected graph G=(V,E) with n (=|V|) vertices and m (=|E|) edges. It is well-known that the problem of computing the sequence Nn-1,Nn,...,Nm is #P-complete (see e.g.,[3]), where Ni denotes the number of connected spanning subgraphs with i (n-1!im) edges in G. In this paper, by proving new inequalities on the sequence Nn-1,Nn,...,Nm, we show an interesting and stronger property that the sequence γn-1,γn,...,γm, where γi denotes the average number of spanning trees in the connected spanning subgraphs with i edges, is a convex sequence as well as a monotonically increasing sequence, although this property does not hold for the sequence Nn-1,Nn,...,Nm.

Given a graph G, a designated vertex r and a natural number k, we wish to find k "independent" spanning trees of G rooted at r, that is, k spanning trees such that, for any vertex v, the k paths connecting r and v in the k trees are internally disjoint in G. In this paper we give a linear-time algorithm to find k independent spanning trees in a k-connected maximal planar graph rooted at any designated vertex.

Let T1, , Tn be n spanning trees rooted at node r of graph G. If for any node v, n paths from r to v, each path in each spanning tree of T1, , Tn, are internally disjoint, then T1, , Tn are said to be independent spanning trees rooted at r. A graph G is called an n-channel graph if G has n independent spanning trees rooted at each node of G. We generalize the definition of n-channel graphs. If for any node v of G, among the n paths from r to v, each path in each spanning tree of T1, , Tn, there are k internally disjoint paths, then T1, , Tn are said to be (k,n)-independent spanning trees rooted at r of G. A graph G is called a (k,n)-channel graph if G has (k,n)-independent spanning trees rooted at each node of G. We study two fault-tolerant communication tasks in (k,n)-channel graphs. The first task is reliable broadcasting. We analyze the relation between the reliability and the efficiency of broadcasting in (k,n)-channel graphs. The second task is secure message distribution such that one node called the distributor attempts to send different messages safely to different nodes. We should keep each message secret from the nodes called adversaries. We give two message distribution schemes in (k,n)-channel graphs. The first scheme uses secret sharing, and it can tolerate up to t+k-n listening adversaries for any t < n if G is a (k,n)-channel graph. The second scheme uses unverifiable secret sharing, and it can tolerate up to t+k-n disrupting adversaries for any t < n/3 if G is a (k,n)-channel graph.

A graph G is called an n-channel graph at vertex r if there are n independent spanning trees rooted at r. A graph G is called an n-channel graph if G is an n-channel graph at every vertex. Independent spanning trees of a graph play an important role in fault-tolerant broadcasting in the graph. In this paper we show that if G1 is an n1-channel graph and G2 is an n2-channel graph, then G1G2 is an (n1 + n2)-channel graph. We prove this fact by a construction of n1+n2 independent spanning trees of G1G2 from n1 independent spanning trees of G1 and n2 independent spanning trees of G2. As an application we describe a fault-tolerant broadcasting scheme along independent spanning trees.