A comparison between the metric dimension and zero forcing number of trees and unicyclic graphs

The metric dimension dim(G)of a graph G is the minimum number of vertices such that every vertex of G is uniquely determined by its vector of distances to the chosen vertices.The zero forcing number Z(G)of a graph G is the minimum cardinality of a set S of black vertices(whereas vertices in V(G)\S are colored white)such that V(G)is turned black after finitely many applications of"the color-change rule":a white vertex is converted black if it is the only white neighbor of a black vertex.We show that dim(T)≤Z(T)for a tree T,and that dim(G)≤Z(G)+1 if G is a unicyclic graph;along the way,we characterize trees T attaining dim(T)=Z(T).For a general graph G,we introduce the"cycle rank conjecture".We conclude with a proof of dim(T)-2≤dim(T+e)≤dim(T)+1 for e∈E(T).     

A faster 2-approximation algorithm for the minmax p-traveling salesmen problem on a tree

Given an edge-weighted tree T and an integer p1, the minmax p-traveling salesmen problem on a tree T asks to find p tours such that the union of the p tours covers all the vertices. The objective is to minimize the maximum of length of the p tours. It is known that the problem is NP-hard and has a (2−2/(p+1))-approximation algorithm which runs in O(p^p−1n^p−1) time for a tree with n vertices. In this paper, we consider an extension of the problem in which the set of vertices to be covered now can be chosen as a subset S of vertices and weights to process vertices in S are also introduced in the tour length. For the problem, we give an approximation algorithm that has the same performance guarantee, but runs in O((p−1)!·n) time.     

An edge version of the matrix-tree theorem and the wiener index

Let T be a tree on n vertices. The Laplacian matrix is L(T)=D(T)-A(T), where D(T) is the diagonal matrix of vertex degrees and A(T) is the adjacency matrix. A special case of the Matrix-Tree Theorem is that the adjugate of L(T) is the n-by-n matrix of l's. The (n-l)-square "edge version" of L(T)is K(T). The main result is a graph-theoretic interpretation of the entries of the adjugate of K(T). As an application, it is shown that the Wiener Index from chemistry is the trace of this adjugate.     

The k-ball l-path branch weight centroid

If x is a vertex of a tree T of radius r, if k and l are integers, if 0 k r, 0 l r, and if P is an l-path with one end at x, then define β(x; k, P) to be the number of vertices of T that are reachable from x via the l-path P and that are outside of the k-ball about x. That is, β(x;k,P) = {yεV(T):y is reachable from x via P,d(x,y) > k}. Define the k-ball l-path branch weight of x, denoted β(x;k,l), to be max {β(x;k,P):P an l-path with one end at x}, and define the k-balll-path branch weight centroid of T, denoted B(T;k,l), to be the set xεV(T): β(x;k,l) β(y;k,l), yεV(T). This two-parameter family of central sets in T includes the one-parameter family of central sets called the k-nuclei introduced by Slater (1981) which has been shown to be the one parameter family of central sets called the k-branch weight centroids by Zaw Win (1993). It also includes the one-parameter family of central sets called the k-ball branch weight centroid introduced by Reid (1991). In particular, this new family contains the classical central sets, the center and the median (which Zelinka (1968) showed is the ordinary branch weight centroid). The sets obtained for particular values of k and l are examined, and it is shown that for many values they consist of one vertex or two adjacent vertices.     

Moore-penrose inverse of the incidence matrix of a tree

Let T be a tree with n vertices, where each edge is given an orientation, and let Q be its vertex-edge incidence matrix. It is shown that the Moore-Penrose inverse of Q is the (n-1)× n matrix M obtained as follows. The rows and the columns of M are indexed by the edges and the vertices of T respectively. If e,ν are an edge and a vertex of T respectively, then the (e,ν)-entry of M is, upto a sign, the number of vertices in the connected component of T\e which does not contain ν. Furthermore, the sign of the entry is positive or negative, depending on whether e is oriented away from or towards ν. This result is then used to obtain an expression for the Moore-Penrose inverse of the incidence matrix of an arbitrary directed graph. A recent result due to Moon is also derived as a consequence.     

A linear time algorithm for edge coloring of binomial trees

