The Diameter of Sparse Random Graphs

We consider the diameter of a random graph G(n, p) for various ranges of p close to the phase transition point for connectivity. For a disconnected graph G, we use the convention that the diameter of G is the maximum diameter of its connected components. We show that almost surely the diameter of random graph G(n, p) is close to if np → ∞. Moreover if , then the diameter of G(n, p) is concentrated on two values. In general, if , the diameter is concentrated on at most 21/c₀ + 4 values. We also proved that the diameter of G(n, p) is almost surely equal to the diameter of its giant component if np > 3.6.     

The Flooding Time in Random Graphs

Based on our analysis of the hopcount of the shortest path between two arbitrary nodes in the class G _p (N) of random graphs, the corresponding flooding time is investigated. The flooding time T _N (p) is the minimum time needed to reach all other nodes from one node. We show that, after scaling, the flooding time T _N (p) converges in distribution to the two-fold convolution ^(2*) of the Gumbel distribution function (z)=exp (–e ^–z ), when the link density p _N satisfies Np _N /(log N)³ if N .     

The t-Tone Chromatic Number of Random Graphs

A proper 2-tone k-coloring of a graph is a labeling of the vertices with elements from \({\binom{[k]}{2}}\) such that adjacent vertices receive disjoint labels and vertices distance 2 apart receive distinct labels. The 2-tone chromatic number of a graph G, denoted τ ₂(G) is the smallest k such that G admits a proper 2-tone k coloring. In this paper, we prove that w.h.p. for \({p\geq Cn^{-1/4} {\rm ln}^{9/4}n, \tau_2(G_{n, p}) = (2 + o(1))\chi(G_{n, p})}\) where \({\chi}\) represents the ordinary chromatic number. For sparse random graphs with p = c/n, c constant, we prove that \({\tau_2(G_{n, p}) = \lceil{({\sqrt{8\Delta + 1} + 5})/{2}}}\) where Δ represents the maximum degree. For the more general concept of t-tone coloring, we achieve similar results.     

随机图的广义3-连通度

图的广义连通度的概念是由Chartrand等人引入的.令S表示图G的一个非空顶点集,κ(S)表示图G中连结S的内部不交树的最大数目.那么,对任意一个满足2≤r≤n的整数r,定义G的广义r-连通度为所有κ(S)中的最小值,其中S取遍G的顶点集合的r-元子集.显然,κ_2(G)=κ(G),即为图G的顶点连通度.所以广义连通度是经典连通度的一个自然推广.本文研究了随机图的广义3-连通度,证明了对任一给定的整数k,k≥1,p=(log n+(k+1)log long n-log lon logn)/n是关于性质κ_3(G(n,p))≥k的紧阈值函数.我们得到的结果可以看作是Bollobas和Thomason给出的关于经典连通度结果的推广.     

Circular Chromatic Indices of Regular Graphs

The circular chromatic index of a graph G, written , is the minimum r permitting a function such that whenever e and are adjacent. It is known that for any , there is a 3‐regular simple graph G with . This article proves the following results: Assume is an odd integer. For any , there is an n‐regular simple graph G with . For any , there is an n‐regular multigraph G with .     

Generating Random Regular Graphs

Random regular graphs play a central role in combinatorics and theoretical computer science. In this paper, we analyze a simple algorithm introduced by Steger and Wormald [10] and prove that it produces an asymptotically uniform random regular graph in a polynomial time. Precisely, for fixed d and n with d = O(n^1/3−ε), it is shown that the algorithm generates an asymptotically uniform random d-regular graph on n vertices in time O(nd²). This confirms a conjecture of Wormald. The key ingredient in the proof is a recently developed concentration inequality by the second author. The algorithm works for relatively large d in practical (quadratic) time and can be used to derive many properties of uniform random regular graphs. * Research supported in part by grant RB091G-VU from UCSD, by NSF grant DMS-0200357 and by an A. Sloan fellowship.     

Infinite Random Geometric Graphs

We introduce a new class of countably infinite random geometric graphs, whose vertices V are points in a metric space, and vertices are adjacent independently with probability p ? (0, 1){p \in (0, 1)} if the metric distance between the vertices is below a given threshold. For certain choices of V as a countable dense set in \mathbbRⁿ{\mathbb{R}^n} equipped with the metric derived from the L _∞-norm, it is shown that with probability 1 such infinite random geometric graphs have a unique isomorphism type. The isomorphism type, which we call GR _n , is characterized by a geometric analogue of the existentially closed adjacency property, and we give a deterministic construction of GR _n . In contrast, we show that infinite random geometric graphs in \mathbbR²{\mathbb{R}^{2}} with the Euclidean metric are not necessarily isomorphic.     

随机图的谱矩

简单图G的k阶谱矩定义为G的特征值的k阶幂之和,记为Mk(G).应用概率和代数的方法,对于几乎所有的图G,本文给出Mk(G)的一个精确估计.此外,对于几乎所有的多部图G,本文给出了Mk(G)的上界和下界.     

2-外平面图的无圈边色数

