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.     

A dual ascent approach for steiner tree problems on a directed graph

The Steiner tree problem on a directed graph (STDG) is to find a directed subtree that connects a root node to every node in a designated node setV. We give a dual ascent procedure for obtaining lower bounds to the optimal solution value. The ascent information is also used in a heuristic procedure for obtaining feasible solutions to the STDG. Computational results indicate that the two procedures are very effective in solving a class of STDG's containing up to 60 nodes and 240 directed/120 undirected arcs. The directed spanning tree and uncapacitated plant location problems are special cases of the STDG. Using these relationships, we show that our ascent procedure can be viewed as a generalization ofboth the Chu-Liu-Edmonds directed spanning tree algorithm and the Bilde-Krarup-Erlenkotter ascent algorithm for the plant location problem. The former comparison yields a dual ascent interpretation of the steps of the directed spanning tree algorithm.     

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 .     

On the spanning fan-connectivity of graphs

Let G be a graph. The connectivity of G, κ(G), is the maximum integer k such that there exists a k-container between any two different vertices. A k-container of G between u and v, C_k(u,v), is a set of k-internally-disjoint paths between u and v. A spanning container is a container that spans V(G). A graph G is k^∗-connected if there exists a spanning k-container between any two different vertices. The spanning connectivity of G, κ^∗(G), is the maximum integer k such that G is w^∗-connected for 1≤w≤k if G is 1^∗-connected.Let x be a vertex in G and let U={y₁,y₂,…,y_k} be a subset of V(G) where x is not in U. A spanningk−(x,U)-fan, F_k(x,U), is a set of internally-disjoint paths {P₁,P₂,…,P_k} such that P_i is a path connecting x to y_i for 1≤i≤k and . A graph G is k^∗-fan-connected (or -connected) if there exists a spanning F_k(x,U)-fan for every choice of x and U with |U|=k and x∉U. The spanning fan-connectivity of a graph G, , is defined as the largest integer k such that G is -connected for 1≤w≤k if G is -connected.In this paper, some relationship between κ(G), κ^∗(G), and are discussed. Moreover, some sufficient conditions for a graph to be -connected are presented. Furthermore, we introduce the concept of a spanning pipeline-connectivity and discuss some sufficient conditions for a graph to be k^∗-pipeline-connected.     

Factorizations of complete graphs into caterpillars of diameter 5

We examine factorizations of complete graphs K_2n into caterpillars of diameter 5. First we present a construction generalizing some previously known methods. Then we use the new method along with some previous partial results to give a complete characterization of caterpillars of diameter 5, which factorize the complete graph K_2n.     

On spanning tree congestion

We prove that every connected graph G of order n has a spanning tree T such that for every edge e of T the edge cut defined in G by the vertex sets of the two components of T−e contains at most edges. This result solves a problem posed by Ostrovskii (M.I. Ostrovskii, Minimal congestion trees, Discrete Math. 285 (2004) 219-226).     

Unbalanced bipartite factorizations of complete bipartite graphs

We construct a new infinite family of factorizations of complete bipartite graphs by factors all of whose components are copies of a (fixed) complete bipartite graph K_p,q. There are simple necessary conditions for such factorizations to exist. The family constructed here demonstrates sufficiency in many new cases. In particular, the conditions are always sufficient when q=p+1.     

A Flow Formulation for the Optimum Communication Spanning Tree

In this paper we address the Optimum Communication Spanning Tree Problem. We present a formulation that uses three index variables and we propose several families of inequalities, which can be used to reinforce the formulation. Preliminary computational experiments are very promising.     

Decomposition of bipartite graphs into special subgraphs

Let F and G be two graphs and let H be a subgraph of G. A decomposition of G into subgraphs F₁,F₂,…,F_m is called an F-factorization of G orthogonal to H if F_i≅F and |E(F_i∩H)|=1 for each i=1,2,…,m. Gyárfás and Schelp conjectured that the complete bipartite graph K_4k,4k has a C₄-factorization orthogonal to H provided that H is a k-factor of K_4k,4k. In this paper, we show that (1) the conjecture is true when H satisfies some structural conditions; (2) for any two positive integers r?k, K_kr²,kr² has a K_r,r-factorization orthogonal to H if H is a k-factor of K_kr²,kr²; (3) K_2d²,2d² has a C₄-factorization such that each edge of H belongs to a different C₄ if H is a subgraph of K_2d²,2d² with maximum degree Δ(H)?d.     

An algorithm for the enumeration of spanning trees

Enumeration of spanning trees of an undirected graph is one of the graph problems that has received much attention in the literature. In this paper a new enumeration algorithm based on the idea of contractions of the graph is presented. The worst-case time complexity of the algorithm isO(n+m+nt) wheren is the number of vertices,m the number of edges, andt the number of spanning trees in the graph. The worst-case space complexity of the algorithm isO(n ²). Computational analysis indicates that the algorithm requires less computation time than any other of the previously best-known algorithms.     

Total edge irregularity strength of complete graphs and complete bipartite graphs