We consider the problem of efficient coloring of the edges of a so-called binomial tree T, i.e. acyclic graph containing two kinds of edges: those which must have a single color and those which are to be colored with L consecutive colors, where L is an arbitrary integer greater than 1. We give an O(n) time algorithm for optimal coloring of such a tree, where n is the number of vertices of T. Also, we give simple bounds on the chromatic index of T and a division of all binomial trees into two classes depending on their chromaticity.     

NoteA 16-vertex tournament for which Banks set and Slater set are disjoint

Given a tournament T, a Banks winner of T is the first vertex of any maximal (with respect to inclusion) transitive subtournament of T; a Slater winner of T is the first vertex of any transitive tournament at minimum distance of T (the distance being the number of arcs to reverse in T to make T transitive). In this note, we show that there exists a tournament with 16 vertices for which no Slater winner is a Banks winner. This counterexample improves the previous one, due to G. Laffond and J.-F. Laslier, which has 75 vertices.     

Characteristic vertices of weighted trees via perron values

We consider a weighted tree T with algebraic connectivity μ, and characteristic vertex v. We show that μ and its associated eigenvectors can be described in terms of the Perron value and vector of a nonnegative matrix which can be computed from the branches of T at v. The machinery of Perron-Frobenius theory can then be used to characterize Type I and Type II trees in terms of these Perron values, and to show that if we construct a weighted tree by taking two weighted trees and identifying a vertex of one with a vertex of the other, then any characteristic vertex of the new tree lies on the path joining the characteristic vertices of the two old trees.     

Coloring permutation graphs in parallel

A coloring of a graph G is an assignment of colors to its vertices so that no two adjacent vertices have the same color. We study the problem of coloring permutation graphs using certain properties of the lattice representation of a permutation and relationships between permutations, directed acyclic graphs and rooted trees having specific key properties. We propose an efficient parallel algorithm which colors an n-node permutation graph in O(log² n) time using O(n²/log n) processors on the CREW PRAM model. Specifically, given a permutation π we construct a tree T^*[π], which we call coloring-permutation tree, using certain combinatorial properties of π. We show that the problem of coloring a permutation graph is equivalent to finding vertex levels in the coloring-permutation tree.     

Decomposition of some planar graphs into trees

We prove that each simple planar graph G whose all faces are quadrilaterals can be decomposed into two disjoint trees T_r and T_b such that V(T_r) = V(G − u) and V(T_b) = V(G − v) for any two non-adjacent vertices u and v of G.     

All trees are 1-embeddable and all except stars are 2-embeddable

A graph G with n vertices is said to be embeddable (in its complement) if there is an automorphism φ of K_n such that E(G) ∩ E(φ(G))=. It is known that all trees T with n (≥2) vertices and T K_1,n−1 are embeddable. We say that G is 1-embeddable if, for every edge e, there is an automorphism φ of K_n such that E(G) ∩ E(φ(G))={e};and that it is 2-embeddable if,for every pair e₁, e₂ of edges, there is an automorphism φ of K_n such that E(G) ∩ E(φ(G))={e₁, e₂}. We prove here that all trees with n (3) vertices are 1-embeddable; and that all trees T with n (4) vertices and T K_1,n−1 are 2-embeddable. In a certain sense, this result is sharp.     

The reversing number of a diagraph

A minimum reversing set of a diagraph is a smallest sized set of arcs which when reversed makes the diagraph acyclic. We investigate a related issue: Given an acyclic diagraph D, what is the size of a smallest tournament T which has the arc set of D as a minimun reversing set? We show that such a T always exists and define the reversing number of an acyclic diagraph to be the number of vertices in T minus the number of vertices in D. We also derive bounds and exact values of the reversing number for certain classes of acyclic diagraphs.     

Induced subtrees in graphs of large chromatic number

Our paper proves special cases of the following conjecture: for any fixed tree T there exists a natural number f = f (T) to that every triangle-free graph of chromaticnumber f(T) contains T as an induced subgraph. The main result concerns the case when T has radius two.     

A note on transitive orientations with maximum sets of sources and sinks

