Some results on generalized exponents

A digraph G = (V, E) is primitive if, for some positive integer k, there is a u → v walk of length k for every pair u, v of vertices of V. The minimum such k is called the exponent of G, denoted exp(G). The exponent of a vertex u ∈ V, denoted exp(u), is the least integer k such that there is a u → v walk of length k for each v ∈ V. For a set X ⊆ V, exp(X) is the least integer k such that for each v ∈ V there is a X → v walk of length k, i.e., a u → v walk of length k for some u ∈ X. Let F(G, k) : = max{exp(X) : |X| = k} and F(n, k) : = max{F(G, k) : |V| = n}, where |X| and |V| denote the number of vertices in X and V, respectively. Recently, B. Liu and Q. Li proved F(n, k) = (n − k)(n − 1) + 1 for all 1 ≤ k ≤ n − 1. In this article, for each k, 1 ≤ k ≤ n − 1, we characterize the digraphs G such that F(G, k) = F(n, k), thereby answering a question of R. Brualdi and B. Liu. We also find some new upper bounds on the (ordinary) exponent of G in terms of the maximum outdegree of G, Δ⁺(G) = max{d⁺(u) : u ∈ V}, and thus obtain a new refinement of the Wielandt bound (n − 1)² + 1. © 1998 John Wiley & Sons, Inc. J. Graph Theory 28: 215–225, 1998     

A polynomial method for the pos/neg weighted 3-median problem on a tree

Let a connected undirected graph G  =  (V, E) be given. In the classical p-median problem we want to find a set X containing p points in G such that the sum of weighted distances from X to all vertices in V is minimized. We consider the semi-obnoxious case where every vertex has either a positive or negative weight. In this case we have two different objective functions: the sum of the minimum weighted distances from X to all vertices and the sum of the weighted minimum distances. In this paper we show that for the case p = 3 an optimal solution for the second model in a tree can be found in O(n ⁵) time. If the 3-median is restricted to vertices or if the tree is a path then the complexity can be reduced to O(n ³). This research has partially been supported by the Spezialforschungsbereich F 003 “Optimierung und Kontrolle”, Projektbereich Diskrete Optimierung.     

On Four-Connecting a Triconnected Graph

We consider the problem of finding a smallest set of edges whose addition four-connects a triconnected graph. This is a fundamental graph-theoretic problem that has applications in designing reliable networks and improving statistical database security. We present an O(n · α(m, n) + m)-time algorithm for four-connecting an undirected graph G that is triconnected by adding the smallest number of edges, where n and m are the number of vertices and edges in G, respectively, and α(m, n) is the inverse Ackermann function. This is the first polynomial time algorithm to solve this problem exactly.In deriving our algorithm, we present a new lower bound for the number of edges needed to four-connect a triconnected graph. The form of this lower bound is different from the form of the lower bound known for biconnectivity augmentation and triconnectivity augmentation. Our new lower bound applies for arbitrary k and gives a tighter lower bound than the one known earlier for the number of edges needed to k-connect a (k − 1)-connected graph. For k = 4, we show that this lower bound is tight by giving an efficient algorithm to find a set of edges whose size equals the new lower bound and whose addition four-connects the input triconnected graph.     

Visibility queries in a polygonal region

In this paper, we consider the problem of computing the region visible to a query point located in a given polygonal domain. The polygonal domain is specified by a simple polygon with m holes and a total of n vertices. We provide two bounds on the complexity of this problem. One approach constructs a data structure with space complexity O(n²) in time O(n²lgn) and yields a query time of O((1+min(m,|V(q)|))lg²n+m+|V(q)|). Here, V(q) represents the set of vertices of the visibility polygon of a query point q, and |E| denotes the number of edges in the visibility graph. The other approach provides a data structure with space complexity O(min(|E|,mn)+n) in time O(T+|E|+nlgn) with the query time of O(|V(q)|lgn+m). Here, T is the time to triangulate the given polygonal region (which is O(n+mlg¹⁺m) for a small positive constant >0). In both of these approaches, O(m) additive factor in the query time is eliminated with an additional O((min(|E|,mn))²) space and an additional O(m(min(|E|,mn))²) preprocessing time.     

