Limit theory for the random on‐line nearest‐neighbor graph

In the on‐line nearest‐neighbor graph (ONG), each point after the first in a sequence of points in ?^d is joined by an edge to its nearest neighbor amongst those points that precede it in the sequence. We study the large‐sample asymptotic behavior of the total power‐weighted length of the ONG on uniform random points in (0,1)^d. In particular, for d = 1 and weight exponent α > 1/2, the limiting distribution of the centered total weight is characterized by a distributional fixed‐point equation. As an ancillary result, we give exact expressions for the expectation and variance of the standard nearest‐neighbor (directed) graph on uniform random points in the unit interval. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Optimal algorithm for the nearest common dominator problem

In a directed acyclic graph G = (V, E) with a single source s, the nearest common dominator for a set of nodes U V is the node d closest to U such that every path from s to any node in U goes through d. The distance between any node w and U is defined as the number of arcs in a shortest path from w to any node in U. We develop an optimal algorithm for finding the nearest common dominator d for U, which runs in time proportional to the number of arcs in between d and U.     

Long cycles passing through a specified path in a graph

For a graph G and an integer k ≥ 1, let ς_k(G) = d_G(v_i): {v₁, …, v_k} is an independent set of vertices in G}. Enomoto proved the following theorem. Let s ≥ 1 and let G be a (s + 2)-connected graph. Then G has a cycle of length ≥ min{|V(G)|, ς₂(G) − s} passing through any path of length s. We generalize this result as follows. Let k ≥ 3 and s ≥ 1 and let G be a (k + s − 1)-connected graph. Then G has a cycle of length ≥ min{|V(G)|, − s} passing through any path of length s. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 177–184, 1998     

Multiple Phase Transitions in Long‐Range First‐Passage Percolation on Square Lattices

We consider a model of long‐range first‐passage percolation on the d‐dimensional square lattice ?d in which any two distinct vertices x,y ? ?^d are connected by an edge having exponentially distributed passage time with mean ‖ x – y ‖^α+o(1), where α > 0 is a fixed parameter and ‖·‖ is the l¹–norm on ?^d. We analyze the asymptotic growth rate of the set ß_t, which consists of all x ? ?^d such that the first‐passage time between the origin 0 and x is at most t as t → ∞. We show that depending on the values of α there are four growth regimes: (i) instantaneous growth for α < ^d, (ii) stretched exponential growth for α ? d,2d), (iii) superlinear growth for α ? (2d,2d + 1), and finally (iv) linear growth for α > 2d + 1 like the nearest‐neighbor first‐passage percolation model corresponding to α=∞. © 2015 Wiley Periodicals, Inc.     

Defective choosability of graphs with no edge‐plus‐independent‐set minor

It is proved that, if s ≥ 2, a graph that does not have K₂ + K _s = K₁ + K_{1, s} as a minor is (s, 1)*‐choosable. This completes the proof that such a graph is (s + 1 ? d,d)*‐choosable whenever 0 ≤ d ≤ s ?1 © 2003 Wiley Periodicals, Inc. J Graph Theory 45: 51–56, 2004     

Digraphs containing every possible pair of dicycles

Let D = (V, A) be a directed graph of order n ≥ 4. Suppose that the minimum degree of D is at least (3n − 3)/2. Then for any two integers s and t with s ≥ 2, t ≥ 2 and s + t ≤ n, D contains two vertex‐disjoint directed cycles of lengths s and t, respectively. Moreover, the condition on the minimum degree is sharp. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 154–162, 2000     

Random walks on random simple graphs

This paper looks at random regular simple graphs and considers nearest neighbor random walks on such graphs. This paper considers walks where the degree d of each vertex is around (log n)^a where a is a constant which is at least 2 and where n is the number of vertices. By extending techniques of Dou, this paper shows that for most such graphs, the position of the random walk becomes close to uniformly distributed after slightly more than log n/log d steps. This paper also gets similar results for the random graph G(n, p), where p = d/(n − 1). © 1996 John Wiley & Sons, Inc.     

Hamilton cycles,avoiding prescribed arcs,in close-to-regular tournaments

The local irregularity of a digraph D is defined as i_l(D) = max {|d⁺ (x) − d⁻ (x)| : x ϵ V(D)}. Let T be a tournament, let Γ = {V₁, V₂, …, V_c} be a partition of V(T) such that |V₁| ≥ |V₂| ≥ … ≥ |V_c|, and let D be the multipartite tournament obtained by deleting all the arcs with both end points in the same set in Γ. We prove that, if |V(T)| ≥ max{2i_l(T) + 2|V₁| + 2|V₂| − 2, i_l(T) + 3|V₁| − 1}, then D is Hamiltonian. Furthermore, if T is regular (i.e., i_l(T) = 0), then we state slightly better lower bounds for |V(T)| such that we still can guarantee that D is Hamiltonian. Finally, we show that our results are best possible. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 123–136, 1999     

