Harmonic trees

A graph G is defined to be harmonic if there is a constant λ (necessarily a natural number) such that, for every vertex v, the sum of the degrees of the neighbors of v equals λd_G (v) where d_G (v) is the degree of v. We show that there is exactly one finite harmonic tree for every λ ε , and we give a recursive construction for all infinite harmonic trees.     

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.     

树的变形与代数连通度

本文利用瓶颈矩阵的Perron值和代数连通度的二次型形式,系统地研究了当迁移或改变分支(边、点)和变动一些边的权重时无向赋权树的代数连通度的变化规律,认为代数连通度可用来描述树的边及其权重的某种中心趋势性.引入广义树和广义特征点概念,将II型树转换成具有相同代数连通度的I型树,使得树的代数连通度的讨论只须限于I型树的研究即可.     

On L(d,1)-labelings of graphs

Given a graph G and a positive integer d, an L(d,1)-labeling of G is a function f that assigns to each vertex of G a non-negative integer such that if two vertices u and v are adjacent, then |f(u)−f(v)|d; if u and v are not adjacent but there is a two-edge path between them, then |f(u)−f(v)|1. The L(d,1)-number of G, λ_d(G), is defined as the minimum m such that there is an L(d,1)-labeling f of G with f(V){0,1,2,…,m}. Motivated by the channel assignment problem introduced by Hale (Proc. IEEE 68 (1980) 1497–1514), the L(2,1)-labeling and the L(1,1)-labeling (as d=2 and 1, respectively) have been studied extensively in the past decade. This article extends the study to all positive integers d. We prove that λ_d(G)Δ²+(d−1)Δ for any graph G with maximum degree Δ. Different lower and upper bounds of λ_d(G) for some families of graphs including trees and chordal graphs are presented. In particular, we show that the lower and the upper bounds for trees are both attainable, and the upper bound for chordal graphs can be improved for several subclasses of chordal graphs.     

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.     

Every tree is 3-equitable

A labeling of a graph is a function f from the vertex set to some subset of the natural numbers. The image of a vertex is called its label. We assign the label |f(u)−f(v)| to the edge incident with vertices u and v. In a k-equitable labeling the image of f is the set {0,1,2,…,k−1}. We require both the vertex labels and the edge labels to be as equally distributed as possible, i.e., if v_i denotes the number of vertices labeled i and e_i denotes the number of edges labeled i, we require |v_i−v_j|1 and |e_i−e_j|1 for every i,j in {0,1,2,…,k−1}. Equitable graph labelings were introduced by I. Cahit as a generalization for graceful labeling. We prove that every tree is 3-equitable.     

Constructions for type I trees with nonisomorphic Perron branches

A tree is classified as being type I provided that there are two or more Perron branches at its characteristic vertex. The question arises as to how one might construct such a tree in which the Perron branches at the characteristic vertex are not isomorphic. Motivated by an example of Grone and Merris, we produce a large class of such trees, and show how to construct others from them. We also investigate some of the properties of a subclass of these trees. Throughout, we exploit connections between characteristic vertices, algebraic connectivity, and Perron values of certain positive matrices associated with the tree.     

Coupling and harmonic functions in the case of continuous time Markov processes

Consider two transient Markov processes (X^v_t)_tεR·, (X^μ_t)_tεR· with the same transition semigroup and initial distributions v and μ. The probability spaces supporting the processes each are also assumed to support an exponentially distributed random variable independent of the process.

We show that there exist (randomized) stopping times S for (X^v_t), T for (X^μ_t) with common final distribution, L(X^v_S|S < ∞) = L(X^μ_T|T < ∞), and the property that for t < S, resp. t < T, the processes move in disjoint portions of the state space. For such a coupling (S, T) it is shown

where denotes the bounded harmonic functions of the Markov transition semigroup. Extensions, consequences and applications of this result are discussed.     

Budget constrained minimum cost connected medians

Several practical instances of network design and location theory problems require the network to satisfy multiple constraints. In this paper, we study a graph-theoretic problem that aims to simultaneously address a network design task and a location-theoretic constraint. The Budget Constrained Connected Median Problem is the following: We are given an undirected graph G=(V,E) with two different edge-weight functions c (modeling the construction or communication cost) and d (modeling the service distance), and a bound B on the total service distance. The goal is to find a subtree T of G with minimum c-cost c(T) subject to the constraint that the sum ∑_vVTdist_d(v,T) of the service distances of all the remaining nodes vVT does not exceed the specified budget B. Here, the service distance dist_d(v,T) denotes the shortest path distance of v to a vertex in T with respect to d. This problem has applications in optical network design and the efficient maintenance of distributed databases.

We formulate this problem as a bicriteria network design problem, and present bicriteria approximation algorithms. We also prove lower bounds on the approximability of the problem which demonstrate that our performance ratios are close to best possible.     

Weighted domination in triangle-free graphs

A weighted graph (G,w) is a graph G together with a positive weight-function on its vertex set w : V(G)→R^>0. The weighted domination number γ_w(G) of (G,w) is the minimum weight w(D)=∑_vDw(v) of a set DV(G) such that every vertex xV(D)−D has a neighbor in D. If ∑_vV(G)w(v)=|V(G)|, then we speak of a normed weighted graph. Recently, we proved that

for normed weighted bipartite graphs (G,w) of order n such that neither G nor the complement has isolated vertices. In this paper we will extend these Nordhaus–Gaddum-type results to triangle-free graphs.     

Strong equality of domination parameters in trees