The Conditional Covering Problem on Unweighted Interval Graphs with Nonuniform Coverage Radius

Let G = (V, E) be an interval graph with n vertices and m edges. A positive integer R(x) is associated with every vertex x ? V{x\in V}. In the conditional covering problem, a vertex x ? V{x \in V} covers a vertex y ? V{y \in V} (x ≠ y) if d(x, y) ≤ R(x) where d(x, y) is the shortest distance between the vertices x and y. The conditional covering problem (CCP) finds a minimum cardinality vertex set C í V{C\subseteq V} so as to cover all the vertices of the graph and every vertex in C is also covered by another vertex of C. This problem is NP-complete for general graphs. In this paper, we propose an efficient algorithm to solve the CCP with nonuniform coverage radius in O(n ²) time, when G is an interval graph containing n vertices.     

Almost Injective Transformations of an Infinite Set

Let V be an infinite-dimensional vector space, let n be a cardinal such that ?₀ ≤ n ≤ dim V, and let AM(V, n) denote the semigroup consisting of all linear transformations of V whose nullity is less than n. In recent work, Mendes-Gonçalves and Sullivan studied the ideal structure of AM(V, n). Here, we do the same for a similarly-defined semigroup AM(X, q) of transformations defined on an infinite set X. Although our results are clearly comparable with those already obtained for AM(V, n), we show that the two semigroups are never isomorphic.     

All-Pairs Small-Stretch Paths

Let G = (V, E) be a weighted undirected graph. A path between u, v  V is said to be of stretch t if its length is at most t times the distance between u and v in the graph. We consider the problem of finding small-stretch paths between all pairs of vertices in the graph G.It is easy to see that finding paths of stretch less than 2 between all pairs of vertices in an undirected graph with n vertices is at least as hard as the Boolean multiplication of two n × n matrices. We describe three algorithms for finding small-stretch paths between all pairs of vertices in a weighted graph with n vertices and m edges. The first algorithm, STRETCH₂, runs in Õ(n^3/2m^1/2) time and finds stretch 2 paths. The second algorithm, STRETCH_7/3, runs in Õ(n^7/3) time and finds stretch 7/3 paths. Finally, the third algorithm, STRETCH₃, runs in Õ(n²) and finds stretch 3 paths.Our algorithms are simpler, more efficient and more accurate than the previously best algorithms for finding small-stretch paths. Unlike all previous algorithms, our algorithms are not based on the construction of sparse spanners or sparse neighborhood covers.     

Embedding Planar Graphs at Fixed Vertex Locations

 Let G be a planar graph of n vertices, v ₁,…,v _n , and let {p ₁,…,p _n } be a set of n points in the plane. We present an algorithm for constructing in O(n ²) time a planar embedding of G, where vertex v _i is represented by point p _i and each edge is represented by a polygonal curve with O(n) bends (internal vertices). This bound is asymptotically optimal in the worst case. In fact, if G is a planar graph containing at least m pairwise independent edges and the vertices of G are randomly assigned to points in convex position, then, almost surely, every planar embedding of G mapping vertices to their assigned points and edges to polygonal curves has at least m/20 edges represented by curves with at least m/40³ bends. Received: May 24, 1999 Final version received: April 10, 2000     

On cycle—Complete graph ramsey numbers

A new upper bound is given for the cycle-complete graph Ramsey number r(C_m, K_n), the smallest order for a graph which forces it to contain either a cycle of order m or a set of n independent vertices. Then, another cycle-complete graph Ramsey number is studied, namely r(?C_m, K_n) the smallest order for a graph which forces it to contain either a cycle of order / for some / satisfying 3?/?m or a set of n independent vertices. We obtain the exact value of r(?C_m K_n) for all m > n and an upper bound which applies when m is large in comparison with log n.     