A total edge irregular k-labelling ν of a graph G is a labelling of the vertices and edges of G with labels from the set {1,…,k} in such a way that for any two different edges e and f their weights φ(f) and φ(e) are distinct. Here, the weight of an edge g=uv is φ(g)=ν(g)+ν(u)+ν(v), i. e. the sum of the label of g and the labels of vertices u and v. The minimum k for which the graph G has an edge irregular total k-labelling is called the total edge irregularity strength of G.We have determined the exact value of the total edge irregularity strength of complete graphs and complete bipartite graphs.     

On the Decomposition of Graphs into Complete Bipartite Graphs

In a complete bipartite decomposition π of a graph, we consider the number ϑ(v;π) of complete bipartite subgraphs incident with a vertex v. Let ϑ(G)= ϑ(v;π). In this paper the exact values of ϑ(G) for complete graphs and hypercubes and a sharp upper bound on ϑ(G) for planar graphs are provided, respectively. An open problem proposed by P.C. Fishburn and P.L. Hammer is solved as well.     

Minimum cost spanning tree games

We consider the problem of cost allocation among users of a minimum cost spanning tree network. It is formulated as a cooperative game in characteristic function form, referred to as a minimum cost spanning tree (m.c.s.t.) game. We show that the core of a m.c.s.t. game is never empty. In fact, a point in the core can be read directly from any minimum cost spanning tree graph associated with the problem. For m.c.s.t. games with efficient coalition structures we define and construct m.c.s.t. games on the components of the structure. We show that the core and the nucleolus of the original game are the cartesian products of the cores and the nucleoli, respectively, of the induced games on the components of the efficient coalition structure.This paper is a revision of [4].     

Chordal bipartite completion of colored graphs

Golumbic, Kaplan, and Shamir [Graph sandwich problems, J. Algorithms 19 (1995) 449-473], in their paper on graph sandwich problems published in 1995, left the status of the sandwich problems for strongly chordal graphs and chordal bipartite graphs open. It was recently shown [C.M.H. de Figueiredo, L. Faria, S. Klein, R. Sritharan, On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs, Theoret. Comput. Sci., accepted for publication] that the sandwich problem for strongly chordal graphs is NP-complete. We show that given graph G with a proper vertex coloring c, determining whether there is a supergraph of G that is chordal bipartite and also is properly colored by c is NP-complete. This implies that the sandwich problem for chordal bipartite graphs is also NP-complete.     

On the use of graphs in discrete tomography

In this tutorial paper, we consider the basic image reconstruction problem which stems from discrete tomography. We derive a graph theoretical model and we explore some variations and extensions of this model. This allows us to establish connections with scheduling and timetabling applications. The complexity status of these problems is studied and we exhibit some polynomially solvable cases. We show how various classical techniques of operations research like matching, 2-SAT, network flows are applied to derive some of these results.      

On the core and nucleolus of minimum cost spanning tree games

We develop two efficient procedures for generating cost allocation vectors in the core of a minimum cost spanning tree (m.c.s.t.) game. The first procedure requires O(n ²) elementary operations to obtain each additional point in the core, wheren is the number of users. The efficiency of the second procedure, which is a natural strengthening of the first procedure, stems from the special structure of minimum excess coalitions in the core of an m.c.s.t. game. This special structure is later used (i) to ease the computational difficulty in computing the nucleolus of an m.c.s.t. game, and (ii) to provide a geometric characterization for the nucleolus of an m.c.s.t. game. This geometric characterization implies that in an m.c.s.t. game the nucleolus is the unique point in the intersection of the core and the kernel. We further develop an efficient procedure for generating fair cost allocations which, in some instances, coincide with the nucleolus. Finally, we show that by employing Sterns' transfer scheme we can generate a sequence of cost vectors which converges to the nucleolus. Part of this research was done while the author was visiting the Department of Operations Research at Stanford University. This research was partially supported by Natural Sciences and Engineering Research Council Canada Grant A-4181.     

On the number of rainbow spanning trees in edge-colored complete graphs

A spanning tree of a properly edge-colored complete graph, $K_n$, is rainbow provided that each of its edges receives a distinct color. In 1996, Brualdi and Hollingsworth conjectured that if $K_{2m}$ is properly $(2m?1)$-edge-colored, then the edges of $K_{2m}$ can be partitioned into $m$ rainbow spanning trees except when $m=2$. By means of an explicit, constructive approach, in this paper we construct $?\sqrt{6m+9}∕3?$ mutually edge-disjoint rainbow spanning trees for any positive value of $m$. Not only are the rainbow trees produced, but also some structure of each rainbow spanning tree is determined in the process. This improves upon best constructive result to date in the literature which produces exactly three rainbow trees.     

A note on the domination dot-critical graphs

A graph G is dot-critical if contracting any edge decreases the domination number. Nader Jafari Rad (2009) [3] posed the problem: Is it true that a connected k-dot-critical graph G with G^′=0? is 2-connected? In this note, we give a family of 1-connected 2k-dot-critical graph with G^′=0? and show that this problem has a negative answer.     

Multicolored forests in complete bipartite graphs

If the edges of a graph G are colored using k colors, we consider the color distribution for this coloring a=(a₁,a₂,…,a_k), in which a_i denotes the number of edges of color i for i=1,2,…,k. We find inequalities and majorization conditions on color distributions of the complete bipartite graph K_n,n which guarantee the existence of multicolored subgraphs: in particular, multicolored forests and trees. We end with a conjecture on partitions of K_n,n into multicolored trees.