On approximation intractability of the path–distance–width problem

Path–distance–width of a graph G=(V,E), denoted by pdw(G), is the minimum integer k satisfying that there is a nonempty subset of SV such that the number of the nodes with distance i from S is at most k for any nonnegative integer i. It is known that given a positive integer k and a graph G, the decision problem pdw(G)k is NP-complete even if G is a tree (Yamazaki et al. Lecture Notes in Computer Science, vol. 1203, Springer, Berlin, 1997, pp. 276–287). In this paper, we show that it is NP-hard to approximate the path–distance–width of a graph within a ratio for any >0, even for trees.     

A doubly cyclic channel assignment problem

A standard model for radio channel assignment involves a set V of sites, the set {0,1,2,…} of channels, and a constraint matrix (w(u, v)) specifying minimum channel separations. An assignment f:V→{0,1,2,…} is feasible if the distance f(u) − f(v)w(u, v) for each pair of sites u and v. The aim is to find the least k such that there is a feasible assignment using only the k channels 0, 1, …, k − 1, and to find a corresponding optimal assignment.

We consider here a related problem involving also two cycles. There is a given cyclic order τ on the sites, and feasible assignments f must also satisfy f(τv) f(v) for all except one site v. Further, the channels are taken to be evenly spaced around a circle, so that if the k channels 0, 1, …, k − 1 are available then the distance between channels i and j is the minimum of ¦i − j¦ and k − ¦i − j¦. We show how to find a corresponding optimal channel assignment in O(¦V¦³) steps.     

Continuous bottleneck tree partitioning problems

We study continuous partitioning problems on tree network spaces whose edges and nodes are points in Euclidean spaces. A continuous partition of this space into p connected components is a collection of p subtrees, such that no pair of them intersect at more than one point, and their union is the tree space. An edge-partition is a continuous partition defined by selecting p−1 cut points along the edges of the underlying tree, which is assumed to have n nodes. These cut points induce a partition into p subtrees (connected components). The objective is to minimize (maximize) the maximum (minimum) “size” of the components (the min–max (max–min) problem). When the size is the length of a subtree, the min–max and the max–min partitioning problems are NP-hard. We present O(n² log(min(p,n))) algorithms for the edge-partitioning versions of the problem. When the size is the diameter, the min–max problems coincide with the continuous p-center problem. We describe O(n log³ n) and O(n log² n) algorithms for the max–min partitioning and edge-partitioning problems, respectively, where the size is the diameter of a component.     

Geometric applications of posets

We show the power of posets in computational geometry by solving several problems posed on a set S of n points in the plane: (1) find the n − k − 1 rectilinear farthest neighbors (or, equivalently, k nearest neighbors) to every point of S (extendable to higher dimensions), (2) enumerate the k largest (smallest) rectilinear distances in decreasing (increasing) order among the points of S, (3) given a distance δ > 0, report all the pairs of points that belong to S and are of rectilinear distance δ or more (less), covering k ≥ n/2 points of S by rectilinear (4) and circular (5) concentric rings, and (6) given a number k ≥ n/2 decide whether a query rectangle contains k points or less.     

Bipartite dimensions and bipartite degrees of graphs

A cover (bipartite) of a graph G is a family of complete bipartite subgraphs of G whose edges cover G's edges. G'sbipartite dimension d(G) is the minimum cardinality of a cover, and its bipartite degree η(G) is the minimum over all covers of the maximum number of covering members incident to a vertex. We prove that d(G) equals the Boolean interval dimension of the irreflexive complement of G, identify the 21 minimal forbidden induced subgraphs for d 2, and investigate the forbidden graphs for d n that have the fewest vertices. We note that for complete graphs, d(K_n) = [log₂n], η(K_n) = d(K_n) for n 16, and η(K_n) is unbounded. The list of minimal forbidden induced subgraphs for η 2 is infinite. We identify two infinite families in this list along with all members that have fewer than seven vertices.     

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.     

A new constrained edit distance between quotiented ordered trees

In this paper we propose a dynamic programming algorithm to compare two quotiented ordered trees using a constrained edit distance. An ordered tree is a tree in which the left-to-right order among siblings is significant. A quotiented ordered tree is an ordered tree T with an equivalence relation on vertices and such that, when the equivalence classes are collapsed to super-nodes, the graph so obtained is an ordered tree as well. Based on an algorithm proposed by Zhang and Shasha [K. Zhang, D. Shasha, Simple fast algorithms for the editing distance between trees and related problems, SIAM Journal on Computing 18 (6) (1989) 1245–1262] and introducing new notations, we describe a tree edit distance between quotiented ordered trees preserving equivalence relations on vertices during computation which works in polynomial time. Its application to RNA secondary structures comparison is finally presented.     

