Resilience of perfect matchings and Hamiltonicity in random graph processes

Let {G_i} be the random graph process: starting with an empty graph G₀ with n vertices, in every step i ≥ 1 the graph G_i is formed by taking an edge chosen uniformly at random among the nonexisting ones and adding it to the graph G_{i ? 1}. The classical “hitting‐time” result of Ajtai, Komlós, and Szemerédi, and independently Bollobás, states that asymptotically almost surely the graph becomes Hamiltonian as soon as the minimum degree reaches 2, that is if δ(G_i) ≥ 2 then G_i is Hamiltonian. We establish a resilience version of this result. In particular, we show that the random graph process almost surely creates a sequence of graphs such that for edges, the 2‐core of the graph G_m remains Hamiltonian even after an adversary removes ‐fraction of the edges incident to every vertex. A similar result is obtained for perfect matchings.     

A random tree model associated with random graphs

Grow a tree on n vertices by starting with no edges and successively adding an edge chosen uniformly from the set of possible edges whose addition would not create a cycle. This process is closely related to the classical random graph process. We describe the asymptotic structure of the tree, as seen locally from a given vertex. In particular, we give an explicit expression for the asymptotic degree distribution. Our results an be applied to study the random minimum-weight spanning tree question, when the edge-weight distribution is allowed to vary almost arbitrarily with n.     

The Greedy Independent Set in a Random Graph with Given Degrees

We analyse the size of an independent set in a random graph on n vertices with specified vertex degrees, constructed via a simple greedy algorithm: order the vertices arbitrarily, and, for each vertex in turn, place it in the independent set unless it is adjacent to some vertex already chosen. We find the limit of the expected proportion of vertices in the greedy independent set as (the jamming constant), expressed as an integral whose upper limit is defined implicitly, valid whenever the second moment of a random vertex degree is uniformly bounded. We further show that the random proportion of vertices in the independent set converges in probability to the jamming constant as . The results hold under weaker assumptions in a random multigraph with given degrees constructed via the configuration model. © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 51, 565–586, 2017     

A degree bound on decomposable trees

A n-vertex graph is said to be decomposable if for any partition (λ₁,…,λ_p) of the integer n, there exists a sequence (V₁,…,V_p) of connected vertex-disjoint subgraphs with |V_i|=λ_i. In this paper, we focus on decomposable trees. We show that a decomposable tree has degree at most 4. Moreover, each degree-4 vertex of a decomposable tree is adjacent to a leaf. This leads to a polynomial time algorithm to decide if a multipode (a tree with only one vertex of degree greater than 2) is decomposable. We also exhibit two families of decomposable trees: arbitrary large trees with one vertex of degree 4, and trees with an arbitrary number of degree-3 vertices.     

A contact process with a semi-infected state on the complete graph

In this paper, we are concerned with a contact process with a semi-infected state on the complete graph C_n with n vertices. Our model is a special case of a general model introduced by Schinazi in 2003. In our model, each vertex is in one of three states, namely, “healthy,” “semi-infected,” or “fully-infected.” Only fully-infected vertices can infect others. A healthy vertex becomes semi-infected when being infected while a semi-infected vertex becomes fully-infected when being further infected. Each (semi- and fully-) infected vertex becomes healthy at constant rate. Our main result shows a phase transition for the waiting time until extinction of the fully-infected vertices. Conditioned on all the vertices are fully-infected when t = 0, we show that fully-infected vertices survive for exp?{O(n)} units of time when the infection rate λ > 4 while they die out in O(log?n) units of time when λ < 4.     

A lower bound for groupies in graphs

A non-isolated vertex of a graph G is called a groupie if the average degree of the vertices connected to it is larger than or equal to the average degree of the vertices in G. An isolated vertex is a groupie only if all vertices of G are isolated. While it is well known that every graph must contain at least one groupie, the graph K_n − e contains just 2 groupie vertices for n ≥ 2. In this paper we derive a lower bound for the number of groupies which shows, in particular, that any graph with 2 or more vertices must contain at least 2 groupies. © 1996 John Wiley & Sons, Inc.     

The random binary growth model

We describe a family of models of random partial orders, called classical sequential growth models, and study a specific case, which is the simplest interesting model, called a random binary growth model. This model produces a random poset, called a random binary order, B₂, on the vertex set ? by considering each vertex n ≥ 2 in turn and placing it above 2 vertices chosen uniformly at random from the set {0,…,n ? 1} (with additional relations added to ensure transitivity). We show that B₂ has infinite dimension, almost surely. Using the differential equation method of Wormald, we can closely approximate the size of the up‐set of an arbitrary vertex. We give an upper bound on the largest vertex incomparable with vertex n, which is polynomial in n, and, using this bound, we provide an example of a poset P, such that there is a positive probability that B₂ does not contain P. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005     

Scale Free Properties of Random <Emphasis Type="Italic">k</Emphasis>-Trees

