Notes on growing a tree in a graph

We study the height of a spanning tree T of a graph G obtained by starting with a single vertex of G and repeatedly selecting, uniformly at random, an edge of G with exactly one endpoint in T and adding this edge to T.     

Quasi‐randomness of graph balanced cut properties

Quasi‐random graphs can be informally described as graphs whose edge distribution closely resembles that of a truly random graph of the same edge density. Recently, Shapira and Yuster proved the following result on quasi‐randomness of graphs. Let k ≥ 2 be a fixed integer, α₁,…,α_k be positive reals satisfying \begin{align*}\sum_{i} \alpha_i = 1\end{align*} and (α₁,…,α_k)≠(1/k,…,1/k), and G be a graph on n vertices. If for every partition of the vertices of G into sets V ₁,…,V _k of size α₁n,…,α_kn, the number of complete graphs on k vertices which have exactly one vertex in each of these sets is similar to what we would expect in a random graph, then the graph is quasi‐random. However, the method of quasi‐random hypergraphs they used did not provide enough information to resolve the case (1/k,…,1/k) for graphs. In their work, Shapira and Yuster asked whether this case also forces the graph to be quasi‐random. Janson also posed the same question in his study of quasi‐randomness under the framework of graph limits. In this paper, we positively answer their question. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

Probabilistic analysis of a parallel algorithm for finding the lexicographically first depth first search tree in a dense random graph

We describe an O((log n)²) time parallel algorithm, using n processors, for finding the lexicographically first depth first search tree in the random graph G _{n, p}, with p fixed. The problem itself is complete for P, and so is unlikely to be efficiently parallelizable always.     

On the chordality of a graph

The chordality of a graph G = (V, E) is defined as the minimum k such that we can write E = E₁ ∩ … ∩ E_k with each (V, E_i) a chordal graph. We present several results bounding the value of this generalization of boxicity. Our principal result is that the chordality of a graph is at most its tree width. In particular, series-parallel graphs have chordality at most 2. Potential strengthenings of this statement fail in that there are planar graphs with chordality 3 and series-parallel graphs with boxicity 3. © 1993 John Wiley & Sons, Inc.     

On the graph for which there is a tree as the inverse interchange graph of a local graph

Let G be a finite, connected, undirected graph without loops and multiple edges. The note modifies slightly the concept of I^–1 (T_t), the inverse interchange graph of the local graph G(T_t) defined by a reference tree t G, and considers the properties of the graph G, when I^–1(T_t) is a tree.     

Diameter of random spanning trees in a given graph

Motivated by the observation that the sparse tree‐like subgraphs in a small world graph have large diameter, we analyze random spanning trees in a given host graph. We show that the diameter of a random spanning tree of a given host graph G is between and with high probability., where c and c′ depend on the spectral gap of G and the ratio of the moments of the degree sequence. For the special case of regular graphs, this result improves the previous lower bound by Aldous by a factor of logn. Copyright © 2011 John Wiley Periodicals, Inc. J Graph Theory 69: 223–240, 2012     

Analysis of three graph parameters for random trees

We consider three basic graph parameters, the node‐independence number, the path node‐covering number, and the size of the kernel, and study their distributional behavior for an important class of random tree models, namely the class of simply generated trees, which contains, e.g., binary trees, rooted labeled trees, and planted plane trees, as special instances. We can show for simply generated tree families that the mean and the variance of each of the three parameters under consideration behave for a randomly chosen tree of size n asymptotically ～μn and ～νn, where the constants μ and ν depend on the tree family and the parameter studied. Furthermore we show for all parameters, suitably normalized, convergence in distribution to a Gaussian distributed random variable. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Local connectivity of a random graph

A graph is locally connected if for each vertex ν of degree ≧2, the subgraph induced by the vertices adjacent to ν is connected. In this paper we establish a sharp threshold function for local connectivity. Specifically, if the probability of an edge of a labeled graph of order n is p = ((3/2 +?_n) log n/n)^1/2 where ?_n = (log log n + log(3/8) + 2x)/(2 log n), then the limiting probability that a random graph is locally connected is exp(-exp(-x)).     

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)     

On the number of vertices of given degree in a random graph

This note can be treated as a supplement to a paper written by Bollobas which was devoted to the vertices of a given degree in a random graph. We determine some values of the edge probability p for which the number of vertices of a given degree of a random graph G ∈ ??(n, p) asymptotically has a normal distribution.     

Random graph orders

Let P _n be the order determined by taking a random graph G on {1, 2,..., n}, directing the edges from the lesser vertex to the greater (as integers), and then taking the transitive closure of this relation. We call such and ordered set a random graph order. We show that there exist constants c, and °, such that the expected height and set up number of P _n are sharply concentrated around cn and °n respectively. We obtain the estimates: .565<c<.610, and .034<°<.289. We also discuss the width, dimension, and first-order properties of P _n.     

