Minimum congestion spanning trees in bipartite and random graphs

The first problem considered in this article reads: is it possible to find upper estimates for the spanning tree congestion in bipartite graphs, which are better than those for general graphs? It is proved that there exists a bipartite version of the known graph with spanning tree congestion of order n 3 2 , where n is the number of vertices. The second problem is to estimate spanning tree congestion of random graphs. It is proved that the standard model of random graphs cannot be used to find graphs whose spanning tree congestion has order greater than n 3 2 .     

Minimum congestion spanning trees in planar graphs

The main purpose of the paper is to develop an approach to the evaluation or the estimation of the spanning tree congestion of planar graphs. This approach is used to evaluate the spanning tree congestion of triangular grids.     

On spanning tree congestion of graphs

Let G be a connected graph and T be a spanning tree of G. For e∈E(T), the congestion of e is the number of edges in G connecting two components of T−e. The edge congestion ofGinT is the maximum congestion over all edges in T. The spanning tree congestion ofG is the minimum congestion of G in its spanning trees. In this paper, we show the spanning tree congestion for the complete k-partite graphs and the two-dimensional tori. We also address lower bounds of spanning tree congestion for the multi-dimensional grids and the hypercubes.     

Efficient spanning trees

The definition of a shortest spanning tree of a graph is generalized to that of an efficient spanning tree for graphs with vector weights, where the notion of optimality is of the Pareto type. An algorighm for obtaining all efficient spanning trees is presented.     

一些图的生成树数

图 G 的生成树是它的连通子图(子树).本文精确地计算出了一些图的生成树的数目, 例如双心轮图、双柄扇图等等.     

Tree network design avoiding congestion

We introduce in this paper an optimal method for tree network design avoiding congestion. We see this problem arising in telecommunication and transportation networks as a flow extension of the Steiner problem in directed graphs, thus including as a particular case any alternative approach based on the minimum spanning tree problem. Our multi-commodity formulation is able to cope with the design of centralized computer networks, modern multi-cast multi-party or hub-based transportation trees. The objective in such cases is the minimization of the sum of the fixed (structural) and variable (operational) costs of all the arcs composing an arborescence that links the origin node (switching center, server, station) to every demand node (multi-cast participants, users in general). The non-linear multi-commodity flow model is solved by a generalized Benders decomposition approach.     

Minimum edge ranking spanning trees of split graphs

Given a graph G, the minimum edge ranking spanning tree problem (MERST) is to find a spanning tree of G whose edge ranking is minimum. However, this problem is known to be NP-hard for general graphs. In this paper, we show that the problem MERST has a polynomial time algorithm for split graphs, which have useful applications in practice. The result is also significant in the sense that this is a first non-trivial graph class for which the problem MERST is found to be polynomially solvable. We also show that the problem MERST for threshold graphs can be solved in linear time, where threshold graphs are known to be split.     

Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs

A locally connected spanning tree of a graph G is a spanning tree T of G such that the set of all neighbors of v in T induces a connected subgraph of G for every v∈V(G). The purpose of this paper is to give linear-time algorithms for finding locally connected spanning trees on strongly chordal graphs and proper circular-arc graphs, respectively.     

Spanning trees of extended graphs

A generalization of the Prüfer coding of trees is given providing a natural correspondence between the set of codes of spanning trees of a graph and the set of codes of spanning trees of theextension of the graph. This correspondence prompts us to introduce and to investigate a notion ofthe spanning tree volume of a graph and provides a simple relation between the volumes of a graph and its extension (and in particular a simple relation between the spanning tree numbers of a graph and its uniform extension). These results can be used to obtain simple purely combinatorial proofs of many previous results obtained by the Matrix-tree theorem on the number of spanning trees of a graph. The results also make it possible to construct graphs with the maximal number of spanning trees in some classes of graphs.     

几类图的支撑树的个数

推广了计算图的支撑树个数的递归公式,解释了组合计数原理的用法.用组合技巧和常系数线性递归序列的解法,对n步梯、n-棱柱、Mobius n-棱柱及有关图,找到了计算它们的支撑树的个数的若干公式.     

On homeomorphically irreducible spanning trees in cubic graphs

A spanning tree without a vertex of degree two is called a HIST, which is an abbreviation for homeomorphically irreducible spanning tree. We provide a necessary condition for the existence of a HIST in a cubic graph. As one consequence, we answer affirmatively an open question on HISTs by Albertson, Berman, Hutchinson, and Thomassen. We also show several results on the existence of HISTs in plane and toroidal cubic graphs.     

Edge-Ends in Countable Graphs

We introduce the notion of an edge-end and characterize those countable graphs which have edge-end-faithful spanning trees. We also prove that for a natural class of graphs, there always exists a tree which is faithful on the undominated ends and rayless over the dominated does.     

Transchordal graphs

Transchordal graphs generalize chordal graphs in terms of those aspects that seem particularly relevant to applications. In particular, transchordal graphs are defined as intersection graphs (only with circuit bases somewhat taking the place of spanning trees), they support a greedy construction that extends the notion of clique tree, and they have a combinatorial characterization that resembles two previous characterizations of chordal graphs.     

