Search

For the underlying graph G of a network, k (⩾ 2) spanning trees of G are called completely independent spanning trees (CISTs for short) if they are mutually inner-node-disjoint. It is well-known that determining the existence of k CISTs in a graph is an NP-hard problem, even for k = 2. Also, there exists a k -connected graph which does not possess two CISTs for any k ⩾ 2. Accordingly, researches focused on the problem of constructing multiple CISTs in some particular famous networks. Pai and Chang (2016) proposed a unified approach to recursively construct two CISTs with diameter 2 n − 1 in several n -dimensional hypercube-variant networks for n ⩾ 4 , including locally twisted cubes L T Q n and crossed cubes C Q n. Later on, new constructions showed that the diameter of two CISTs can be reduced to 2 n − 2 if n = 4 and 2 n − 3 if n ⩾ 5 for L T Q n , and to 2 n − 2 if n = 4 , 5 and 2 n − 3 if n ⩾ 6 for C Q n. In this paper, we intend to construct more CISTs for those networks that are paid attention. We develop a novel tree searching algorithm, called two-stages tree-searching algorithm (abbreviated as TS 2), which can be used to construct three CISTs of a 6-regular graph if the scale of the graph is not too large and there exist three CISTs for certain. In particular, we demonstrate that three CISTs of L T Q 6 and C Q 6 can be acquired by using TS 2. Moreover, for high-dimensional L T Q n and C Q n with n ⩾ 7 , we show that their three CISTs can be constructed by recursion. Consequently, we obtain the following results: (i) For L T Q n , the diameters of three CISTs we constructed are 11, 12 and 12 when n = 6 , and all are 2 n − 1 when n ⩾ 7 ; (ii) For C Q n , all diameters of three CISTs we constructed are 12 when n = 6 , and 2 n + 1 when n ⩾ 7. [ABSTRACT FROM AUTHOR]

In this paper, we consider rainbow connection number of maximal outerplanar graphs (MOPs) on algorithmic aspect. For the (MOP) G , we give sufficient conditions to guarantee that r c ( G ) = d i a m ( G ) . Moreover, we produce the graph with given diameter D and give their rainbow coloring in linear time. X. Deng et al. [4] give a polynomial time algorithm to compute the rainbow connection number of MOPs by the Maximal fan partition method, but only obtain a compact upper bound. J. Lauri [11] proved that, for chordal outerplanar graphs given an edge-coloring, to verify whether it is rainbow connected is NP-complete under the coloring, it is so for MOPs. Therefore we construct Central-cut-spine of MOP G , by which we design an algorithm to give a rainbow edge coloring with at most 2 r a d ( G ) + 2 + c , 0 ≤ c ≤ r a d ( G ) − 2 colors in polynomial time. [ABSTRACT FROM AUTHOR]

Abstract: Double-loop networks have been widely studied as an architecture for local area networks. It is well known that the minimum distance diagram of a double-loop network yields an L-shape. Given a positive integer , it is desirable to find a double-loop network with its diameter being the minimum among all double-loop networks with nodes. Since the diameter of a double-loop network can be easily computed from its L-shape, one method is to start with a desirable L-shape and then find a double-loop network to realize it. This is a problem discussed by many authors [F. Aguiló, M.A. Fiol, An efficient algorithm to find optimal double loop networks, Discrete Math. 138 (1995) 15–29, R.C. Chan, C.Y. Chen, Z.X. Hong, A simple algorithm to find the steps of double-loop networks, Discrete Appl. Math. 121 (2002) 61–72, C.Y. Chen, F.K. Hwang, The minimum distance diagram of double-loop networks, IEEE Trans. Comput. 49 (2000) 977–979, P. Esqué, F. Aguiló, M.A. Fiol, Double commutative-step diagraphs with minimum diameters, Discrete Math. 114 (1993) 147–157] and it has been open for a long time whether this problem can be solved in time. In this paper, we will provide a simple and efficient -time algorithm for solving this problem. [Copyright &y& Elsevier]

A double-loop digraph G=G(N;s1,s2), with gcd(N,s1,s2)=1, has the set of vertices V=ZN and the adjacencies are given by u→u+si (mod N) i=1,2. The diameter of G, denoted by D(N;s1,s2), is known to be lower bounded by lb(N) withThis lower bound is known to be sharp. For a fixed N∈N, some algorithms to find D(N) and steps 1⩽α<β such that D(N;α,β)=D(N) are known through the bibliography, being of numerical nature all of them.In this paper we propose a symbolic algorithm on the following problem: Given a number of vertices N0∈N, find if possible an infinite family of tight double-loop digraphs G(x)=G(N(x);s1(x),s2(x)) such that N(x0)=N0 and D(x)=D(N(x);s1(x),s2(x))=lb(N(x)) ∀x⩾x0. This family is parameterized by the integer x with N(x)∈Z and s1(x),s2(x)∈Z/(N(x)). As a direct consequence of such an explicit family of digraphs G(x), we also have an additive basis {s1(x),s2(x)} which covers the elements of Z/(N(x)) with optimal order.The time cost of this algorithm is O(√ of N0 log N0), in the worst case. [Copyright &y& Elsevier]