The polytope of degree sequences of hypergraphs

Let D_n(r) denote the convex hull of degree sequences of simple r-uniform hypergraphs on the vertex set {1,2,…,n}. The polytope D_n(2) is a well-studied object. Its extreme points are the threshold sequences (i.e., degree sequences of threshold graphs) and its facets are given by the Erdös–Gallai inequalities. In this paper we study the polytopes D_n(r) and obtain some partial information. Our approach also yields new, simple proofs of some basic results on D_n(2). Our main results concern the extreme points and facets of D_n(r). We characterize adjacency of extreme points of D_n(r) and, in the case r=2, determine the distance between two given vertices in the graph of D_n(2). We give a characterization of when a linear inequality determines a facet of D_n(r) and use it to bound the sizes of the coefficients appearing in the facet defining inequalities; give a new short proof for the facets of D_n(2); find an explicit family of Erdös–Gallai type facets of D_n(r); and describe a simple lifting procedure that produces a facet of D_n+1(r) from one of D_n(r).     

Parallel searching on m rays

We investigate parallel searching on m concurrent rays. We assume that a target t is located somewhere on one of the rays; we are given a group of m point robots each of which has to reach t. Furthermore, we assume that the robots have no way of communicating over distance. Given a strategy S we are interested in the competitive ratio defined as the ratio of the time needed by the robots to reach t using S and the time needed to reach t if the location of t is known in advance.

If a lower bound on the distance to the target is known, then there is a simple strategy which achieves a competitive ratio of 9—independent of m. We show that 9 is a lower bound on the competitive ratio for two large classes of strategies if m2.

If the minimum distance to the target is not known in advance, we show a lower bound on the competitive ratio of 1+2(k+1)^k+1/k^k where k=logm where log is used to denote the base-2 logarithm. We also give a strategy that obtains this ratio.     

Competitive on-line coverage of grid environments by a mobile robot

We describe in this paper two on-line algorithms for covering planar areas by a square-shaped tool attached to a mobile robot. Let D be the tool size. The algorithms, called Spanning Tree Covering (STC) algorithms, incrementally subdivide the planar area into a grid of D-size cells, while following a spanning tree of a grid graph whose nodes are 2D-size cells. The two STC algorithms cover general planar grids. The first, Spiral-STC, employs uniform weights on the grid-graph edges and generates spiral-like covering patterns. The second, Scan-STC, assigns lower weights to edges aligned with a particular direction and generates scan-like covering patterns along this direction. Both algorithms cover any planar grid using a path whose length is at most (n+m)D, where n is the total number of D-size cells and mn is the number of boundary cells, defined as cells that share at least one point with the grid boundary. We also demonstrate that any on-line coverage algorithm generates a covering path whose length is at least (2−)l_opt in worst case, where l_opt is the length of the optimal off-line covering path. Since (n+m)D2l_opt, the bound is tight and the STC algorithms are worst-case optimal. Moreover, in practical environments mn, and the STC algorithms generate close-to-optimal covering paths in such environments.     

On polyhedral retracts and compactifications of locally symmetric spaces

The results in this paper are based on a previously constructed exhaustion of a locally symmetric space V=ΓX by Riemannian polyhedra, i.e., compact submanifolds with corners: V=_s0V(s). We show that the interior of every polyhedron V(s) is homeomorphic to V. The universal covering space X(s) of V(s) is quasi-isometric to the discrete group Γ. It can be written as the complement of a Γ-invariant union of horoballs in X (which in general have intersections giving rise to the corners). This yields exponential isoperimetric inequalities for Γπ₁(V(s)). We also discuss the relation of this compactification of V with the Borel–Serre compactification.     

Nowhere zero flows in line graphs

Cai an Corneil (Discrete Math. 102 (1992) 103–106), proved that if a graph has a cycle double cover, then its line graph also has a cycle double cover, and that the validity of the cycle double cover conjecture on line graphs would imply the truth of the conjecture in general. In this note we investigate the conditions under which a graph G has a nowhere zero k-flow would imply that L(G), the line graph of G, also has a nowhere zero k-flow. The validity of Tutte's flow conjectures on line graphs would also imply the truth of these conjectures in general.     

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.     

Least domination in a graph