The List-Chromatic Number of Infinite Graphs Defined on Euclidean Spaces

If D is a countable set of positive reals, 2≤n<ω, let X _n (D) be the graph with the points of R ⁿ as vertices where two vertices are joined iff their distance is in D. We determine the list-chromatic number of X _n (D) as much as possible.     

Linear preservers of matrices of rank-2

Let T be a linear operator on the space of all m×n matrices over any field. we prove that if T maps rank-2 matrices to rank-2 matrices then there exist nonsingular matrices U and V such that either T(X)=UXV for all matrices X, or m=n and T(X)=UX^tV for all matrices X where X^t denotes the transpose of X.     

Asymptotic Determination of the Last Packing Number of Quadruples

A 3-(n,4,1) packing design consists of an n-element set X and a collection of 4-element subsets of X, called blocks, such that every 3-element subset of X is contained in at most one block. The packing number of quadruples d(3,4,n) denotes the number of blocks in a maximum 3-(n,4,1) packing design, which is also the maximum number A(n,4,4) of codewords in a code of length n, constant weight 4, and minimum Hamming distance 4. In this paper the last packing number A(n,4,4) for n≡ 5(mod 6) is shown to be equal to Johnson bound with 21 undecided values n=6k+5, k∈{m: m is odd , 3≤ m≤ 35, m≠ 17,21}∪ {45,47,75,77,79,159}. AMS Classification:05B40, 94B25     

The degree sequence of a random graph. I. The models

We show that the joint distribution of the degrees of a random graph can be accurately approximated by several simpler models derived from a set of independent binomial distributions. On the one hand, we consider the distribution of degree sequences of random graphs with n vertices and ½m edges. For a wide range of values of m, this distribution is almost everywhere in close correspondence with the conditional distribution {(X₁,…,X_n) | ∑ X_i=m}, where X₁,…,X_n are independent random variables, each having the same binomial distribution as the degree of one vertex. We also consider random graphs with n vertices and edge probability p. For a wide range of functions p=p(n), the distribution of the degree sequence can be approximated by {(X₁,…,X>_n) | ∑ X_i is even}, where X₁,…,X_n are independent random variables each having the distribution Binom (n−1, p′), where p′ is itself a random variable with a particular truncated normal distribution. To facilitate computations, we demonstrate techniques by which statistics in this model can be inferred from those in a simple model of independent binomial random variables. Where they apply, the accuracy of our method is sufficient to determine asymptotically all probabilities greater than n^−k for any fixed k. In this first paper, we use the geometric mean of degrees as a tutorial example. In the second paper, we will determine the asymptotic distribution of the tth largest degree for all functions t=t(n) as n→∞. © 1997 John Wiley & Sons, Inc. Random Struct. Alg., 11 , 97–117 (1997)     

Lollipop graphs are extremal for commute times

Consider a simple random walk on a connected graph G=(V, E). Let C(u, v) be the expected time taken for the walk starting at vertex u to reach vertex v and then go back to u again, i.e., the commute time for u and v, and let C(G)=max_{u, v∈V}C(u, v). Further, let 𝒢(n, m) be the family of connected graphs on n vertices with m edges, , and let 𝒢(n)=∪_m𝒢(n, m) be the family of all connected n‐vertex graphs. It is proved that if G∈(n, m) is such that C(G)=max_{H∈𝒢(n, m)}C(H) then G is either a lollipop graph or a so‐called double‐handled lollipop graph. It is further shown, using this result, that if C(G)=max_H∈𝒢(n)C(H) then G is the full lollipop graph or a full double‐handled lollipop graph with [(2n−1)/3] vertices in the clique unless n≤9 in which case G is the n‐path. ©2000 John Wiley & Sons, Inc. Random Struct. Alg., 16, 131–142, 2000     

Distributing vertices on Hamiltonian cycles

