The diameter of randomly perturbed digraphs and some applications

The central observation of this paper is that if εn random arcs are added to any n‐node strongly connected digraph with bounded degree then the resulting graph has diameter 𝒪(lnn) with high probability. We apply this to smoothed analysis of algorithms and property testing. Smoothed Analysis: Recognizing strongly connected digraphs is a basic computational task in graph theory. Even for digraphs with bounded degree, it is NL‐complete. By XORing an arbitrary bounded degree digraph with a sparse random digraph R ∼ 𝔻_n,ε/n we obtain a “smoothed” instance. We show that, with high probability, a log‐space algorithm will correctly determine if a smoothed instance is strongly connected. We also show that if NL ⫅̸ almost‐L then no heuristic can recognize similarly perturbed instances of (s,t)‐connectivity. Property Testing: A digraph is called k‐linked if, for every choice of 2k distinct vertices s₁,…,s_k,t₁,…,t_k, the graph contains k vertex disjoint paths joining s_r to t_r for r = 1,…,k. Recognizing k‐linked digraphs is NP‐complete for k ≥ 2. We describe a polynomial time algorithm for bounded degree digraphs, which accepts k‐linked graphs with high probability, and rejects all graphs that are at least εn arcs away from being k‐linked. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

Digraphs with real and gaussian spectra

The conventional binary operations of cartesian product, conjunction, and composition of two digraphs D₁ and D₂ are observed to give the sum, the product, and a more complicated combination of the spectra of D₁ and D₂ as the resulting spectrum. These formulas for analyzing the spectrum of a digraph are utilized to construct for any positive integer n, a collection of n nonisomorphic strong regular nonsymmetric digraphs with real spectra. Further, an infinite collection of strong nonsymmetric digraphs with nonzero gaussian integer value is found. Finally, for any n, it is shown that there are n cospectral strong nonsymmetric digraphs with integral spectra.     

The scaling window of the 2‐SAT transition