一个图G的无圈边染色是一个止常的边染色使得其不产生双色圈．Alon,Sudakov和Zaks（2001）猜想：每一个简单图G是无到（△（G）＋2）-边可染的,其中△（G）是G的最大度．本文对2-外平面图族证明了该猜想成立．     

Computation of Topological Indices of Some Graphs

Let G=(V,E) be a simple connected graph with vertex set V and edge set E. The Wiener index of G is defined by W(G)=∑_{x,y}⊆V d(x,y), where d(x,y) is the length of the shortest path from x to y. The Szeged index of G is defined by Sz(G)=∑ _e=uv∈E n _u (e|G)n _v (e|G), where n _u (e|G) (resp. n _v (e|G)) is the number of vertices of G closer to u (resp. v) than v (resp. u). The Padmakar–Ivan index of G is defined by PI(G)=∑ _e=uv∈E [n _eu (e|G)+n _ev (e|G)], where n _eu (e|G) (resp. n _ev (e|G)) is the number of edges of G closer to u (resp. v) than v (resp. u). In this paper we find the above indices for various graphs using the group of automorphisms of G. This is an efficient method of finding these indices especially when the automorphism group of G has a few orbits on V or E. We also find the Wiener indices of a few graphs which frequently arise in mathematical chemistry using inductive methods.     

Random Matchings in Regular Graphs

d -regular graph G, let M be chosen uniformly at random from the set of all matchings of G, and for let be the probability that M does not cover x. We show that for large d, the 's and the mean μ and variance of are determined to within small tolerances just by d and (in the case of μ and ) : Theorem. For any d-regular graph G, (a) , so that , (b) , where the rates of convergence depend only on d. Received: April 12, 1996     

On the Edge-forwarding Indices of Frobenius Graphs

A G-Frobenius graph F, as defined by Fang, Li, and Praeger, is a connected orbital graph of a Frobenius group G = K × H with Frobenius kernel K and Frobenius complement H. F is also shown to be a Cayley graph, F = Cay（K, S） for K and some subset S of the group K. On the other hand, a network N with a routing function R, written as （N, R）, is an undirected graph N together with a routing R which consists of a collection of simple paths connecting every pair of vertices in the graph. The edge-forwarding index π（N） of a network （N, R）, defined by Heydemann, Meyer, and Sotteau, is a parameter to describe tile maximum load of edges of N. In this paper, we study the edge-forwarding indices of Frobenius graphs. In particular, we obtain the edge-forwarding index of a G-Frobenius graph F with rank（G） ≤ 50.     

Random Motion on Simple Graphs

Consider a stochastic process that lives on n-semiaxes joined at the origin. On each ray it behaves as one dimensional Brownian Motion and at the origin it chooses a ray uniformly at random (Kirchhoff condition). The principal results are the computation of the exit probabilities and certain other probabilistic quantities regarding exit and occupation times.     

随机映射图的连接概率

本文将计算随机映射图的给定顶点集的任意分类的连接概率及其极限性质,导出随机映射图的连通分支个数的分布与渐进分布．     

随机映射图的局部图

讨论了当n趋向无穷大时,n个顶点的随机映射图的k-局部图收敛于随机生长过程时刻k的二叉图,这儿,k-局部图足随机映射图前k个顶点{1,2,…,k}所生成的最小图.在这种意义下,称随机映射图为渐近二叉的.     

随机映射图的局部图

讨论了当n趋向无穷大时,n个顶点的随机映射图的k-局部图收敛于随机生长过程时刻k的二叉图,这儿,k-局部图是随机映射图前k个顶点{1,2,…,k}所生成的最小图.在这种意义下,称随机映射图为渐近二叉的.     

Distance-2-Matchings of Random Graphs

In this paper we study the maximal size of a distance-2-matching in a random graph G _n;M , i.e., the probability space consisting of subgraphs of the complete graph over n vertices, K _n , having exactly M edges and uniform probability measure. A distance-2-matching in a graph Y, M ₂, is a set of Y-edges with the property that for any two elements every pair of their 4 incident vertices has Y-distance 2. Let M₂(Y) be the maximal size of a distance-2-matching in Y. Our main results are the derivation of a lower bound for M₂(Y) and a sharp concentration result for the random variable AMS Subject Classification: 05C80, 05C70.     

通过增强型萨格勒布指数对图排序

Recently, Furtula et al. proposed a valuable predictive index in the study of the heat of formation in octanes and heptanes, the augmented Zagreb index(AZI index) of a graph G, which is defined as AZI(G) =∑uv∈E(G)( d_u d_v/d_u + d_v-2)~3,where E(G) is the edge set of G, d u and d v are the degrees of the terminal vertices u and v of edge uv, respectively. In this paper, we obtain the first five largest(resp., the first two smallest) AZI indices of connected graphs with n vertices. Moreover, we determine the trees of order n with the first three smallest AZI indices, the unicyclic graphs of order n with the minimum, the second minimum AZI indices, and the bicyclic graphs of order n with the minimum AZI index, respectively.