The least domination number γ_L of a graph G is the minimum cardinality of a dominating set of G whose domination number is minimum. The least point covering number _L of G is the minimum cardinality of a total point cover (point cover including every isolated vertex of G) whose total point covering number is minimum. We prove a conjecture of Sampathkumar saying that in every connected graph of order n 2. We disprove another one saying that γ_{L L} in every graph but instead of it, we establish the best possible inequality . Finally, in relation with the minimum cardinality γ_t of a dominating set without isolated vertices (total dominating set), we prove that the ratio γ_L/γ_t can be in general arbitrarily large, but remains bounded by if we restrict ourselves to the class of trees.     

Equivalence constants for certain matrix norms II

We give an almost complete solution of a problem posed by Klaus and Li [A.-L. Klaus, C.-K. Li, Isometries for the vector (p, q) norm and the induced (p, q) norm, Linear and Multilinear Algebra 38 (1995) 315–332]. Klaus and Li’s problem, which arose during their investigations of isometries, was to relate the Frobenius (or Hilbert–Schmidt) norm of a matrix to various operator norms of that matrix. Our methods are based on earlier work of Feng [B.Q. Feng, Equivalence constants for certain matrix norms, Linear Algebra Appl. 374 (2003) 247–253] and Tonge [A. Tonge, Equivalence constants for matrix norms: a problem of Goldberg, Linear Algebra Appl. 306 (2000) 1–13], but introduce as a new ingredient some techniques developed by Hardy and Littlewood [G.H. Hardy, J.E. Littlewood, Bilinear forms bounded in space [p, q], Quart. J. Math. (Oxford) 5 (1934) 241–254].     

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.     

Some results on integral sum graphs

Let Z denote the set of all integers. The integral sum graph of a finite subset S of Z is the graph (S,E) with vertex set S and edge set E such that for u,vS, uvE if and only if u+vS. A graph G is called an integral sum graph if it is isomorphic to the integral sum graph of some finite subset S of Z. The integral sum number of a given graph G, denoted by ζ(G), is the smallest number of isolated vertices which when added to G result in an integral sum graph. Let x denote the least integer not less than the real x. In this paper, we (i) determine the value of ζ(K_n−E(K_r)) for r2n/3−1, (ii) obtain a lower bound for ζ(K_n−E(K_r)) when 2r<2n/3−1 and n5, showing by construction that the bound is sharp when r=2, and (iii) determine the value of ζ(K_r,r) for r2. These results provide partial solutions to two problems posed by Harary (Discrete Math. 124 (1994) 101–108). Finally, we furnish a counterexample to a result on the sum number of K_r,s given by Hartsfiedl and Smyth (Graphs and Matrices, R. Rees (Ed.), Marcel, Dekker, New York, 1992, pp. 205–211).     

Semi-planar Steiner loops of cardinality 2n

It is well known that there is a planar sloop of cardinality n for each n≡2 or 4 (mod 6) (Math. Z. 111 (1969) 289–300). A semi-planar sloop is a simple sloop in which each triangle either generates the whole sloop or the 8-element sloop. In fact, Quackenbush (Canad. J. Math. 28 (1976) 1187–1198) has stated that there should be such semi-planar sloops. In this paper, we construct a semi-planar sloop of cardinality 2n for each n≡2 or 4 (mod 6). Consequently, we may say that there is a semi-planar sloop that is not planar of cardinality m for each m>16 and m≡4 or 8 (mod 12). Moreover, Quackenbush (Canad. J. Math. 28 (1976) 1187–1198) has proved that each finite simple planar sloop generates a variety, which covers the smallest non-trivial subvariety (the variety of all Boolean sloops) of the lattice of the subvarieties of all sloops. Similarly, it is easy to show that each finite semi-planar sloop generates another variety, which also covers the variety of all Boolean sloops. Furthermore, for any finite simple sloop of cardinality n, the author (Beiträge Algebra Geom. 43 (2) (2002) 325–331) has constructed a subdirectly irreducible sloop of cardinality 2n and containing as the only proper normal subsloop. Accordingly, if is a semi-planar sloop, then the variety generated by properly contains the subvariety .     

ContributionsAcyclic graphoidal covers and path partitions in a graph

An acyclic graphoidal cover of a graph G is a collection ψ of paths in G such that every path in ψ has at least two vertices, every vertex of G is an internal vertex of at most one path in ψ and every edge of G is in exactly one path in ψ. The minimum cardinality of an acyclic graphoidal cover of G is called the acyclic graphoidal covering number of G and is denoted by η_a. A path partition of a graph G is a collection P of paths in G such that every edge of G is in exactly one path in P. The minimum cardinality of a path partition of G is called the path partition number of G and is denoted by π. In this paper we determine η_a and π for several classes of graphs and obtain a characterization of all graphs with Δ 4 and η_a = Δ − 1. We also obtain a characterization of all graphs for which η_a = π.