A longstanding problem in spectral graph theory asks for graphs with maximum number of spanning trees among all connected simple graphs with a prescribed number of vertices and edges. Such graphs are called t -optimal graphs. Petingi and Rodríguez [Discrete Math. 244 (2002), 351–373] achieved in finding infinitely many t -optimal graphs. Basically, they reduced the problem of finding t -optimal graphs to the determination of almost-regular graphs with minimum number of induced 3-paths. In this work we revisit the construction of t -optimal graphs given by Petingi and Rodríguez. Then, we generalize the previous construction using the key concept of trace-minimal graph introduced by Ábrego et al. [Linear Algebra Appl. 412 (2006) 161–221]. Finally, as a consequence, we construct infinitely many new t -optimal regular graphs.

We propose a polynomial-time algorithm for detecting and deleting classes of network edges which are irrelevant in the evaluation of the Source-to-terminal Diameter Constrained Network reliability parameter. As evaluating this parameter is known to be an NP-hard problem, the proposed procedure may lead to important computational gains when combined with an exact method to calculate the reliability. For illustration, we integrate this algorithm within an exact recursive factorization approach based upon Moskowitz's edge decomposition. Experiments conducted on different real-world topologies confirmed a substantial computational gain, except when highly-dense graphs were tested.

Abstract Let G = (V,E) be an undirected graph with a distinguished set of terminal vertices K ⊆ V, |K| ≥ 2. A K‐Steiner tree T of G is a tree containing the terminal vertex‐set K, where any vertex of degree one in T must belong to K. The Steiner Tree Packing problem (STPP for short) is the problem of finding the maximum number of edge‐disjoint K‐Steiner trees, tK(G), contained in G. Specifically we are interested in finding a lower bound on tK(G) with respect to the K‐edge‐connectivity, denoted as λK(G). In 2003, Kriesell conjectured that any graph G with terminal vertex‐set K has at least ⌊λK(G)/2⌋ edge‐disjoint K‐Steiner trees. In this article, we show that this conjecture can be answered affirmatively if the edges of G can be partitioned into K‐Steiner trees. This result yields bounds for the problem of packing K‐Steiner trees with certain intersection properties in a graph. In addition we show that for any graph G with terminal vertex‐set K, tK(G) ≥ ⌊λK(G)/2⌋ − |V − K|/2 − 1. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009

The all-terminal reliability (ATR) of an undirected graph G, denoted as R (G, q), is the probability that, when the edges are assigned independent but equal failure probabilities q, 0 < q < 1 (nodes are perfect), the surviving edges induce a spanning connected subgraph of G. A graph G with n nodes and e edges is said to be uniformly least reliable if and only if R(G, q) ≤ R(G′ q) among all connected G′ with the same number of nodes and edges as G and for all failure probabilities 0 < q < 1. In this paper, we characterize uniformly least reliable graphs for e ≥ (n - 1)(n - 2)/2 + 1. We note that, unlike general graphs, for which computing the ATR has been shown to be NP-hard, the ATR of these graphs can be computed in polynomial time, providing an efficient lower bound for the general problem. © 1996 John Wiley & Sons, Inc.