On the average genus of the random graph

The generalized Petersen graph GP (n, k), n ≤ 3, 1 ≥ k < n/2 is a cubic graph with vertex-set {u_j; i ? Z_n} ∪ {v_j; i ? Z_n}, and edge-set {u_iu_i, u_iv_i, v_iv_{i+k, i?}Z_n}. In the paper we prove that (i) GP(n, k) is a Cayley graph if and only if k² ? 1 (mod n); and (ii) GP(n, k) is a vertex-transitive graph that is not a Cayley graph if and only if k² ? -1 (mod n) or (n, k) = (10, 2), the exceptional graph being isomorphic to the 1-skeleton of the dodecahedon. The proof of (i) is based on the classification of orientable regular embeddings of the n-dipole, the graph consisting of two vertices and n parallel edges, while (ii) follows immediately from (i) and a result of R. Frucht, J.E. Graver, and M.E. Watkins [“The Groups of the Generalized Petersen Graphs,” Proceedings of the Cambridge Philosophical Society, Vol. 70 (1971), pp. 211-218]. © 1995 John Wiley & Sons, Inc.     

On the average genus of a graph

Not all rational numbers are possibilities for the average genus of an individual graph. The smallest such numbers are determined, and varied examples are constructed to demonstrate that a single value of average genus can be shared by arbitrarily many different graphs. It is proved that the number 1 is a limit point of the set of possible values for average genus and that the complete graph K₄ is the only 3-connected graph whose average genus is less than 1.     

On the cycle space of a random graph

Write for the cycle space of a graph G, for the subspace of spanned by the copies of the κ‐cycle in G, for the class of graphs satisfying , and for the class of graphs each of whose edges lies in a . We prove that for every odd and , so the 's of a random graph span its cycle space as soon as they cover its edges. For κ = 3 this was shown in [6].     

On k-leaf connectivity of a random graph

We prove that, in a random graph with n vertices and N = cn log n edges, the subgraph generated by a set of all vertices of degree at least k + 1 is k-leaf connected for c > 1/4. A threshold function for k-leaf connectivity is also found.     

On the Euler genus of a 2-connected graph

The Euler genus of the surface Σ obtained from the sphere by the addition of k crosscaps and h handles is ε(Σ) = k + 2h. For a graph G, the Euler genus ε(G) of G is the smallest Euler genus among all surfaces in which G embeds. The following additivity theorem is proved.Theorem. Suppose G = H ∪ K, where H and K have exactly the vertices v and win common. Then ε(G) = min(ε(H + vw) + ε(K + vw), ε(H) + ε(K) + 2).     

On the non-orientable genus of a 2-connected graph

In earlier works, additivity theorems for the genus and Euler genus of unions of graphs at two points have been given. In this work, the analogous result for the non-orientable genus is given. If Σ is obtained from the sphere by the addition of k>0 crosscaps, define γ(Σ) to be k. For a graph G, define γ(G) to be the least element in the set {γ(Σ) | G embeds in Σ}.Theorem. Let H₁ and H₂ be connected graphs such that H₁ ∩ H₂ consists of the isolated vertices v and w. Then, for some μ ϵ −1, 0, 1, 2, γ(H₁ ∪ H₂) = γ(H₁) + γ(H₂) + μ.A formula for μ is given.     

On a random graph evolving by degrees

We consider a random (multi)graph growth process {Gm} on a vertex set [n], which is a special case of a more general process proposed by Laci Lovász in 2002. G₀ is empty, and Gm+1 is obtained from Gm by inserting a new edge e at random. Specifically, the conditional probability that e joins two currently disjoint vertices, i and j, is proportional to (di+α)(dj+α), where di, dj are the degrees of i, j in Gm, and α>0 is a fixed parameter. The limiting case α=∞ is the Erd?s-Rényi graph process. We show that whp Gm contains a unique giant component iff c:=2m/n>cα=α/(1+α), and the size of this giant is asymptotic to , where c^∗<cα is the root of . A phase transition window is proved to be contained, essentially, in [cα−An−1/3,cα+Bn−1/4], and we conjecture that 1/4 may be replaced with 1/3. For the multigraph version, {MGm}, we show that MGm is connected whp iff m?mn:=n1+α−1. We conjecture that, for α>1, mn is the threshold for connectedness of Gm itself.     

On the chromatic forcing number of a random graph

When we wish to compute lower bounds for the chromatic number χ(G) of a graph G, it is of interest to know something about the ‘chromatic forcing number’ f_χ(G), which is defined to be the least number of vertices in a subgraph H of G such that χ(H) = χ(G). We show here that for random graphs G_n,p with n vertices, f_χ(G_n,p) is almost surely at least ($\text{1}\text{2}$?ε)n, despite say the fact that the largest complete subgraph of G_n,p has only about log n vertices.     

On the total variation distance between the binomial random graph and the random intersection graph

When each vertex is assigned a set, the intersection graph generated by the sets is the graph in which two distinct vertices are joined by an edge if and only if their assigned sets have a nonempty intersection. An interval graph is an intersection graph generated by intervals in the real line. A chordal graph can be considered as an intersection graph generated by subtrees of a tree. In 1999, Karoński, Scheinerman, and Singer‐Cohen introduced a random intersection graph by taking randomly assigned sets. The random intersection graph has n vertices and sets assigned to the vertices are chosen to be i.i.d. random subsets of a fixed set M of size m where each element of M belongs to each random subset with probability p, independently of all other elements in M. In 2000, Fill, Scheinerman, and Singer‐Cohen showed that the total variation distance between the random graph and the Erdös‐Rényi graph tends to 0 for any if , where is chosen so that the expected numbers of edges in the two graphs are the same. In this paper, it is proved that the total variation distance still tends to 0 for any whenever .     

On the number of hamilton cycles in a random graph

Let a random graph G be constructed by adding random edges one by one, starting with n isolated vertices. We show that with probability going to one as n goes to infinity, when G first has minimum degree two, it has at least (log n) distinct hamilton cycles for any fixed ?>0.     

On the probability of the occurrence of a copy of a fixed graph in a random distance graph

The threshold probability of the occurrence of a copy of a balanced graph in a random distance graph is obtained. The technique used by P. Erd?s and A. Rényi for determining the threshold probability for the classical random graph could not be applied in the model under consideration. In this connection, a new method for deriving estimates of the number of copies of a balanced graph in a complete distance graph is developed.     

On the mean square displacement of a random walk on a graph

We study a relation between Ollivier’s Ricci curvature and the mean square displacement of a random walk on a graph. Also we obtain explicit formulas for the mean square displacement of random walks on regular polyhedra.     

On the chromatic number of a random subgraph of the Kneser graph

Results are obtained that substantially strengthen a previously known bound for the chromatic number of a random subgraph of the Kneser graph.     

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.     

On k‐connectivity for a geometric random graph

For n points uniformly randomly distributed on the unit cube in d dimensions, with d≥2, let ρ_n (respectively, σ_n) denote the minimum r at which the graph, obtained by adding an edge between each pair of points distant at most r apart, is k‐connected (respectively, has minimum degree k). Then P[ρ_n=σ_n]→1 as n→∞. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 15, 145–164, 1999     

On the variance of the random sphere of influence graph

We show that the variance of the number of edges in the random sphere of influence graph built on n i.i.d. sites which are uniformly distributed over the unit cube in R ^d, grows linearly with n. This is then used to establish a central limit theorem for the number of edges in the random sphere of influence graph built on a Poisson number of sites. Some related proximity graphs are discussed as well. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 14, 139–152, 1999