The number of spanning trees of a graph with given matching number

The number of spanning trees of a graph G is the total number of distinct spanning subgraphs of G that are trees. In this paper, we present sharp upper bounds for the number of spanning trees of a graph with given matching number.     

On maximally distant spanning trees of a graph

A set ofk spanning trees of a graphG is calledmaximally distant if their union contains the maximum number of edges ofG. We present a necessary and sufficient condition for a set of spanning trees to be maximally distant. We also give an efficient algorithm which actually findsk maximally distant spanning trees in a given graph.     

Cyclic bundle Hamiltonicity

Cyclic bundle Hamiltonicity cbH(G) of a graph G is the minimal n for which there is an automorphism α of G such that the graph bundle C _n □^α G is Hamiltonian. We define an invariant I that is related to the maximal vertex degree of spanning trees suitably involving the symmetries of G and prove cbH(G)≤I≤cbH(G)+1 for any non-trivial connected graph G.     

Maximizing the number of spanning trees on the (p,p+2) graphs

This paper considers the problem of maximizing the number of spanning trees. A newly established result is the formula and the graph topology for the maximum number of spanning trees among the class of (p, p+2) graph.     

Stability analysis of constrained MPC with CLF applied to discrete-time nonlinear system

The problem of counting the number of spanning trees is an old topic in graph theory with important applications to reliable network design. Usually, it is desirable to put forward a formula of the number of spanning trees for various graphs, which is not only interesting in its own right but also in practice. Since some large graphs can be composed of some existing smaller graphs by using the product of graphs, the number of spanning trees of such large graph is also closely related to that of the corresponding smaller ones. In this article, we establish a formula for the number of spanning trees in the lexicographic product of two graphs, in which one graph is an arbitrary graph G and the other is a complete multipartite graph. The results extend some of the previous work, which is closely related to the number of vertices and Lapalacian eigenvalues of smaller graphs only.     

Extremal values on the harmonic number of trees

Let G=(V(G), E(G)) be a simple connected graph. The harmonic number of G, denoted by H(G), is defined as the sum of the weights 2/(d(u)+d(v)) of all edges uv of G, where d(u) denotes the degree of a vertex u in G. In this paper, some extremal problems on the harmonic number of trees are studied. The extremal values on the harmonic number of trees with given graphic parameters, such as pendant number, matching number, domination number and diameter, are determined. The corresponding extremal graphs are characterized, respectively.     

Minimizing the makespan in a single machine scheduling problem with a time-based learning effect

Both the building cost and the multiple-source routing cost are important considerations in construction of a network system. A spanning tree with minimum building cost among all spanning trees is called a minimum spanning tree (MST), and a spanning tree with minimum k-source routing cost among all spanning trees is called a k-source minimum routing cost spanning tree (k-MRCT). This paper proposes an algorithm to construct a spanning tree T for a metric graph G with a source vertex set S such that the building cost of T is at most 1+2/(α−1) times of that of an MST of G, and the k-source routing cost of T is at most α(1+2(k−1)(n−2)/k(n+k−2)) times of that of a k-MRCT of G with respect to S, where α>1, k=|S| and n is the number of vertices of G.     

Approximating Biconnectivity in Parallel

Consider the following NP-hard problems: Given a graph G , find minimum 2-edge connected and 2-vertex connected subgraphs spanning all vertices of G . Over the past few years, exciting sequential algorithms for approximating such minimum subgraphs have been produced [6],[10]. The approximation factors are improved from 2 to 3/2 for both of the problems. Yet the techniques involved are all based on augmenting depth-first-search trees and no similar progress has been carried to the parallel context. This paper presents NC algorithms to achieve approximation factors of 3/2 + ε for these two problems without computing depth-first-search trees. Received June 21, 1995; revised December 24, 1996, and June 2, 1997.     

An Algorithm for Enumerating All Spanning Trees of a Directed Graph