Given a transitive orientation of a comparability graph G, a vertex of G is a source (sink) if it has indegree (outdegree) zero in , respectively. A source set of G is a subset of vertices formed by sources of some transitive orientation . A pair of subsets S,TV(G) is a source–sink pair of G when the vertices of S and T are sources and sinks, of some transitive orientation , respectively. We describe algorithms for finding a transitive orientation with a maximum source–sink pair in a comparability graph. The algorithms are applications of modular decomposition and are all of linear-time complexity.     

A Ramsey-type problem on right-angled triangles in space

It is proved that for any 3-coloring of R³ and for any right-angled triangle T, one can find a congruent copy of T, all of whose vertices are of the same color.     

Area-efficient algorithms for straight-line tree drawings

We investigate several straight-line drawing problems for bounded-degree trees in the integer grid without edge crossings under various types of drawings: (1) upward drawings whose edges are drawn as vertically monotone chains, a sequence of line segments, from a parent to its children, (2) order-preserving drawings which preserve the left-to-right order of the children of each vertex, and (3) orthogonal straight-line drawings in which each edge is represented as a single vertical or horizontal segment.

Main contribution of this paper is a unified framework to reduce the upper bound on area for the straight-line drawing problems from O(nlogn) (Crescenzi et al., 1992) to O(nloglogn). This is the first solution of an open problem stated by Garg et al. (1993). We also show that any binary tree admits a small area drawing satisfying any given aspect ratio in the orthogonal straight-line drawing type.

Our results are briefly summarized as follows. Let T be a bounded-degree tree with n vertices. Firstly, we show that T admits an upward straight-line drawing with area O(nloglogn). If T is binary, we can obtain an O(nloglogn)-area upward orthogonal drawing in which each edge is drawn as a chain of at most two orthogonal segments and which has O(n/logn) bends in total. Secondly, we present O(nloglogn)-area (respectively, -volume) orthogonal straight-line drawing algorithms for binary trees with arbitrary aspect ratios in 2-dimension (respectively, 3-dimension). Finally, we present some experimental results which shows the area requirements, in practice, for (order-preserving) upward drawing are much smaller than theoretical bounds obtained through analysis.     

On the bounded domination number of tournaments

In a simple digraph, a star of degree t is a union of t edges with a common tail. The k-domination number γ_k(G) of digraph G is the minimum number of stars of degree at most k needed to cover the vertex set. We prove that γ_k(T)=n/(k+1) when T is a tournament with n14k lg k vertices. This improves a result of Chen, Lu and West. We also give a short direct proof of the result of E. Szekeres and G. Szekeres that every n-vertex tournament is dominated by at most lg n−lglg n+2 vertices.     

A linear time algorithm for balance vertices on trees

The concept of balance vertices was first investigated by Reid (1999). For the main result “the balance vertices of a tree consist of a single vertex or two adjacent vertices”, Shan and Kang (2004) and Reid and DePalma (2005) improved the length and technique of the proof. In this paper we further discuss the balance vertices on trees in a generalization context. We do not only provide a simple efficient proof for the relevant result but also develop a linear time algorithm to find the set of balance vertices on the underlying tree.     

Compound connection matrices

Suppose T is an incidence, basis circuit or basis cut set matrix of a connected graph and T^(k) is the k compound of T. It is proven that any second order minor of T^(k) is equal +1, −1, or 0. For the case of an incidence matrix this result is applied to tree counting and some structural properties of T^(k) are given.     

Cell rotation graphs of strongly connected orientations of plane graphs with an application

The cell rotation graph D(G) on the strongly connected orientations of a 2-edge-connected plane graph G is defined. It is shown that D(G) is a directed forest and every component is an in-tree with one root; if T is a component of D(G), the reversions of all orientations in T induce a component of D(G), denoted by T⁻, thus (T,T⁻) is called a pair of in-trees of D(G); G is Eulerian if and only if D(G) has an odd number of components (all Eulerian orientations of G induce the same component of D(G)); the width and height of T are equal to that of T⁻, respectively. Further it is shown that the pair of directed tree structures on the perfect matchings of a plane elementary bipartite graph G coincide with a pair of in-trees of D(G). Accordingly, such a pair of in-trees on the perfect matchings of any plane bipartite graph have the same width and height.