On the spanning tree packing number of a graph: a survey

The spanning tree packing number or STP number of a graph G is the maximum number of edge-disjoint spanning trees contained in G. We use an observation of Paul Catlin to investigate the STP numbers of several families of graphs including quasi-random graphs, regular graphs, complete bipartite graphs, cartesian products and the hypercubes.     

Uniform election in trees and polyominoids

Election is a classical paradigm in distributed algorithms. This paper aims to design and analyze a distributed algorithm choosing a node in a graph which models a network. In case the graph is a tree, a simple schema of algorithm acts as follows: it removes leaves until the graph is reduced to a single vertex; the elected one. In Métivier et al. (2003) [7], the authors studied a randomized variant of this schema which gives the same probability of being elected to each node of the tree. They conjectured that the expected election duration of this algorithm is O(ln(n)) where n denotes the size of the tree, and asked whether it is possible to use the same algorithm to obtain a fair election in other classes of graphs.In this paper, we prove their conjecture. We then introduce a new structure called polyominoid graphs. We show how a spanning tree for these graphs can be computed locally so that our algorithm, applied to this spanning tree, gives a uniform election algorithm on polyominoids.     

Graphs with homeomorphically irreducible spanning trees

It is an NP-complete problem to decide whether a graph contains a spanning tree with no vertex of degree 2. We show that these homeomorphically irreducible spanning trees are contained in all graphs with minimum degree at least c√n and in triangulations of the plane. They are nearly present in all graphs of diameter 2. They do not necessarily occur in r-regular or r-connected graphs.     

Weighted enumeration of spanning subgraphs in locally tree‐like graphs

Using the theory of negative association for measures and the notion of unimodularity for random weak limits of sparse graphs, we establish the validity of the cavity method for counting spanning subgraphs subject to local constraints in asymptotically tree‐like graphs. Specifically, the normalized logarithm of the associated partition function (free energy) is shown to converge along any sequence of graphs whose random weak limit is a tree, and the limit is directly expressed in terms of the unique solution to a limiting cavity equation. On a Galton–Watson tree, the latter simplifies into a recursive distributional equation which can be solved explicitly. As an illustration, we provide a new asymptotic formula for the maximum size of a b‐matching in the Erd?s–Rényi random graph with fixed average degree and diverging size, for any $b\in\mathbb{N}Using the theory of negative association for measures and the notion of unimodularity for random weak limits of sparse graphs, we establish the validity of the cavity method for counting spanning subgraphs subject to local constraints in asymptotically tree‐like graphs. Specifically, the normalized logarithm of the associated partition function (free energy) is shown to converge along any sequence of graphs whose random weak limit is a tree, and the limit is directly expressed in terms of the unique solution to a limiting cavity equation. On a Galton–Watson tree, the latter simplifies into a recursive distributional equation which can be solved explicitly. As an illustration, we provide a new asymptotic formula for the maximum size of a b‐matching in the Erd?s–Rényi random graph with fixed average degree and diverging size, for any $b\in\mathbb{N}$. To the best of our knowledge, this is the first time that correlation inequalities and unimodularity are combined together to yield a general proof of uniqueness of Gibbs measures on infinite trees. We believe that a similar argument is applicable to other Gibbs measures than those over spanning subgraphs considered here. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

An algorithm to generate all spanning trees with flow

Spanning tree enumeration in undirected graphs is an important issue and task in many problems encountered in computer network and circuit analysis. This paper discusses the spanning tree with flow for the case that there are flow requirements between each node pair. An algorithm based on minimal paths (MPs) is proposed to generate all spanning trees without flow. The proposed algorithm is a structured approach, which splits the system into structural MPs first, and also all steps in it are easy to follow.     

A Generalization of Heterochromatic Graphs and f-Chromatic Spanning Forests

In 2006, Suzuki, and Akbari and Alipour independently presented a necessary and sufficient condition for edge-colored graphs to have a heterochromatic spanning tree, where a heterochromatic spanning tree is a spanning tree whose edges have distinct colors. In this paper, we propose f-chromatic graphs as a generalization of heterochromatic graphs. An edge-colored graph is f-chromatic if each color c appears on at most f(c) edges. We also present a necessary and sufficient condition for edge-colored graphs to have an f-chromatic spanning forest with exactly m components. Moreover, using this criterion, we show that a g-chromatic graph G of order n with ${|E(G)| > \binom{n-m}{2}}$ has an f-chromatic spanning forest with exactly m (1 ≤ m ≤ n ? 1) components if ${g(c) \le \frac{|E(G)|}{n-m}f(c)}$ for any color c.     

Decomposing planar cubic graphs

The 3‐Decomposition Conjecture states that every connected cubic graph can be decomposed into a spanning tree, a 2‐regular subgraph and a matching. We show that this conjecture holds for the class of connected plane cubic graphs.