On encodings of spanning trees

Deo and Micikevicius recently gave a new bijection for spanning trees of complete bipartite graphs. In this paper we devise a generalization of Deo and Micikevicius's method, which is also a modification of Olah's method for encoding the spanning trees of any complete multipartite graph K(n₁,…,n_r). We also give a bijection between the spanning trees of a planar graph and those of any of its planar duals. Finally we discuss the possibility of bijections for spanning trees of DeBriujn graphs, cubes, and regular graphs such as the Petersen graph that have integer eigenvalues.     

The number of spanning trees of plane graphs with reflective symmetry

A plane graph is called symmetric if it is invariant under the reflection across some straight line (called symmetry axis). Let G be a symmetric plane graph. We prove that if there is no edge in G intersected by its symmetry axis then the number of spanning trees of G can be expressed in terms of the product of the number of spanning trees of two smaller graphs, each of which has about half the number of vertices of G.     

Bounds on cost effective domination numbers

A vertex υ in a set S is said to be cost effective if it is adjacent to at least as many vertices in V\S as it is in S and is very cost effective if it is adjacent to more vertices in V\S than to vertices in S. A dominating set S is (very) cost effective if every vertex in S is (very) cost effective. The minimum cardinality of a (very) cost effective dominating set of G is the (very) cost effective domination number of G. Our main results include a quadratic upper bound on the very cost effective domination number of a graph in terms of its domination number. The proof of this result gives a linear upper bound for hereditarily sparse graphs which include trees. We show that no such linear bound exists for graphs in general, even when restricted to bipartite graphs. Further, we characterize the extremal trees attaining the bound. Noting that the very cost effective domination number is bounded below by the domination number, we show that every value of the very cost effective domination number between these lower and upper bounds for trees is realizable. Similar results are given for the cost effective domination number.     

Minimum cycle bases of graphs on surfaces

In this paper we study the cycle base structures of embedded graphs on surfaces. We first give a sufficient and necessary condition for a set of facial cycles to be contained in a minimum cycle base (or MCB in short) and then set up a 1-1 correspondence between the set of MCBs and the set of collections of nonseparating cycles which are in general positions on surfaces and are of shortest total length. This provides a way to enumerate MCBs in a graph via nonseparating cycles. In particular, some known results such as P.F. Stadler's work on Halin graphs [Minimum cycle bases of Halin graphs, J. Graph Theory 43 (2003) 150-155] and Leydold and Stadler's results on outer-planar graphs [Minimum cycle bases of outerplanar graphs, Electronic J. Combin. 5(16) (1998) 14] are concluded. As applications, the number of MCBs in some types of graphs embedded in lower surfaces (with arbitrarily high genera) is found. Finally, we present an interpolation theorem for the number of one-sided cycles contained in MCB of an embedded graph.     

Maximum andk-th maximal spanning trees of a weighted graph

LetA be a maximum spanning tree andP be an arbitrary spanning tree of a connected weighted graphG. Then we prove that there exists a bijectionψ fromA/P intoP/A such that for any edgea∈A/P, (P/ψ(a)) ∪a is a spanning tree ofG whose weight is greater than or equal to that ofP. We apply this theorem to some problems concerning spanning trees of a weighted graph.     

Hajós Theorem For Colorings Of Edge-Weighted Graphs

Hajós theorem states that every graph with chromatic number at least k can be obtained from the complete graph K _k by a sequence of simple operations such that every intermediate graph also has chromatic number at least k. Here, Hajós theorem is extended in three slightly different ways to colorings and circular colorings of edge-weighted graphs. These extensions shed some new light on the Hajós theorem and show that colorings of edge-weighted graphs are most natural extension of usual graph colorings.* Supported in part by the Ministry of Education, Science and Sport of Slovenia, Research Program P0–0507–0101.     

The splittance of a graph

The splittance of an arbitrary graph is the minimum number of edges to be added or removed in order to produce a split graph (i.e. a graph whose vertex set can be partitioned into a clique and an independent set). The splittance is seen to depend only on the degree sequence of the graph, and an explicit formula for it is derived. This result allows to give a simple characterization of the degree sequences of split graphs. Worst cases for the splittance are determined for some classes of graphs (the class of all graphs, of all trees and of all planar graphs).     

On the spanning trees of weighted graphs