We present an O(NV + V ³ ) time algorithm for enumerating all spanning trees of a directed graph. This improves the previous best known bound of O(NE + V+E) [1] when V ² =o(N) , which will be true for most graphs. Here, N refers to the number of spanning trees of a graph having V vertices and E edges. The algorithm is based on the technique of obtaining one spanning tree from another by a series of edge swaps. This result complements the result in the companion paper [3] which enumerates all spanning trees in an undirected graph in O(N+V+E) time. Received September 11, 1997; revised March 6, 1998.     

Approximating the Maximum Internal Spanning Tree problem

Given an undirected connected graph G$G$ we consider the problem of finding a spanning tree of G$G$ which has a maximum number of internal (non-leaf) vertices among all spanning trees of G$G$. This problem, called Maximum Internal Spanning Tree problem, is clearly NP-hard since it is a generalization of the Hamiltonian Path problem. From the optimization point of view the Maximum Internal Spanning Tree problem is equivalent to the Minimum Leaf Spanning Tree problem. However, the two problems have different approximability properties. Lu and Ravi proved that the latter has no constant factor approximation–unless P = NP–, while Salamon and Wiener gave a linear-time 2-approximation algorithm for the Maximum Internal Spanning Tree problem.     

Locally connected spanning trees in cographs, complements of bipartite graphs and doubly chordal graphs

A spanning tree T of a graph G=(V,E) is called a locally connected spanning tree if the set of all neighbors of v in T induces a connected subgraph of G for all v∈V. The problem of recognizing whether a graph admits a locally connected spanning tree is known to be NP-complete even when the input graphs are restricted to chordal graphs. In this paper, we propose linear time algorithms for finding locally connected spanning trees in cographs, complements of bipartite graphs and doubly chordal graphs, respectively.     

Listing all the minimum spanning trees in an undirected graph

Efficient polynomial time algorithms are well known for the minimum spanning tree problem. However, given an undirected graph with integer edge weights, minimum spanning trees may not be unique. In this article, we present an algorithm that lists all the minimum spanning trees included in the graph. The computational complexity of the algorithm is O(N(mn+n ² log n)) in time and O(m) in space, where n, m and N stand for the number of nodes, edges and minimum spanning trees, respectively. Next, we explore some properties of cut-sets, and based on these we construct an improved algorithm, which runs in O(N m log n) time and O(m) space. These algorithms are implemented in C language, and some numerical experiments are conducted for planar as well as complete graphs with random edge weights.     

Spanning Trees and the Complexity of Flood-Filling Games

We consider problems related to the combinatorial game (Free-) Flood-It, in which players aim to make a coloured graph monochromatic with the minimum possible number of flooding operations. We show that the minimum number of moves required to flood any given graph G is equal to the minimum, taken over all spanning trees T of G, of the number of moves required to flood T. This result is then applied to give two polynomial-time algorithms for flood-filling problems. Firstly, we can compute in polynomial time the minimum number of moves required to flood a graph with only a polynomial number of connected subgraphs. Secondly, given any coloured connected graph and a subset of the vertices of bounded size, the number of moves required to connect this subset can be computed in polynomial time.     

Maintaining Spanning Trees of Small Diameter

Given a graph G with m edges and n nodes, a spanning tree T of G , and an edge e that is being deleted from or inserted into G , we give efficient O(n) algorithms to compute a possible swap for e that minimizes the diameter of the new spanning tree. This problem arises in high-speed networks, particularly in optical networks. Received January 1995; revised February 1997.     

The rupture degree of trees

For the complete graph K _n , its rupture degree is defined as 1?n; and for a noncomplete connected graph G, its rupture degree is defined by r(G)=max{ω(G ? X)?|X|?m(G ? X):X ? V(G), ω(G ? X) > 1 }, where ω(G ? X) is the number of components of G ? X and m(G ? X) is the order of a largest component of G ? X. It is shown that this parameter can be well used to measure the vulnerability of networks. Li and Li proved in 2004 that computing the rupture degree for a general graph is NP-complete. In this paper, we give a recursive algorithm for computing the rupture degree of trees, and determine the maximum and minimum rupture degree of trees with given order and maximum degree.     

On the edge-tenacity of the middle graph of a graph