We consider the random 2‐satisfiability (2‐SAT) problem, in which each instance is a formula that is the conjunction of m clauses of the form x∨y, chosen uniformly at random from among all 2‐clauses on n Boolean variables and their negations. As m and n tend to infinity in the ratio m/n→α, the problem is known to have a phase transition at α_c=1, below which the probability that the formula is satisfiable tends to one and above which it tends to zero. We determine the finite‐size scaling about this transition, namely the scaling of the maximal window W(n, δ)=(α_?(n,δ), α₊(n,δ)) such that the probability of satisfiability is greater than 1?δ for α<α_? and is less than δ for α>α₊. We show that W(n,δ)=(1?Θ(n^?1/3), 1+Θ(n^?1/3)), where the constants implicit in Θ depend on δ. We also determine the rates at which the probability of satisfiability approaches one and zero at the boundaries of the window. Namely, for m=(1+ε)n, where ε may depend on n as long as |ε| is sufficiently small and |ε|n^1/3 is sufficiently large, we show that the probability of satisfiability decays like exp(?Θ(nε³)) above the window, and goes to one like 1?Θ(n^?1|ε|^?3 below the window. We prove these results by defining an order parameter for the transition and establishing its scaling behavior in n both inside and outside the window. Using this order parameter, we prove that the 2‐SAT phase transition is continuous with an order parameter critical exponent of 1. We also determine the values of two other critical exponents, showing that the exponents of 2‐SAT are identical to those of the random graph. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 201–256 2001     

Bootstrap percolation on the hypercube

In the bootstrap percolation on the n-dimensional hypercube, in the initial position each of the 2ⁿ sites is occupied with probability p and empty with probability 1−p, independently of the state of the other sites. Every occupied site remains occupied for ever, while an empty site becomes occupied if at least two of its neighbours are occupied. If at the end of the process every site is occupied, we say that the (initial) position spans the hypercube. We shall show that there are constants c₁,c₂>0 such that for the probability of spanning tends to 1 as n→∞, while for the probability tends to 0. Furthermore, we shall show that for each n the transition has a sharp threshold function. J. Balogh: work was done while at The University of Memphis, USA Research supported in part by NSF grant DMS0302804 Research supported in part by NSF grant ITR 0225610 and DARPA grant F33615-01-C-1900     

Counting strongly‐connected,moderately sparse directed graphs

A sharp asymptotic formula for the number of strongly connected digraphs on n labelled vertices with m arcs, under the condition m ‐ n ? n^2/3, m = O(n), is obtained; this provides a partial solution of a problem posed by Wright back in 1977. This formula is a counterpart of a classic asymptotic formula, due to Bender, Canfield and McKay, for the total number of connected undirected graphs on n vertices with m edges. A key ingredient of their proof was a recurrence equation for the connected graphs count due to Wright. No analogue of Wright's recurrence seems to exist for digraphs. In a previous paper with Nick Wormald we rederived the BCM formula by counting first connected graphs among the graphs of minimum degree 2, at least. In this paper, using a similar embedding for directed graphs, we find an asymptotic formula, which includes an explicit error term, for the fraction of strongly‐connected digraphs with parameters m and n among all such digraphs with positive in/out‐degrees. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

Hamilton cycles in 3‐out

Let G_3‐out denote the random graph on vertex set [n] in which each vertex chooses three neighbors uniformly at random. Note that G_3‐out has minimum degree 3 and average degree 6. We prove that the probability that G_3‐out is Hamiltonian goes to 1 as n tends to infinity. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

The asymptotic distribution of leaf heights in binary trees

Let ℬ _n be the family of extended binary tress withn internal nodes and assume that eacht ∈ℬ _n has equal probability. We identify the asymptotic distribution of the height of leafi (where the leaves are enumerated from left to right) asi andn tend to infinity, such thati/n tends tox λ]0, 1[, as a Maxwell distribution. A generalization of the used combinatorial resp. probabilistic considerations is indicated.     

A new algorithm for digraph isomorphism

A new and efficient procedure for testing a pair of digraphs for isomorphism is developed. It is based on conducting a depth-first search on one of the digraphs followed by a systematic matching of edges using backtracking with very effective pruning. It is proved that for digraphs (ofn vertices) the expected time complexity of this procedure isO(n ^logn ). This theoretical result is verified empirically on more than 300 large random digraphs. This procedure is shown to be more efficient than any of the existing general isomorphism procedures.     

Quasi-transitive digraphs

A digraph is quasi-transitive if there is a complete adjacency between the inset and the outset of each vertex. Quasi-transitive digraphs are interseting because of their relation to comparability graphs. Specifically, a graph can be oriented as a quasi-transitive digraph if and only if it is a comparability graph. Quasi-transitive digraphs are also of interest as they share many nice properties of tournaments. Indeed, we show that every strongly connected quasi-transitive digraphs D on at least four vertices has two vertices v₁ and v₂ such that D – v_i is strongly connected for i = 1, 2. A result of tournaments on the existence of a pair of arc-disjoint in- and out-branchings rooted at the same vertex can also be extended to quasi-transitive digraphs. However, some properties of tournaments, like hamiltonicity, cannot be extended directly to quasi-transitive digraphs. Therefore we characterize those quasi-transitive digraphs which have a hamiltonian cycle, respectively a hamiltonian path. We show the existence of highly connected quasi-transitive digraphs D with a factor (a collection of disjoint cycles covering the vertex set of D), which have a cycle of every length 3 ≦ k ≦ |V(D)| ? 1 through every vertex and yet they are not hamiltonian. Finally we characterize pancyclic and vertex pancyclic quasi-transitive digraphs. © 1995, John Wiley & Sons, Inc.     

Exponents of two-colored digraphs

We consider the primitive two-colored digraphs whose uncolored digraph has n + s vertices and consists of one n-cycle and one (n − 3)-cycle. We give bounds on the exponents and characterizations of extremal two-colored digraphs.     

On digraphs without antidirected cycles

Let t(n) denote the greatest number of arcs in a diagraph of orders n which does not contain any antidrected cycles. We show that [16/5(n ? 1)] ≤ t(n) ≤ 1/2 (n ? 1) for n ≥ 5. Let t_r (n) denote the corresponding quantity for r-colorable digraphs. We show that [16/5(n ? 1)] ≤ t₅(n) ≤ t₆(n) ≤ 10/3(n ? 1) for n ≥ 5 and that t₄(n) = 3(n ? 1) for n ≥ 3.     

Largest planar matching in random bipartite graphs

For a distribution ?? over labeled bipartite (multi) graphs G = (W, M, E), |W| = |M| = n, let L(n) denote the size of the largest planar matching of G (here W and M are posets drawn on the plane as two ordered rows of nodes and edges are drawn as straight lines). We study the asymptotic (in n) behavior of L(n) for different distributions ??. Two interesting instances of this problem are Ulam's longest increasing subsequence problem and the longest common subsequence problem. We focus on the case where ?? is the uniform distribution over the k‐regular bipartite graphs on W and M. For k = o(n^1/4), we establish that $L(n) \slash \sqrt{kn}$ tends to 2 in probability when n → ∞. Convergence in mean is also studied. Furthermore, we show that if each of the n² possible edges between W and M are chosen independently with probability 0 < p < 1, then L(n)/n tends to a constant γ_p in probability and in mean when n → ∞. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 21: 162–181, 2002     

On Vertices of outdegree n in minimally n‐connected digraphs

Let |D| and |D|⁺_n denote the number of vertices of D and the number of vertices of outdegree n in the digraph D, respectively. It is proved that every minimally n‐connected, finite digraph D has |D|⁺_n ≥ n + 1 and that for n ≥ 2, there is a c_n > 0 such that for all minimally n‐connected, finite digraphs D. Furthermore, case n = 2 of the following conjecture is settled which says that every minimally n‐connected, finite digraph has a vertex of indegree and outdegree equal to n. © 2002 John Wiley & Sons, Inc. J Graph Theory 39: 129–144, 2002     

The asymptotic number of acyclic digraphs. I

We obtain an asymptotic formula forA _n,q , the number of digraphs withn labeled vertices,q edges and no cycles. The derivation consists of two separate parts. In the first we analyze the generating function forA _n,q so as to obtain a central limit theorem for an associated probability distribution. In the second part we show combinatorially thatA _n,q is a smooth function ofq. By combining these results, we obtain the desired asymptotic formula. Research supported by NSF under grant MCS-8300414. Research supported by NSERC under grant A4067. Research supported by NSF under grant MCS-8302282. Research supported by the Australian Department of Science and Technology under the Queen Elizabeth II Fellowship Scheme, while this author was at the University of Newcastle, Australia.     

ISOMORPHISMS OF CIRCULANT DIAGAPHS

ＩＳＯＭＯＲＰＨＩＳＭＳＯＦＣＩＲＣＵＬＡＮＴＤＩＡＧＡＰＨＳＭＥＮＧＪＩＸＩＡＮＧＡＮＤＨＵＡＮＧＱＩＯＮＧＸＩＡＮＧＡｂｓｔｒａｃｔ：ＬｅｔＳＺｎ－｛０｝．ＴｈｅｃｉｒｃｕｌａｎｔｄｉｇｒａｐｈＤＣｎ（Ｓ）ｉｓａｄｉｒｅｃｔｅｄｇｒａｐｈｗｉｔｈ...     

On the sum of all distances in a graph or digraph

The transmission of a graph or digraph G is the sum of all distances in G. Strict bounds on the transmission are collected and extended for several classes of graphs and digraphs. For example, in the class of 2-connected or 2-edge-connected graphs of order n, the maximal transmission is realized only by the cycle C_n. The independence of the transmission on the diameter or radius is shown. Remarks are also given about the NP-hardness of some related algorithmic problems.     

On Combinatorial Structures Kept Fixed by the Action of a Given Permutation

Let β be a given permutation of [n]={1,2,...,n} of type (β₁, β₂,...,β_n) (i.e., β has β₁ cycles of length i; ∑iβ₁ = n. We find (in terms of the β₁'s and bijectively) the number of endofunctions, permutations, cyclic permutations, derangements, fixed point free involutions, assemblies of octopuses, octopuses, idempotent endofunctions, rooted trees (i.e. contractions), forests of rooted trees, trees, vertebrates, relations (digraphs), symmetric relations (simple graphs), partitions, and connected endofunctions on [n], kept fixed by the natural action (byconjugation) of β. This approach leads to algorithms generating these structures.     

Homological connectivity of random k‐dimensional complexes

Let Δ_n?1 denote the (n ? 1)‐dimensional simplex. Let Y be a random k‐dimensional subcomplex of Δ_n?1 obtained by starting with the full (k ? 1)‐dimensional skeleton of Δ_n?1 and then adding each k‐simplex independently with probability p. Let H_k?1(Y; R) denote the (k ? 1)‐dimensional reduced homology group of Y with coefficients in a finite abelian group R. It is shown that for any fixed R and k ≥ 1 and for any function ω(n) that tends to infinity © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

ON ARC-TRANSITIVE CIRCULANT DIGRAPHS

Denote by c,(s)the circulant digraph with vertex set zn=[0,1,2……n-1]and symbol set s(≠-s)∈zn\[0].let x be the automorphism group of cn(S)and xo the stabilizer of o in x.then cn(S)is arctransitive if and only if xo acts transitively on s.in this paper,co(S)with xo is being the symmetric group is characterized by its symbot set .by the way all the arctransitive clcculant digraphs of degree 2are given.     

Digraphs with the path-merging property

In this paper we study those digraphs D for which every pair of internally disjoint (X, Y)-paths P₁, P₂ can be merged into one (X, Y)-path P* such that V(P₁) ∪ V(P₂), for every choice of vertices X, Y ? V(D). We call this property the path-merging property and we call a graph path-mergeable if it has the path-merging property. We show that each such digraph has a directed hamiltonian cycle whenever it can possibly have one, i.e., it is strong and the underlying graph has no cutvertex. We show that path-mergeable digraphs can be recognized in polynomial time and we give examples of large classes of such digraphs which are not contained in any previously studied class of digraphs. We also discuss which undirected graphs have path-mergeable digraph orientations. © 1995, John Wiley & Sons, Inc.