What is the furthest graph from a hereditary property?

For a graph property P, the edit distance of a graph G from P, denoted E_P(G), is the minimum number of edge modifications (additions or deletions) one needs to apply to G to turn it into a graph satisfying P. What is the furthest graph on n vertices from P and what is the largest possible edit distance from P? Denote this maximal distance by ed(n,P). This question is motivated by algorithmic edge‐modification problems, in which one wishes to find or approximate the value of E_P(G) given an input graph G. A monotone graph property is closed under removal of edges and vertices. Trivially, for any monotone property, the largest edit distance is attained by a complete graph. We show that this is a simple instance of a much broader phenomenon. A hereditary graph property is closed under removal of vertices. We prove that for any hereditary graph property P, a random graph with an edge density that depends on P essentially achieves the maximal distance from P, that is: ed(n,P) = E_P(G(n,p(P))) + o(n²) with high probability. The proofs combine several tools, including strengthened versions of the Szemerédi regularity lemma, properties of random graphs and probabilistic arguments. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

How many random edges make a graph hamiltonian?

A threshold for a graph propertyQ in the scale of random graph spacesG _n,p is ap-band across which the asymptotic probability ofQ jumps from 0 to 1. We locate a sharp threshold for the property of having a hamiltonian path.     

The average Steiner distance of a graph

The average distance μ(G) of a graph G is the average among the distances between all pairs of vertices in G. For n ≥ 2, the average Steiner n-distance μ_n(G) of a connected graph G is the average Steiner distance over all sets of n vertices in G. It is shown that for a connected weighted graph G, μ_n(G) ≤ μ_k(G) + μ_n+1−k(G) where 2 ≤ k ≤ n − 1. The range for the average Steiner n-distance of a connected graph G in terms of n and |V(G)| is established. Moreover, for a tree T and integer k, 2 ≤ k ≤ n − 1, it is shown that μ_n(T) ≤ (n/k)μ_k(T) and the range for μ_n(T) in terms of n and |V(T)| is established. Two efficient algorithms for finding the average Steiner n-distance of a tree are outlined. © 1996 John Wiley & Sons, Inc.     

On the number of complementary trees in a graph

Consider a graph with no loops or multiple arcs with n+1 nodes and 2n arcs labeled a_l,…,a_n,a′_l,…,a′_n, where n ≥ 5. A spanning tree of such a graph is called complementary if it contains exactly one arc of each pair {a_i,a′_i}. The purpose of this paper is to develop a procedure for finding complementary trees in a graph, given one such tree. Using the procedure repeatedly we give a constructive proof that every graph of the above form which has one complementary tree has at least six such trees.     

Fundamental cycles and graph embeddings

In this paper, we investigate fundamental cycles in a graph G and their relations with graph embeddings. We show that a graph G may be embedded in an orientable surface with genus at least g if and only if for any spanning tree T , there exists a sequence of fundamental cycles C1, C2, . . . , C2g with C2i-1 ∩ C2i≠ф for 1≤ i ≤g. In particular, among β(G) fundamental cycles of any spanning tree T of a graph G, there are exactly 2γM (G) cycles C1, C2, . . . , C2γM (G) such that C2i-1 ∩ C2i≠ф for 1 ≤i≤γM (G), w...     

A phase transition phenomenon in a random directed acyclic graph

Let a random directed acyclic graph be defined as being obtained from the random graph G_{n, p} by orienting the edges according to the ordering of vertices. Let γ_n* be the size of the largest (reflexive, transitive) closure of a vertex. For p=c(log n)/n, we prove that, with high probability, γ_n* is asymptotic to n^c log n, 2n(log log n)/log n, and n(1−1/c) depending on whether c<1, c=1, or c>1. We also determine the limiting distribution of the first vertex closure in all three ranges of c. As an application, we show that the expected number of comparable pairs is asymptotic to n^1+c/c log n, ½(n(log log n)/log n)², and ½(n(1−1/c))², respectively. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 164–184, 2001     

Vertices of given degree in a random graph

This paper concerns the degree sequence d₁ ≥ d₂ ≥ … ≥ d_n of a randomly labeled graph of order n in which the probability of an edge is p(n) ≦ 1/2. Among other results the following questions are answered. What are the values of p(n) for which d₁, the maximum degree, is the same for almost every graph? For what values of p(n) is it true that d₂ > d₂ for almost every graph, that is, there is a unique vertex of maximum degree? The answers are (essentially) p(n) = o(logn/n/n) and p(n)n/logn → ∞. Also included is a detailed study of the distribution of degrees when 0 < lim n p(n)/log n ≦ lim n p(n)/log n < ∞.