The Laplacian energy of random graphs

Gutman et al. introduced the concepts of energy E(G) and Laplacian energy EL(G) for a simple graph G, and furthermore, they proposed a conjecture that for every graph G, E(G) is not more than EL(G). Unfortunately, the conjecture turns out to be incorrect since Liu et al. and Stevanovi? et al. constructed counterexamples. However, So et al. verified the conjecture for bipartite graphs. In the present paper, we obtain, for a random graph, the lower and upper bounds of the Laplacian energy, and show that the conjecture is true for almost all graphs.     

Matching properties in connected domination critical graphs

A dominating set of vertices S of a graph G is connected if the subgraph G[S] is connected. Let γ_c(G) denote the size of any smallest connected dominating set in G. A graph G is k-γ-connected-critical if γ_c(G)=k, but if any edge is added to G, then γ_c(G+e)?k-1. This is a variation on the earlier concept of criticality of edge addition with respect to ordinary domination where a graph G was defined to be k-critical if the domination number of G is k, but if any edge is added to G, the domination number falls to k-1.A graph G is factor-critical if G-v has a perfect matching for every vertex v∈V(G), bicritical if G-u-v has a perfect matching for every pair of distinct vertices u,v∈V(G) or, more generally, k-factor-critical if, for every set S⊆V(G) with |S|=k, the graph G-S contains a perfect matching. In two previous papers [N. Ananchuen, M.D. Plummer, Matching properties in domination critical graphs, Discrete Math. 277 (2004) 1-13; N. Ananchuen, M.D. Plummer, 3-factor-criticality in domination critical graphs, Discrete Math. 2007, to appear [3].] on ordinary (i.e., not necessarily connected) domination, the first and third authors showed that under certain assumptions regarding connectivity and minimum degree, a critical graph G with (ordinary) domination number 3 will be factor-critical (if |V(G)| is odd), bicritical (if |V(G)| is even) or 3-factor-critical (again if |V(G)| is odd). Analogous theorems for connected domination are presented here. Although domination and connected domination are similar in some ways, we will point out some interesting differences between our new results for the case of connected domination and the results in [N. Ananchuen, M.D. Plummer, Matching properties in domination critical graphs, Discrete Math. 277 (2004) 1-13; N. Ananchuen, M.D. Plummer, 3-factor-criticality in domination critical graphs, Discrete Math. 2007, to appear [3].].     

Universality of critical behaviour in a class of recurrent random walks

Let X₀=0, X₁, X₂,.. be an aperiodic random walk generated by a sequence ₁, ₂,... of i.i.d. integer-valued random variables with common distribution p(·) having zero mean and finite variance. For anN-step trajectory and a monotone convex functionV: withV(0)=0, define Further, let be the set of all non-negative paths compatible with the boundary conditionsX₀=a, X_N=b. We discuss asymptotic properties of under the probability distribution N and 0, Z^a,b_N,+, being the corresponding normalization. If V(·) grows not faster than polynomially at infinity, define H() to be the unique solution to the equation Our main result reads that as 0, the typical height of X_[, ^N] scales as H() and the correlations along decay exponentially on the scale H()². Using a suitable blocking argument, we show that the distribution tails of the rescaled height decay exponentially with critical exponent 3/2. In the particular case of linear potential V(·), the characteristic length H() is proportional to ^-1/3 as 0.Mathematics Subject Classification (2000):60G50, 60K35; 82B27, 82B41     

The good, the bad, and the great: Homomorphisms and cores of random graphs

We consider homomorphism properties of a random graph G(n,p), where p is a function of n. A core H is great if for all e∈E(H), there is some homomorphism from H−e to H that is not onto. Great cores arise in the study of uniquely H-colourable graphs, where two inequivalent definitions arise for general cores H. For a large range of p, we prove that with probability tending to 1 as n→∞, G∈G(n,p) is a core that is not great. Further, we give a construction of infinitely many non-great cores where the two definitions of uniquely H-colourable coincide.     

Limit laws in the generalized random graphs with random vertex weights

In this note we investigate the number of edges and the vertex degree in the generalized random graphs with vertex weights, which are independent and identically distributed random variables.     

On the normal approximation for random fields via martingale methods

We prove a central limit theorem for strictly stationary random fields under a sharp projective condition. The assumption was introduced in the setting of random sequences by Maxwell and Woodroofe. Our approach is based on new results for triangular arrays of martingale differences, which have interest in themselves. We provide as applications new results for linear random fields and nonlinear random fields of Volterra-type.     

Sandpile groups and the coeulerian property for random directed graphs

We consider random directed graphs, and calculate the distribution of the cokernels of their laplacian, following the methods used by Wood. As a corollary, we show that the probability that a random digraph is coeulerian is asymptotically upper bounded by a constant around 0.43.     

On 1-uniqueness and dense critical graphs for tree-depth

The tree-depth of $G$ is the smallest value of $k$ for which a labeling of the vertices of $G$ with elements from $\{1,\dots ,k\}$ exists such that any path joining two vertices with the same label contains a vertex having a higher label. The graph $G$ is $k$-critical if it has tree-depth $k$ and every proper minor of $G$ has smaller tree-depth.Motivated by a conjecture on the maximum degree of $k$-critical graphs, we consider the property of 1-uniqueness, wherein any vertex of a critical graph can be the unique vertex receiving label 1 in an optimal labeling. Contrary to an earlier conjecture, we construct examples of critical graphs that are not 1-unique and show that 1-unique graphs can have arbitrarily many more edges than certain critical spanning subgraphs. We also show that $(n?1)$-critical graphs on $n$ vertices are 1-unique and use 1-uniqueness to show that the Andrásfai graphs are critical with respect to tree-depth.     