Scale free graphs have attracted attention as their non-uniform structure that can be used as a model for many social networks including the WWW and the Internet. In this paper, we propose a simple random model for generating scale free k-trees. For any fixed integer k, a k-tree consists of a generalized tree parameterized by k, and is one of the basic notions in the area of graph minors. Our model is quite simple and natural; it first picks a maximal clique of size k + 1 uniformly at random, it then picks k vertices in the clique uniformly at random, and adds a new vertex incident to the k vertices. That is, the model only makes uniform random choices twice per vertex. Then (asymptotically) the distribution of vertex degree in the resultant k-tree follows a power law with exponent 2 + 1/k, the k-tree has a large clustering coefficient, and the diameter is small. Moreover, our experimental results indicate that the resultant k-trees have extremely small diameter, proportional to o(log n), where n is the number of vertices in the k-tree, and the o(1) term is a function of k.     

Hamilton cycles in 3‐out

Let G_3‐out denote the random graph on vertex set [n] in which each vertex chooses three neighbors uniformly at random. Note that G_3‐out has minimum degree 3 and average degree 6. We prove that the probability that G_3‐out is Hamiltonian goes to 1 as n tends to infinity. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Bounds on the cover time

Consider a particle that moves on a connected, undirected graphG withn vertices. At each step the particle goes from the current vertex to one of its neighbors, chosen uniformly at random. Tocover time is the first time when the particle has visited all the vertices in the graph starting from a given vertex. In this paper, we present upper and lower bounds that relate the expected cover time for a graph to the eigenvalues of the Markov chain that describes the random walk above. An interesting consequence is that regular expander graphs have expected cover time (n logn).This research was done while this author was a postdoctoral fellow in the Department of Computer Science, Princeton University, and it was supported in part by DNR grant N00014-87-K-0467.     

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)).     

一类Y~(SG)(γλ,n)∪βS_n~G形图簇的伴随分解及其补图的色等价性

设G是m阶连同图,我们用S_n~G(n=km+1)表示把kG的每个分支的d_i度点分别与星图S_k+1的k个1度点重迭后得到的图,Y~(SG)(r_1n,n)表示把r_1S_n~G中每个分支的k度点依次与图的k度点邻接后得到的图,Y~(SG)(r_2λ_1,n)表示把τ_2Y~(SG)(τ_1n,n)中每个分支的r_1+k度点依次与图S_n~G的k度点邻接后得到的图,若k≥3,用Y~(sG)(r_kλ__(k-1),n)表示把τ_kY~(sG)(r_(k-1)λ_(k-2),n)中每个分支的τ_(k-1)+k度顶点依次与图S_n~G的k度点邻接后得到的图,这里λ_k=r_kλ_(k-1)+n.运用图的伴随多项式的性质,证明了一类新的图簇Y~(sG)(r_kλ__(k-1),n)∪β_kS_n~G的伴随多项式的因式分解定理,进而得到了这类图的补图的色等价图.     

Local and global average degree in graphs and multigraphs

A vertex v of a graph G is called groupie if the average degree t_v of all neighbors of v in G is not smaller than the average degree t_G of G. Every graph contains a groupie vertex; the problem of whether or not every simple graph on ≧2 vertices has at least two groupie vertices turned out to be surprisingly difficult. We present various sufficient conditions for a simple graph to contain at least two groupie vertices. Further, we investigate the function f(n) = max min_v (t_v/t_G), where the maximum ranges over all simple graphs on n vertices, and prove that f(n) = 1/42n + o(1). The corresponding result for multigraphs is in sharp contrast with the above. We also characterize trees in which the local average degree t_v is constant.     

Rainbow perfect matchings and Hamilton cycles in the random geometric graph

Given a graph on n vertices and an assignment of colours to the edges, a rainbow Hamilton cycle is a cycle of length n visiting each vertex once and with pairwise different colours on the edges. Similarly (for even n) a rainbow perfect matching is a collection of independent edges with pairwise different colours. In this note we show that if we randomly colour the edges of a random geometric graph with sufficiently many colours, then a.a.s. the graph contains a rainbow perfect matching (rainbow Hamilton cycle) if and only if the minimum degree is at least 1 (respectively, at least 2). More precisely, consider n points (i.e. vertices) chosen independently and uniformly at random from the unit d‐dimensional cube for any fixed . Form a sequence of graphs on these n vertices by adding edges one by one between each possible pair of vertices. Edges are added in increasing order of lengths (measured with respect to the norm, for any fixed ). Each time a new edge is added, it receives a random colour chosen uniformly at random and with repetition from a set of colours, where a sufficiently large fixed constant. Then, a.a.s. the first graph in the sequence with minimum degree at least 1 must contain a rainbow perfect matching (for even n), and the first graph with minimum degree at least 2 must contain a rainbow Hamilton cycle. © 2017 Wiley Periodicals, Inc. Random Struct. Alg., 51, 587–606, 2017     

Firefighting on a random geometric graph

LetG_λ be the graph whose vertices are points of a planar Poisson process of density λ, with vertices adjacent if they are within distance 1. A “fire” begins at some vertex and spreads to all neighbors in discrete steps; in the meantime f vertices can be deleted at each time‐step. Let f_λ be the least f such that, with probability 1, any fire on G_λ can be stopped in finite time. We show that f_λ is bounded between two linear functions of λ. The lower bound makes use of a new result concerning oriented percolation in the plane; the constant factor in the upper bound is is tight, provided a certain conjecture, for which we offer supporting evidence, is correct. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 466–477, 2015     