Given a weighted graph, letW ₁,W ₂,W ₃,... denote the increasing sequence of all possible distinct spanning tree weights. Settling a conjecture due to Kano, we prove that every spanning tree of weightW ₁ is at mostk–1 edge swaps away from some spanning tree of weightW _k . Three other conjectures posed by Kano are proven for two special classes of graphs. Finally, we consider the algorithmic complexity of generating a spanning tree of weightW _k .This work was supported in part by a grant from the AT&T foundation and NSF grant DCR-8351757.Primarily supported by a 1967 Science and Engineering Scholarship from the Natural Sciences and Engineering Research Council of Canada.     

Colorful Isomorphic Spanning Trees in Complete Graphs

Can a complete graph on an even number n (> 4) of vertices be properly edge-colored with n − 1 colors in such a way that the edges can be partitioned into edge-disjoint colorful isomorphic spanning trees? A spanning treee is colorful if all n − 1 colors occur among its edges. It is proved that this is possible to accomplish whenever n is a power of two.Received July 24, 2001     

The spanning trees forced by the path and the star

A set S of trees of order n forces a tree T if every graph having each tree in S as a spanning tree must also have T as a spanning tree. A spanning tree forcing set for order n that forces every tree of order n. A spanning-tree forcing set S is a test set for panarboreal graphs, since a graph of order n is panarboreal if and only if it has all of the trees in S as spanning trees. For each positive integer n ≠ 1, the star belongs to every spanning tree forcing set for order n. The main results of this paper are a proof that the path belongs to every spanning-tree forcing set for each order n ∉ {1, 6, 7, 8} and a computationally tractable characterization of the trees of order n ≥ 15 forced by the path and the star. Corollaries of those results include a construction of many trees that do not belong to any minimal spanning tree forcing set for orders n ≥ 15 and a proof that the following related decision problem is NP-complete: an instance is a pair (G, T) consisting of a graph G of order n and maximum degree n - 1 with a hamiltonian path, and a tree T of order n; the problem is to determine whether T is a spanning tree of G. © 1996 John Wiley & Sons, Inc.     

Domination versus disjunctive domination in graphs

A dominating set in a graph G is a set S of vertices of G such that every vertex not in S is adjacent to a vertex of S. The domination number of G is the minimum cardinality of a dominating set of G. For a positive integer b, a set S of vertices in a graph G is a b-disjunctive dominating set in G if every vertex v not in S is adjacent to a vertex of S or has at least b vertices in S at distance 2 from it in G. The b-disjunctive domination number of G is the minimum cardinality of a b-disjunctive dominating set. In this paper, we continue the study of disjunctive domination in graphs. We present properties of b-disjunctive dominating sets in a graph. A characterization of minimal b-disjunctive dominating sets is given. We obtain bounds on the ratio of the domination number and the b-disjunctive domination number for various families of graphs, including regular graphs and trees.     

Fast Enumeration Algorithms for Non-crossing Geometric Graphs

A non-crossing geometric graph is a graph embedded on a set of points in the plane with non-crossing straight line segments. In this paper we present a general framework for enumerating non-crossing geometric graphs on a given point set. Applying our idea to specific enumeration problems, we obtain faster algorithms for enumerating plane straight-line graphs, non-crossing spanning connected graphs, non-crossing spanning trees, and non-crossing minimally rigid graphs. Our idea also produces efficient enumeration algorithms for other graph classes, for which no algorithm has been reported so far, such as non-crossing matchings, non-crossing red-and-blue matchings, non-crossing k-vertex or k-edge connected graphs, or non-crossing directed spanning trees. The proposed idea is relatively simple and potentially applies to various other problems of non-crossing geometric graphs.     

Classification of interpolation theorems for spanning trees and other families of spanning subgraphs

We say that a graphical invariant i of a graph interpolates over a family F of graphs if i satisfies the following property: If m and M are the minimum and maximum values (respectively) of i over all graphs in F then for each k, m ? k ? M, there is a graph H in F for which i(H)= k. In previous works it was shown that when F is the set of spanning trees of a connected graph G, a large number of invariants interpolate (some of these invariants require the additional assumption that G be 2-connected). Although the proofs of all these results use the same basic idea of gradually transforming one tree into another via a sequence of edge exchanges, some of these processes require sequences that use more properties of trees than do others. We show that the edge exchange proofs can be divided into three types, in accordance with the extent to which the exchange sequence depends upon properties of spanning trees. This idea is then used to obtain new interpolation results for some invariants, and to show how the exchange methods and interpolation results on spanning trees can be extended to other families of spanning subgraphs.     