We consider the problem of efficiently breaking a graph into small components by removing edges. One measure of how easily this can be done is the edge-tenacity. Given a set of edges of G, the score of S is defined as sc(S)=[| S|+τ (G?S)]/[w(G?S)]. Formally, the edge-tenacity of a graph G is defined as T′(G)=min sc(S), where the minimum is taken over all edge-sets S of G. A subset S of E(G) is said to be a T′-set of G if T′(G)=sc(S). Note that if G is disconnected, the set S may be empty. For any graph G, τ(G?S) is the number of vertices in the largest component of G?S and w(G?S) is the number of components of G?S. The middle graph M(G) of a graph G is the graph obtained from G by inserting a new vertex into every edge of G and by joining by edges those pairs of these new vertices which lie on adjacent edges of G. In this paper, we give the edge-tenacity of the middle graph of specific families of graphs and its relationships with other parameters.     

An adaptive heuristic to the bounded-diameter minimum spanning tree problem

Given a graph G and a bound d?≥?2, the bounded-diameter minimum spanning tree problem seeks a spanning tree on G of minimum weight subject to the constraint that its diameter does not exceed d. This problem is NP-hard; several heuristics have been proposed to find near-optimal solutions to it in reasonable times. A decentralized learning automata-based algorithm creates spanning trees that honor the diameter constraint. The algorithm rewards a tree if it has the smallest weight found so far and penalizes it otherwise. As the algorithm proceeds, the choice probability of the tree converges to one; and the algorithm halts when this probability exceeds a predefined value. Experiments confirm the superiority of the algorithm over other heuristics in terms of both speed and solution quality.     

The super spanning connectivity and super spanning laceability of the enhanced hypercubes

A k -container C(u,v) of a graph G is a set of k disjoint paths between u and v. A k-container C(u,v) of G is a k ^* -container if it contains all vertices of G. A graph G is k ^* -connected if there exists a k ^*-container between any two distinct vertices of G. Therefore, a graph is 1^*-connected (respectively, 2^*-connected) if and only if it is Hamiltonian connected (respectively, Hamiltonian). A graph G is super spanning connected if there exists a k ^*-container between any two distinct vertices of G for every k with 1≤k≤κ(G) where κ(G) is the connectivity of G. A bipartite graph G is k ^* -laceable if there exists a k ^*-container between any two vertices from different partite set of G. A bipartite graph G is super spanning laceable if there exists a k ^*-container between any two vertices from different partite set of G for every k with 1≤k≤κ(G). In this paper, we prove that the enhanced hypercube Q _n,m is super spanning laceable if m is an odd integer and super spanning connected if otherwise.

The complexity for partitioning graphs by monochromatic trees,cycles and paths

Let G be an edge-coloured graph. We show in this paper that it is NP-hard to find the minimum number of vertex disjoint monochromatic trees which cover the vertices of the graph G. We also show that there is no constant factor approximation algorithm for the problem unless P?=?NP. The same results hold for the problem of finding the minimum number of vertex disjoint monochromatic cycles (paths, respectively) which cover the vertices of the graph.     

A Flexible Algorithm for Generating All the Spanning Trees in Undirected Graphs

In this paper we propose an algorithm for generating all the spanning trees in undirected graphs. The algorithm requires O (n+m+ τ n) time where the given graph has n vertices, m edges, and τ spanning trees. For outputting all the spanning trees explicitly, this time complexity is optimal. Our algorithm follows a special rooted tree structure on the skeleton graph of the spanning tree polytope. The rule by which the rooted tree structure is traversed is irrelevant to the time complexity. In this sense, our algorithm is flexible. If we employ the depth-first search rule, we can save the memory requirement to O (n+m). A breadth-first implementation requires as much as O (m+ τ n) space, but when a parallel computer is available, this might have an advantage. When a given graph is weighted, the best-first search rule provides a ranking algorithm for the minimum spanning tree problem. The ranking algorithm requires O (n+ m + τ n) time and O (m+ τ n) space when we have a minimum spanning tree. Received January 21, 1995; revised February 19, 1996.