On the chromatic number of random graphs

In this paper we consider the classical Erdős–Rényi model of random graphs G_n,p. We show that for p=p(n)n^−3/4−δ, for any fixed δ>0, the chromatic number χ(G_n,p) is a.a.s. ℓ, ℓ+1, or ℓ+2, where ℓ is the maximum integer satisfying 2(ℓ−1)log(ℓ−1)p(n−1).     

Online Ramsey games for triangles in random graphs

In the online F-avoidance edge-coloring game with r colors, a graph on n vertices is generated by randomly adding a new edge at each stage. The player must color each new edge as it appears; the goal is to avoid a monochromatic copy of F. Let N₀(F,r,n) be the threshold function for the number of edges that the player is asymptotically almost surely able to paint before he/she loses. Even when F=K₃, the order of magnitude of N₀(F,r,n) is unknown for r≥3. In particular, the only known upper bound is the threshold function for the number of edges in the offline version of the problem, in which an entire random graph on n vertices with m edges is presented to the player to be r edge-colored. We improve the upper bound for the online triangle-avoidance game with r colors, providing the first result that separates the online threshold function from the offline bound for r≥3. This supports a conjecture of Marciniszyn, Spöhel, and Steger that the known lower bound is tight for cliques and cycles for all r.     

Duality in inhomogeneous random graphs,and the cut metric

The classical random graph model G(n, c/n) satisfies a “duality principle”, in that removing the giant component from a supercritical instance of the model leaves (essentially) a subcritical instance. Such principles have been proved for various models; they are useful since it is often much easier to study the subcritical model than to directly study small components in the supercritical model. Here we prove a duality principle of this type for a very general class of random graphs with independence between the edges, defined by convergence of the matrices of edge probabilities in the cut metric. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 39, 399–411, 2011     

Greedy approximation for the source location problem with vertex-connectivity requirements in undirected graphs

Let $G=(V,E)$ be a simple undirected graph with a set V of vertices and a set E of edges. Each vertex $v\in V$ has a demand $d(v)\in Z_{+}$, and a cost $c(v)\in R_{+}$, where $Z_{+}$ and $R_{+}$ denote the set of nonnegative integers and the set of nonnegative reals, respectively. The source location problem with vertex-connectivity requirements in a given graph G asks to find a set S of vertices minimizing ${\sum }_{v\in S}c(v)$ such that there are at least $d(v)$ pairwise vertex-disjoint paths from S to v for each vertex $v\in V?S$. It is known that the problem is not approximable within a ratio of $O(\ln {\sum }_{v\in V}d(v))$, unless NP has an $O(N^{\log \log N})$-time deterministic algorithm. Also, it is known that even if every vertex has a uniform cost and $d^1=4$ holds, then the problem is NP-hard, where $d^1=\max \{d(v)|v\in V\}$.In this paper, we consider the problem in the case where every vertex has uniform cost. We propose a simple greedy algorithm for providing a $\max \{d^1,2d^1?6\}$-approximate solution to the problem in $O(\min \{d^1,\sqrt{|V|}\}{d}^1{|V|}^2)$ time, while we also show that there exists an instance for which it provides no better than a $(d^1?1)$-approximate solution. Especially, in the case of $d^1?4$, we give a tight analysis to show that it achieves an approximation ratio of 3. We also show the APX-hardness of the problem even restricted to $d^1?4$.     

On the rate of approximation in the central limit theorem for dependent random variables and random vectors

Large “O” and small “o” approximations of the expected value of a class of smooth functions (f C^r(R)) of the normalized partial sums of dependent random variable by the expectation of the corresponding functions of normal random variables have been established. The same types of approximations are also obtained for dependent random vectors. The technique used is the Lindberg-Levy method generalized by Dvoretzky to dependent random variables.     

A critical functional framework for the inhomogeneous Navier-Stokes equations in the half-space

This paper is devoted to solving globally the boundary value problem for the incompressible inhomogeneous Navier-Stokes equations in the half-space in the case of small data with critical regularity. In dimension n?3, we state that if the initial density ρ₀ is close to a positive constant in and the initial velocity u₀ is small with respect to the viscosity in the homogeneous Besov space then the equations have a unique global solution. The proof strongly relies on new maximal regularity estimates for the Stokes system in the half-space in , interesting for their own sake.     

Some approximation methods for the distribution of random sums

This paper deals with approximation methods for the distribution of random sums, a subject being of high interest especially in actuarial mathematics (distribution of the total claim during a fixed time interval). Above all the authors intended to deliver rigid proofs for some propositions (such as Esscher and Edgeworth approximation) which are established in relevant articles frequently only in heuristic manner.     

On the cover time of random walks on graphs

This article deals with random walks on arbitrary graphs. We consider the cover time of finite graphs. That is, we study the expected time needed for a random walk on a finite graph to visit every vertex at least once. We establish an upper bound ofO(n ²) for the expectation of the cover time for regular (or nearly regular) graphs. We prove a lower bound of (n logn) for the expected cover time for trees. We present examples showing all our bounds to be tight.Mike Saks was supported by NSF-DMS87-03541 and by AFOSR-0271. Jeff Kahn was supported by MCS-83-01867 and by AFOSR-0271.