Connectivity of inhomogeneous random graphs

We find conditions for the connectivity of inhomogeneous random graphs with intermediate density. Our results generalize the classical result for G(n, p), when . We draw n independent points X_i from a general distribution on a separable metric space, and let their indices form the vertex set of a graph. An edge (i, j) is added with probability , where is a fixed kernel. We show that, under reasonably weak assumptions, the connectivity threshold of the model can be determined. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 45, 408‐420, 2014     

Giant components in Kronecker graphs

Let \begin{align*}n\in\mathbb{N}\end{align*}, 0 <α,β,γ< 1. Define the random Kronecker graph K(n,α,γ,β) to be the graph with vertex set \begin{align*}\mathbb{Z}_2^n\end{align*}, where the probability that u is adjacent to v is given by p_u,v =α ^{u ? v} γ^{( 1‐u )?( 1‐v )}β^{n‐ u ? v ‐( 1‐u )?( 1‐v )}. This model has been shown to obey several useful properties of real‐world networks. We establish the asymptotic size of the giant component in the random Kronecker graph.© 2011 Wiley Periodicals, Inc. Random Struct. Alg.,2011     

Maximum acyclic and fragmented sets in regular graphs

We show that a typical d‐regular graph G of order n does not contain an induced forest with around vertices, when n ? d ? 1, this bound being best possible because of a result of Frieze and ?uczak [6]. We then deduce an affirmative answer to an open question of Edwards and Farr (see [4]) about fragmentability, which concerns large subgraphs with components of bounded size. An alternative, direct answer to the question is also given. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 149–156, 2008     

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.     

Almost all 5-regular graphs have a 3-flow

Tutte conjectured in 1972 that every 4-edge–connected graph has a nowhere-zero 3-flow. This has long been known to be equivalent to the conjecture that every 5-regular 4-edge–connected graph has an edge orientation in which every in-degree is either 1 or 4. We show that the assertion of the conjecture holds asymptotically almost surely for random 5-regular graphs. It follows that the conjecture holds for almost all 4-edge–connected 5-regular graphs.     

Spanning maximal planar subgraphs of random graphs

We study the threshold for the existence of a spanning maximal planar subgraph in the random graph G_{n, p} . We show that it is very near p = 1/n^? We also discuss the threshold for the existence of a spanning maximal outerplanar subgraph. This is very near p = 1/n^½.     

On the diameter of Kronecker graphs

We prove that a.a.s. as soon as a Kronecker graph becomes connected it has a finite diameter.     

Random Latin square graphs

In this paper we introduce new models of random graphs, arising from Latin squares which include random Cayley graphs as a special case. We investigate some properties of these graphs including their clique, independence and chromatic numbers, their expansion properties as well as their connectivity and Hamiltonicity. The results obtained are compared with other models of random graphs and several similarities and differences are pointed out. For many properties our results for the general case are as strong as the known results for random Cayley graphs and sometimes improve the previously best results for the Cayley case. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

Randomly coloring random graphs

We consider the problem of generating a coloring of the random graph ??_n,p uniformly at random using a natural Markov chain algorithm: the Glauber dynamics. We assume that there are βΔ colors available, where Δ is the maximum degree of the graph, and we wish to determine the least β = β(p) such that the distribution is close to uniform in O(n log n) steps of the chain. This problem has been previously studied for ??_n,p in cases where np is relatively small. Here we consider the “dense” cases, where np ε [ω ln n, n] and ω = ω(n) → ∞. Our methods are closely tailored to the random graph setting, but we obtain considerably better bounds on β(p) than can be achieved using more general techniques. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Countable sparse random graphs

For each irrational a, 0<a<1, a particular countable graph G is defined which mirrors the asymptotic behavior of the random graph G(n, p) with edge probability p = n^?a.     

Group connectivity in line graphs

Tutte introduced the theory of nowhere zero flows and showed that a plane graph G has a face k-coloring if and only if G has a nowhere zero A-flow, for any Abelian group A with |A|≥k. In 1992, Jaeger et al. [9] extended nowhere zero flows to group connectivity of graphs: given an orientation D of a graph G, if for any b:V(G)?A with ∑_v∈V(G)b(v)=0, there always exists a map f:E(G)?A−{0}, such that at each v∈V(G), in A, then G is A-connected. Let Z₃ denote the cyclic group of order 3. In [9], Jaeger et al. (1992) conjectured that every 5-edge-connected graph is Z₃-connected. In this paper, we proved the following.

• (i) 

  Every 5-edge-connected graph is Z3-connected if and only if every 5-edge-connected line graph is Z3-connected.

• (ii) 

  Every 6-edge-connected triangular line graph is Z3-connected.

• (iii) 

  Every 7-edge-connected triangular claw-free graph is Z3-connected.

In particular, every 6-edge-connected triangular line graph and every 7-edge-connected triangular claw-free graph have a nowhere zero 3-flow.     

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     

Extremal graphs in connectivity augmentation

Let A(n, k, t) denote the smallest integer e for which every k‐connected graph on n vertices can be made (k + t)‐connected by adding e new edges. We determine A(n, k, t) for all values of n, k, and t in the case of (directed and undirected) edge‐connectivity and also for directed vertex‐connectivity. For undirected vertex‐connectivity we determine A(n, k, 1) for all values of n and k. We also describe the graphs that attain the extremal values. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 179–193, 1999     

The thresholds for diameter 2 in random Cayley graphs

Given a group G, the model denotes the probability space of all Cayley graphs of G where each element of the generating set is chosen independently at random with probability p. In this article we show that for any and any family of groups G_k of order n_k for which , a graph with high probability has diameter at most 2 if and with high probability has diameter greater than 2 if . We also provide examples of families of graphs which show that both of these results are best possible. Of particular interest is that for some families of groups, the corresponding random Cayley graphs achieve Diameter 2 significantly faster than the Erd?s‐Renyi random graphs. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 45, 218–235, 2014     

Grids in random graphs

Threshold probabilities for the existence in a random graph on n vertices of a graph isomorphic to a given graph of order Cn and average degree at least three are investigated. In particular it is proved that the random graph G(n, p) on n vertices with edge probability contains a square grid on En/2 vertices. © 1994 John Wiley & Sons, Inc.     

关于线图和全图的原子键连通性指数

连通图G的原子键连通性(ABC)指数定义为: ABC(G)=\sum\limits_{uv\in E(G)} \sqrt{\frac{d(u)+d(v)-2}{d(u)d(v)}} , 其中E(G)为图G的边集, d(u) 和d(v)为顶点u和v的度数. 原子键连通性指数是化学图论中比较重要的连通度指数, 最近的研究表明它可以用来研究烷烃的能量信息. 给出了线图和全图的ABC指数的上界和下界, 并且证明了这些界是可达的.