Steiner Numbers in Graphs

Abstract

The Steiner distance d(S) of a set S of vertices in a connected graph G is the minimum size of a connected subgraph of G that contains S. The Steiner number s(G) of a connected graph G of order p is the smallest positive integer m for which there exists a set S of m vertices of G such that d(S) = p—1. A smallest set S of vertices of a connected graph G of order p for which d(S) = p—1 is called a Steiner spanning set of G. It is shown that every connected graph has a unique Steiner spanning set. If G is a connected graph of order p and k is an integer with 0 ≤ k ≤ p—1, then the kth Steiner number sk(G) of G is the smallest positive integer m for which there exists a set S of m vertices of G such that d(S) = k. The sequence s_o(G),s₁ (G),…,8_p-1(G) is called the Steiner sequence of G. Steiner sequences for trees are characterized.     

Eliminating graphs by means of parallel knock-out schemes

In 1997 Lampert and Slater introduced parallel knock-out schemes, an iterative process on graphs that goes through several rounds. In each round of this process, every vertex eliminates exactly one of its neighbors. The parallel knock-out number of a graph is the minimum number of rounds after which all vertices have been eliminated (if possible). The parallel knock-out number is related to well-known concepts like perfect matchings, hamiltonian cycles, and 2-factors.We derive a number of combinatorial and algorithmic results on parallel knock-out numbers: for families of sparse graphs (like planar graphs or graphs of bounded tree-width), the parallel knock-out number grows at most logarithmically with the number n of vertices; this bound is basically tight for trees. Furthermore, there is a family of bipartite graphs for which the parallel knock-out number grows proportionally to the square root of n. We characterize trees with parallel knock-out number at most 2, and we show that the parallel knock-out number for trees can be computed in polynomial time via a dynamic programming approach (whereas in general graphs this problem is known to be NP-hard). Finally, we prove that the parallel knock-out number of a claw-free graph is either infinite or less than or equal to 2.     

Compatible connectedness in graphs and topological spaces

A topology on the vertex set of a graphG iscompatible with the graph if every induced subgraph ofG is connected if and only if its vertex set is topologically connected. In the case of locally finite graphs with a finite number of components, it was shown in [11] that a compatible topology exists if and only if the graph is a comparability graph and that all such topologies are Alexandroff. The main results of Section 1 extend these results to a much wider class of graphs. In Section 2, we obtain sufficient conditions on a graph under which all the compatible topologies are Alexandroff and in the case of bipartite graphs we show that this condition is also necessary.     

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.     

Further results on monotonic graph invariants and bipartiteness number

Abstract

The bipartiteness of a graph is the minimum number of vertices whose deletion from G results in a bipartite graph. If a graph invariant decreases or increases with addition of edges of its complement, then it is called a monotonic graph invariant. In this article, we determine the extremal values of some famous monotonic graph invariants, and characterize the corresponding extremal graphs in the class of all connected graphs with a given vertex bipartiteness.     

Walks and regular integral graphs

We establish a useful correspondence between the closed walks in regular graphs and the walks in infinite regular trees, which, after counting the walks of a given length between vertices at a given distance in an infinite regular tree, provides a lower bound on the number of closed walks in regular graphs. This lower bound is then applied to reduce the number of the feasible spectra of the 4-regular bipartite integral graphs by more than a half.Next, we give the details of the exhaustive computer search on all 4-regular bipartite graphs with up to 24 vertices, which yields a total of 47 integral graphs.     

Automorphisms of random graphs with specified vertices

Conditions are found under which the expected number of automorphisms of a large random labelled graph with a given degree sequence is close to 1. These conditions involve the probability that such a graph has a given subgraph. One implication is that the probability that a random unlabelledk-regular simple graph onn vertices has only the trivial group of automorphisms is asymptotic to 1 asn → ∞ with 3≦k=O(n ^1/2−c). In combination with previously known results, this produces an asymptotic formula for the number of unlabelledk-regular simple graphs onn vertices, as well as various asymptotic results on the probable connectivity and girth of such graphs. Corresponding results for graphs with more arbitrary degree sequences are obtained. The main results apply equally well to graphs in which multiple edges and loops are permitted, and also to bicoloured graphs. Research of the second author supported by U. S. National Science Foundation Grant MCS-8101555, and by the Australian Department of Science and Technology under the Queen Elizabeth II Fellowships Scheme. Current address: Mathematics Department, University of Auckland, Auckland, New Zealand.