We study the concept of strong equality of domination parameters. Let P₁ and P₂ be properties of vertex subsets of a graph, and assume that every subset of V(G) with property P₂ also has property P₁. Let ψ₁(G) and ψ₂(G), respectively, denote the minimum cardinalities of sets with properties P₁ and P₂, respectively. Then ψ₁(G)ψ₂(G). If ψ₁(G)=ψ₂(G) and every ψ₁(G)-set is also a ψ₂(G)-set, then we say ψ₁(G) strongly equals ψ₂(G), written ψ₁(G)≡ψ₂(G). We provide a constructive characterization of the trees T such that γ(T)≡i(T), where γ(T) and i(T) are the domination and independent domination numbers, respectively. A constructive characterization of the trees T for which γ(T)=γ_t(T), where γ_t(T) denotes the total domination number of T, is also presented.     

Choosability of planar graphs

A graph G = G(V, E) with lists L(v), associated with its vertices v V, is called L-list colourable if there is a proper vertex colouring of G in which the colour assigned to a vertex v is chosen from L(v). We say G is k-choosable if there is at least one L-list colouring for every possible list assignment L with L(v) = k v V(G).

Now, let an arbitrary vertex v of G be coloured with an arbitrary colour f of L(v). We investigate whether the colouring of v can be continued to an L-list colouring of the whole graph. G is called free k-choosable if such an L-list colouring exists for every list assignment L (L(v) = k v V(G)), every vertex v and every colour f L(v). We prove the equivalence of the well-known conjecture of Erd s et al. (1979): “Every planar graph is 5-choosable” with the following conjecture: “Every planar graph is free 5-choosable”.     

Embedding complete trees into the hypercube

We consider embeddings of the complete t-ary trees of depth k (denotation T^k,t) as subgraphs into the hypercube of minimum dimension n. This n, denoted by dim(T^k,t), is known if max{k,t}2. First, we study the next open cases t=3 and k=3. We improve the known upper bound dim(T^k,3)2k+1 up to lim_k→∞dim(T^k,3)/k5/3 and show lim_t→∞dim(T^3,t)/t=227/120. As a co-result, we present an exact formula for the dimension of arbitrary trees of depth 2, as a function of their vertex degrees. These results and new techniques provide an improvement of the known upper bound for dim(T^k,t) for arbitrary k and t.     

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.     

Profile minimization on triangulated triangles

Given graph G=(V,E) on n vertices, the profile minimization problem is to find a one-to-one function f:V→{1,2,…,n} such that ∑_vV(G){f(v)−min_xN[v] f(x)} is as small as possible, where N[v]={v}{x: x is adjacent to v} is the closed neighborhood of v in G. The trangulated triangle T_l is the graph whose vertices are the triples of non-negative integers summing to l, with an edge connecting two triples if they agree in one coordinate and differ by 1 in the other two coordinates. This paper provides a polynomial time algorithm to solve the profile minimization problem for trangulated triangles T_l with side-length l.     

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).     

Algorithmic complexity of list colorings

Given a graph G = (V,E) and a finite set L(v) at each vertex v ε V, the List Coloring problem asks whether there exists a function f:V → _vεVL(V) such that (i) f(v)εL(v) for each vεV and (ii) f(u) ≠f(v) whenever u, vεV and uvεE. One of our results states that this decision problem remains NP-complete even if all of the followingconditions are met: (1) each set L(v) has at most three elements, (2) each “color” xε_vεVL(v) occurs in at most three sets L(v), (3) each vertex vεV has degree at most three, and (4) G is a planar graph. On the other hand, strengthening any of the assumptions (1)–(3) yields a polynomially solvable problem. The connection between List Coloring and Boolean Satisfiability is discussed, too.     

Graph rigidity via Euclidean distance matrices

Let G=(V,E,ω) be an incomplete graph with node set V, edge set E, and nonnegative weights ω_ij's on the edges. Let each edge (v_i,v_j) be viewed as a rigid bar, of length ω_ij, which can rotate freely around its end nodes. A realization of a graph G is an assignment of coordinates, in some Euclidean space, to each node of G. In this paper, we consider the problem of determining whether or not a given realization of a graph G is rigid. We show that each realization of G can be epresented as a point in a compact convex set ; and that a generic realization of G is rigid if and only if its corresponding point is a vertex of Ω, i.e., an extreme point with full-dimensional normal cone.     

On ringeisen's isolation game

We develop the theory of the Isolation Game on a graph G, in which two players alternately “switch” at successive vertices v not previously switched. The switching operation deletes all edges incident with v, and creates new edges between v and those vertices not previously adjacent to it. The game is won when a vertex is first isolated. Among other results, we show that n-vertex forced wins exist for all n, and that length-p forced wins exist for all p. We give generic examples of forced wins which (against best defense) can be won only very late in the game. We also prove several large classes of graphs to be unwinnable, and give a complexity results for a problem closely related to the identification of drawing strategies in I_n(G).     

Voronoi drawings of trees

We study the problem of characterizing sets of points whose Voronoi diagrams are trees and if so, what are the combinatorial properties of these trees. The second part of the problem can be naturally turned into the following graph drawing question: Given a tree T, can one represent T so that the resulting drawing is a Voronoi diagram of some set of points? We investigate the problem both in the Euclidean and in the Manhattan metric. The major contributions of this paper are as follows.

• We characterize those trees that can be drawn as Voronoi diagrams in the Euclidean metric.

• We characterize those sets of points whose Voronoi diagrams are trees in the Manhattan metric.

• We show that the maximum vertex degree of any tree that can be drawn as a Manhattan Voronoi diagram is at most five and prove that this bound is tight.

• We characterize those binary trees that can be drawn as Manhattan Voronoi diagrams.