Optimal linear perfect hash families with small parameters

A linear (q^d, q, t)‐perfect hash family of size s consists of a vector space V of order q^d over a field F of order q and a sequence ?₁,…,?_s of linear functions from V to F with the following property: for all t subsets X ? V, there exists i ∈ {1,·,s} such that ?_i is injective when restricted to F. A linear (q^d, q, t)‐perfect hash family of minimal size d( – 1) is said to be optimal. In this paper, we prove that optimal linear (q², q, 4)‐perfect hash families exist only for q = 11 and for all prime powers q > 13 and we give constructions for these values of q. © 2004 Wiley Periodicals, Inc. J Comb Designs 12: 311–324, 2004     

Resolutions of PG(5, 2) with point‐cyclic automorphism group

A t‐(υ, k, λ) design is a set of υ points together with a collection of its k‐subsets called blocks so that all subsets of t points are contained in exactly λ blocks. The d‐dimensional projective geometry over GF(q), PG(d, q), is a 2‐(q^d + q^d−1 + … + q + 1, q + 1, 1) design when we take its points as the points of the design and its lines as the blocks of the design. A 2‐(υ, k, 1) design is said to be resolvable if the blocks can be partitioned as ℛ = {R₁, R₂, …, R_s}, where s = (υ − 1)/(k−1) and each R_i consists of υ/k disjoint blocks. If a resolvable design has an automorphism σ which acts as a cycle of length υ on the points and ℛ^σ = ℛ, then the design is said to be point‐cyclically resolvable. The design associated with PG(5, 2) is known to be resolvable and in this paper, it is shown to be point‐cyclically resolvable by enumerating all inequivalent resolutions which are invariant under a cyclic automorphism group G = 〈σ〉 where σ is a cycle of length 63. These resolutions are the only resolutions which admit a point‐transitive automorphism group. Furthermore, some necessary conditions for the point‐cyclic resolvability of 2‐(υ, k, 1) designs are also given. © 2000 John Wiley & Sons, Inc. J Combin Designs 8: 2–14, 2000     

Fan‐type theorem for path‐connectivity

For a connected noncomplete graph G, let μ(G):=min{max {d_G(u), d_G(v)}:d_G(u, v)=2}. A well‐known theorem of Fan says that every 2‐connected noncomplete graph has a cycle of length at least min{|V(G)|, 2μ(G)}. In this paper, we prove the following Fan‐type theorem: if G is a 3‐connected noncomplete graph, then each pair of distinct vertices of G is joined by a path of length at least min{|V(G)|?1, 2μ(G)?2}. As consequences, we have: (i) if G is a 3‐connected noncomplete graph with , then G is Hamilton‐connected; (ii) if G is a (s+2)‐connected noncomplete graph, where s≥1 is an integer, then through each path of length s of G there passes a cycle of length≥min{|V(G)|, 2μ(G)?s}. Several results known before are generalized and a conjecture of Enomoto, Hirohata, and Ota is proved. © 2002 Wiley Periodicals, Inc. J Graph Theory 39: 265–282, 2002 DOI 10.1002/jgt.10028     

From regular boundary graphs to antipodal distance-regular graphs

Let Γ be a regular graph with n vertices, diameter D, and d + 1 different eigenvalues λ > λ₁ > ··· > λ_d. In a previous paper, the authors showed that if P(λ) > n − 1, then D ≤ d − 1, where P is the polynomial of degree d − 1 which takes alternating values ± 1 at λ₁, …, λ_d. The graphs satisfying P(λ) = n − 1, called boundary graphs, have shown to deserve some attention because of their rich structure. This paper is devoted to the study of this case and, as a main result, it is shown that those extremal (D = d) boundary graphs where each vertex have maximum eccentricity are, in fact, 2-antipodal distance-regular graphs. The study is carried out by using a new sequence of orthogonal polynomials, whose special properties are shown to be induced by their intrinsic symmetry. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 123–140, 1998     

Circuits including a given set of vertices

Let G = (V, E) be a digraph of order n, satisfying Woodall's condition ? x, y ∈ V, if (x, y) ? E, then d⁺(x) + d^?(y) ≥ n. Let S be a subset of V of cardinality s. Then there exists a circuit including S and of length at most Min(n, 2s). In the case of oriented graphs we obtain the same result under the weaker condition d⁺(x) + d^?(y) ≥ n – 2 (which implies hamiltonism).     

The symmetric (2k,k)‐graphs

A noncomplete graph G is called an (n, k)‐graph if it is n‐connected and G − X is not (n − |X| + 1)‐connected for any X ⊆ V(G) with |X| ≤ k. Mader conjectured that for k ≥ 3 the graph K_{2k + 2} − (1‐factor) is the unique (2k, k)‐graph. We settle this conjecture for strongly regular graphs, for edge transitive graphs, and for vertex transitive graphs. © 2000 John Wiley & Sons, Inc. J Graph Theory 36: 35–51, 2001     