Let G be a graph of order n and 3≤t≤n/4 be an integer. Recently, Kaneko and Yoshimoto [J Combin Theory Ser B 81(1) (2001), 100–109] provided a sharp δ(G) condition such that for any set X of t vertices, G contains a hamiltonian cycle H so that the distance along H between any two vertices of X is at least n/2t. In this article, minimum degree and connectivity conditions are determined such that for any graph G of sufficiently large order n and for any set of t vertices X?V(G), there is a hamiltonian cycle H so that the distance along H between any two consecutive vertices of X is approximately n/t. Furthermore, the minimum degree threshold is determined for the existence of a hamiltonian cycle H such that the vertices of X appear in a prescribed order at approximately predetermined distances along H. © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 28–45, 2012     

A polynomial-time algorithm for the paired-domination problem on permutation graphs

A set S of vertices in a graph H=(V,E) with no isolated vertices is a paired-dominating set of H if every vertex of H is adjacent to at least one vertex in S and if the subgraph induced by S contains a perfect matching. Let G be a permutation graph and π be its corresponding permutation. In this paper we present an O(mn) time algorithm for finding a minimum cardinality paired-dominating set for a permutation graph G with n vertices and m edges.     

A Parallel Algorithm for Computing Minimum Spanning Trees

present a simple and implementable algorithm that computes a minimum spanning tree of an undirected weighted graph G = (V, E) of n = |V| vertices and m = |E| edges on an EREW PRAM in O(log^3/2n) time using n + m processors. This represents a substantial improvement in the running time over the previous results for this problem using at the same time the weakest of the PRAM models. It also implies the existence of algorithms having the same complexity bounds for the EREW PRAM, for connectivity, ear decomposition, biconnectivity, strong orientation, st-numbering and Euler tours problems.     

On Super Restricted Edge Connectivity of Half Vertex Transitive Graphs

Let X =  (V, E) be a connected graph. Call X super restricted edge connected in short, sup-λ′, if F is a minimum edge set of X such that X − F is disconnected and every component of X − F has at least two vertices, then F is the set of edges adjacent to a certain edge with minimum edge degree in X. A bipartite graph is said to be half vertex transitive if its automorphism group is transitive on the sets of its bipartition. In this article, we show that every connected half vertex transitive graph X with n =  |V(X)| ≥  4 and X \ncong K_1,n-1{X \ncong K_{1,n-1}} is λ′-optimal. By studying the λ′-superatoms of X, we characterize sup-λ′ connected half vertex transitive graphs. As a corollary, sup-λ′ connected Bi-Cayley graphs are also characterized.     

Planar rectilinear shortest path computation using corridors

The rectilinear shortest path problem can be stated as follows: given a set of m non-intersecting simple polygonal obstacles in the plane, find a shortest L₁-metric (rectilinear) path from a point s to a point t that avoids all the obstacles. The path can touch an obstacle but does not cross it. This paper presents an algorithm with time complexity O(n+m(lgn)^3/2), which is close to the known lower bound of Ω(n+mlgm) for finding such a path. Here, n is the number of vertices of all the obstacles together.     

Sharp bounds for decompositions of graphs into complete r-partite subgraphs

If G is a graph on n vertices and r ≥ 2, we let m_r(G) denote the minimum number of complete multipartite subgraphs, with r or fewer parts, needed to partition the edge set, E(G). In determining m_r(G), we may assume that no two vertices of G have the same neighbor set. For such reducedgraphs G, we prove that m_r(G) ≥ log₂ (n + r − 1)/r. Furthermore, for each k ≥ 0 and r ≥ 2, there is a unique reduced graph G = G(r, k) with m_r(G) = k for which equality holds. We conclude with a short proof of the known eigenvalue bound m_r(G) ≥ max{n₊ (G, n₋(G)/(r − 1)}, and show that equality holds if G = G(r, k). © 1996 John Wiley & Sons, Inc.