Critical behavior in inhomogeneous random graphs

We study the critical behavior of inhomogeneous random graphs in the so‐called rank‐1 case, where edges are present independently but with unequal edge occupation probabilities. The edge occupation probabilities are moderated by vertex weights, and are such that the degree of vertex i is close in distribution to a Poisson random variable with parameter w_i, where w_i denotes the weight of vertex i. We choose the weights such that the weight of a uniformly chosen vertex converges in distribution to a limiting random variable W. In this case, the proportion of vertices with degree k is close to the probability that a Poisson random variable with random parameter W takes the value k. We pay special attention to the power‐law case, i.e., the case where \begin{align*}{\mathbb{P}}(W\geq k)\end{align*} is proportional to k^‐(τ‐1) for some power‐law exponent τ > 3, a property which is then inherited by the asymptotic degree distribution. We show that the critical behavior depends sensitively on the properties of the asymptotic degree distribution moderated by the asymptotic weight distribution W. Indeed, when \begin{align*}{\mathbb{P}}(W > k) \leq ck^{-(\tau-1)}\end{align*} for all k ≥ 1 and some τ > 4 and c > 0, the largest critical connected component in a graph of size n is of order n^2/3, as it is for the critical Erd?s‐Rényi random graph. When, instead, \begin{align*}{\mathbb{P}}(W > k)=ck^{-(\tau-1)}(1+o(1))\end{align*} for k large and some τ∈(3,4) and c > 0, the largest critical connected component is of the much smaller order n^{(τ‐2)/(τ‐1)}. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 42, 480–508, 2013     

Hamiltonicity of random graphs produced by 2‐processes

Suppose that a random graph begins with n isolated vertices and evolves by edges being added at random, conditional upon all vertex degrees being at most 2. The final graph is usually 2‐regular, but is not uniformly distributed. Some properties of this final graph are already known, but the asymptotic probability of being a Hamilton cycle was not known. We answer this question along with some related questions about cycles arising in the process. © 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

A preferential attachment model with random initial degrees

In this paper, a random graph process {G(t)} _t≥1 is studied and its degree sequence is analyzed. Let {W _t } _t≥1 be an i.i.d. sequence. The graph process is defined so that, at each integer time t, a new vertex with W _t edges attached to it, is added to the graph. The new edges added at time t are then preferentially connected to older vertices, i.e., conditionally on G(t-1), the probability that a given edge of vertex t is connected to vertex i is proportional to d _i (t-1)+δ, where d _i (t-1) is the degree of vertex i at time t-1, independently of the other edges. The main result is that the asymptotical degree sequence for this process is a power law with exponent τ=min{τ_W,τ_P}, where τ_W is the power-law exponent of the initial degrees {W _t } _t≥1 and τ_P the exponent predicted by pure preferential attachment. This result extends previous work by Cooper and Frieze.     

On second order degree of graphs

Given a vertex v of a graph G the second order degree of v denoted as d 2(v) is defined as the number of vertices at distance 2 from v.In this paper we address the following question:What are the sufficient conditions for a graph to have a vertex v such that d2(v) ≥ d(v),where d(v) denotes the degree of v? Among other results,every graph of minimum degree exactly 2,except four graphs,is shown to have a vertex of second order degree as large as its own degree.Moreover,every K-4-free graph or every maximal planar graph is shown to have a vertex v such that d2(v) ≥ d(v).Other sufficient conditions on graphs for guaranteeing this property are also proved.     

Random walks which prefer unvisited edges: Exploring high girth even degree expanders in linear time

Let be a connected graph with vertices. A simple random walk on the vertex set of G is a process, which at each step moves from its current vertex position to a neighbouring vertex chosen uniformly at random. We consider a modified walk which, whenever possible, chooses an unvisited edge for the next transition; and makes a simple random walk otherwise. We call such a walk an edge‐process (or E‐process). The rule used to choose among unvisited edges at any step has no effect on our analysis. One possible method is to choose an unvisited edge uniformly at random, but we impose no such restriction. For the class of connected even degree graphs of constant maximum degree, we bound the vertex cover time of the E‐process in terms of the edge expansion rate of the graph G, as measured by eigenvalue gap of the transition matrix of a simple random walk on G. A vertex v is ?‐good, if any even degree subgraph containing all edges incident with v contains at least ? vertices. A graph G is ?‐good, if every vertex has the ?‐good property. Let G be an even degree ?‐good expander of bounded maximum degree. Any E‐process on G has vertex cover time This is to be compared with the lower bound on the cover time of any connected graph by a weighted random walk. Our result is independent of the rule used to select the order of the unvisited edges, which could, for example, be chosen on‐line by an adversary. As no walk based process can cover an n vertex graph in less than n – 1 steps, the cover time of the E‐process is of optimal order when . With high probability random r‐regular graphs, even, have . Thus the vertex cover time of the E‐process on such graphs is . © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 46, 36–54, 2015