On the number of (r,r+1)‐ factors in an (r,r+1)‐factorization of a simple graph

For integers d≥0, s≥0, a (d, d+s)‐graph is a graph in which the degrees of all the vertices lie in the set {d, d+1, …, d+s}. For an integer r≥0, an (r, r+1)‐factor of a graph G is a spanning (r, r+1)‐subgraph of G. An (r, r+1)‐factorization of a graph G is the expression of G as the edge‐disjoint union of (r, r+1)‐factors. For integers r, s≥0, t≥1, let f(r, s, t) be the smallest integer such that, for each integer d≥f(r, s, t), each simple (d, d+s) ‐graph has an (r, r+1) ‐factorization with x (r, r+1) ‐factors for at least t different values of x. In this note we evaluate f(r, s, t). © 2009 Wiley Periodicals, Inc. J Graph Theory 60: 257‐268, 2009     

Long cycles passing through a specified edge in a 3-connected graph

We prove the following theorem: For a connected noncomplete graph G, let τ(G): = min{d_G(u) + d_G(v)|d_G(u, v) = 2}. Suppose G is a 3-connected noncomplete graph. Then through each edge of G there passes a cycle of length ≥ min{|V(G)|, τ (G) − 1}. © 1997 John Wiley & Sons, Inc.     

On low bound of degree sequences of spanning trees in K-edge-connected graphs

A graph G = (V, E) is k-edge-connected if for any subset E′ ⊆ E,|E′| < k, G − E′ is connected. A d_k-tree T of a connected graph G = (V, E) is a spanning tree satisfying that ∀v ∈ V, d_T(v) ≤ + α, where [·] is a lower integer form and α depends on k. We show that every k-edge-connected graph with k ≥ 2, has a d_k-tree, and α = 1 for k = 2, α = 2 for k ≥ 3. © 1998 John Wiley & Sons, Inc. J Graph Theory 28: 87–95, 1998     

Lp theory for the multidimensional aggregation equation

We consider well‐posedness of the aggregation equation ∂_tu + div(uv) = 0, v = −▿K * u with initial data in \input amssym ${\cal P}_2 {\rm (\Bbb R}^d {\rm )} \cap L^p ({\Bbb R}^d )$ in dimensions 2 and higher. We consider radially symmetric kernels where the singularity at the origin is of order |x|^α, α > 2 − d, and prove local well‐posedness in \input amssym ${\cal P}_2 { (\Bbb R}^d {\rm )} \cap L^p ({\Bbb R}^d )$ for sufficiently large p < p_s. In the special case of K(x) = |x|, the exponent p_s = d/(d = 1) is sharp for local well‐posedness in that solutions can instantaneously concentrate mass for initial data in \input amssym ${\cal P}_2 { (\Bbb R}^d {\rm )} \cap L^p ({\Bbb R}^d )$ with p < p_s. We also give an Osgood condition on the potential K(x) that guarantees global existence and uniqueness in \input amssym ${\cal P}_2 { (\Bbb R}^d {\rm )} \cap L^p ({\Bbb R}^d )$ . © 2010 Wiley Periodicals, Inc.     

Spherical functions and immanants

Let λ be an irreducible character of S_n corresponding to the partition (r,s) of n. Let A be a positive semidefinite Hermitian n × n matrix. Let d_λ (A) and per(A) be the immanants corresponding to λ and to the trivial character of S_n , respectively. A proof of the inequality dλ(A)≤λ(id)per(A) is given.     

On packing 3‐vertex paths in a graph

Let G be a connected graph and let eb(G) and λ(G) denote the number of end‐blocks and the maximum number of disjoint 3‐vertex paths Λ in G. We prove the following theorems on claw‐free graphs: (t1) if G is claw‐free and eb(G) ≤ 2 (and in particular, G is 2‐connected) then λ(G) = ⌊| V(G)|/3⌋; (t2) if G is claw‐free and eb(G) ≥ 2 then λ(G) ≥ ⌊(| V(G) | − eb(G) + 2)/3 ⌋; and (t3) if G is claw‐free and Δ^*‐free then λ(G) = ⌊| V(G) |/3⌋ (here Δ^* is a graph obtained from a triangle Δ by attaching to each vertex a new dangling edge). We also give the following sufficient condition for a graph to have a Λ‐factor: Let n and p be integers, 1 ≤ p ≤ n − 2, G a 2‐connected graph, and |V(G)| = 3n. Suppose that G − S has a Λ‐factor for every S ⊆ V(G) such that |S| = 3p and both V(G) − S and S induce connected subgraphs in G. Then G has a Λ‐factor. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 175–197, 2001