Spanning trees in randomly perturbed graphs

A classical result of Komlós, Sárközy, and Szemerédi states that every n‐vertex graph with minimum degree at least (1/2 + o(1))n contains every n‐vertex tree with maximum degree . Krivelevich, Kwan, and Sudakov proved that for every n‐vertex graph G_α with minimum degree at least αn for any fixed α > 0 and every n‐vertex tree T with bounded maximum degree, one can still find a copy of T in G_α with high probability after adding O(n) randomly chosen edges to G_α. We extend the latter results to trees with (essentially) unbounded maximum degree; for a given and α > 0, we determine up to a constant factor the number of random edges that we need to add to an arbitrary n‐vertex graph with minimum degree αn in order to guarantee with high probability a copy of any fixed n‐vertex tree with maximum degree at most Δ.     

Domination Graphs with Nontrivial Components

 A tournament is an oriented complete graph. Vertices x and y dominate a tournament T if for all vertices z≠x,y, either (x,z) or (y,z) are arcs in T (possibly both). The domination graph of a tournament T is the graph on the vertex set of T containing edge {x,y} if and only if x and y dominate T. In this paper we determine which graphs containing no isolated vertices are domination graphs of tournaments. Received: May 20, 1998 Final version received: May 26, 1999     

Finding Scores in Tournaments

A tournamentT_nis an orientation of the complete graph onnvertices. We continue the algorithmic study initiated by10of recognizing various directed trees in tournaments. Hell and Rosenfeld studied the complexity of finding various oriented paths in tournaments by probing edge directions. Here, we investigate the complexity of finding a vertex of prescribed outdegree (or indegree) in the same model. We show that the complexity of finding a vertex of outdegreek( ≤ (n − 1)/2) inT_nis Θ(nk). This bound is in sharp contrast to the Θ(n) bound for selection in the case of transitive tournaments. We also establish tight bounds for finding vertices of prescribed degree from the adjacency matrix of general directed/undirected graphs. These bounds generalize the classical bound of11for finding a sink (a vertex of outdegree 0 and indegreen − 1) in a directed graph.     

Random lifts of graphs: Independence and chromatic number

For a graph G, a random n‐lift of G has the vertex set V(G)×[n] and for each edge [u, v] ∈ E(G), there is a random matching between {u}×[n] and {v}×[n]. We present bounds on the chromatic number and on the independence number of typical random lifts, with G fixed and n→∞. For the independence number, upper and lower bounds are obtained as solutions to certain optimization problems on the base graph. For a base graph G with chromatic number χ and fractional chromatic number χ_f, we show that the chromatic number of typical lifts is bounded from below by const ? and also by const ? χ_f/log²χ_f (trivially, it is bounded by χ from above). We have examples of graphs where the chromatic number of the lift equals χ almost surely, and others where it is a.s. O(χ/logχ). Many interesting problems remain open. © 2002 John Wiley & Sons, Inc. Random Struct. Alg., 20, 1–22, 2002     

Ramsey Theory and Bandwidth of Graphs

 The bandwidth of a graph is the minimum, over vertex labelings with distinct integers, of the maximum difference between labels on adjacent vertices. Kuang and McDiarmid proved that almost all n-vertex graphs have bandwidth . Thus the sum of the bandwidths of a graph and its complement is almost always at least ; we prove that it is always at most 2n−4 log ₂ n+o(log n). The proofs involve improving the bounds on the Ramsey and Turán numbers of the “halfgraph”. Received: September 2, 1998?Final version received: November 29, 1999     

Hamiltonian graphs involving distances

Let G be a graph of order n. We show that if G is a 2-connected graph and max{d(u), d(v)} + |N(u) U N(v)| ≥ n for each pair of vertices u, v at distance two, then either G is hamiltonian or G ?3K_n/3 U T₁ U T₂, where n ? O (mod 3), and T₁ and T₂ are the edge sets of two vertex disjoint triangles containing exactly one vertex from each K_n/3. This result generalizes both Fan's and Lindquester's results as well as several others.     

Semi‐random graph process

We introduce and study a novel semi‐random multigraph process, described as follows. The process starts with an empty graph on n vertices. In every round of the process, one vertex v of the graph is picked uniformly at random and independently of all previous rounds. We then choose an additional vertex (according to a strategy of our choice) and connect it by an edge to v. For various natural monotone increasing graph properties , we prove tight upper and lower bounds on the minimum (extended over the set of all possible strategies) number of rounds required by the process to obtain, with high probability, a graph that satisfies . Along the way, we show that the process is general enough to approximate (using suitable strategies) several well‐studied random graph models.     

Modularity of Erdős‐Rényi random graphs

For a given graph G, each partition of the vertices has a modularity score, with higher values indicating that the partition better captures community structure in G. The modularity q^?(G) of the graph G is defined to be the maximum over all vertex partitions of the modularity score, and satisfies 0 ≤ q^?(G)<1. Modularity is at the heart of the most popular algorithms for community detection. We investigate the behaviour of the modularity of the Erd?s‐Rényi random graph G_n,p with n vertices and edge‐probability p. Two key findings are that the modularity is 1+o(1) with high probability (whp) for np up to 1+o(1) and no further; and when np ≥ 1 and p is bounded below 1, it has order (np)^?1/2 whp, in accord with a conjecture by Reichardt and Bornholdt in 2006. We also show that the modularity of a graph is robust to changes in a few edges, in contrast to the sensitivity of optimal vertex partitions.     

Deterministic random walks on the integers

Jim Propp’s P-machine, also known as the ‘rotor router model’, is a simple deterministic process that simulates a random walk on a graph. Instead of distributing chips to randomly chosen neighbors, it serves the neighbors in a fixed order.We investigate how well this process simulates a random walk. For the graph being the infinite path, we show that, independent of the starting configuration, at each time and on each vertex, the number of chips on this vertex deviates from the expected number of chips in the random walk model by at most a constant c₁, which is approximately 2.29. For intervals of length L, this improves to a difference of O(logL), for the L₂ average of a contiguous set of intervals even to . All these bounds are tight.     

Small regular graphs having the same path layer matrix*

The path layer matrix of graph G contains quantitative information about all paths in G. The entry (i,j) in this matrix is the number of simple paths in G having initial vertex i and length j. Some new upper bounds for r‐regular graphs with the same path layer matrix are presented for r=4, 5, 6. © 2002 Wiley Periodicals, Inc. J Graph Theory 39: 219–221, 2002; DOI 10.1002/jgt.10005     

Circular flows of nearly Eulerian graphs and vertex‐splitting

The odd edge connectivity of a graph G, denoted by λ_o(G), is the size of a smallest odd edge cut of the graph. Let S be any given surface and ? be a positive real number. We proved that there is a function f_S(?) (depends on the surface S and lim_?→0 f_S(?)=∞) such that any graph G embedded in S with the odd‐edge connectivity at least f_S(?) admits a nowhere‐zero circular (2+?)‐flow. Another major result of the work is a new vertex splitting lemma which maintains the old edge connectivity and graph embedding. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 147–161, 2002     

Subdivisions and the chromatic index of r-graphs

Let T₂ be the graph obtained from the Petersen graph by first deleting a vertex and then contracting an edge incident to a vertex of degree two. We give a simple characterization of the graphs that contain no subdivision of T₂. This characterization is used to show that if every planar r-graph is r-edge colorable, then every r-graph with no subdivision of T₂ is r-edge colorable. © 1996 John Wiley & Sons, Inc.     

The domination and competition graphs of a tournament

Vertices x and y dominate a tournament T if for all vertices z ≠ x, y, either x beats z or y beats z. Let dom(T) be the graph on the vertices of T with edges between pairs of vertices that dominate T. We show that dom(T) is either an odd cycle with possible pendant vertices or a forest of caterpillars. While this is not a characterization, it does lead to considerable information about dom(T). Since dom(T) is the complement of the competition graph of the tournament formed by reversing the arcs of T, complementary results are obtained for the competition graph of a tournament. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 103–110, 1998     

A concentration result with application to subgraph count

Let H = (V,E) be a k ‐uniform hypergraph with a vertex set V and an edge set E. Let V _p be constructed by taking every vertex in V independently with probability p. Let X be the number of edges in E that are contained in V _p. We give a condition that guarantees the concentration of X within a small interval around its mean. The applicability of this result is demonstrated by deriving new sub‐Gaussian tail bounds for the number of copies of small complete and complete bipartite graphs in the binomial random graph. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

Cochromatic Number and the Genus of a Graph

The cochromatic number of a graph G, denoted by z(G), is the minimum number of subsets into which the vertex set of G can be partitioned so that each sbuset induces an empty or a complete subgraph of G. In this paper we introduce the problem of determining for a surface S, z(S), which is the maximum cochromatic number among all graphs G that embed in S. Some general bounds are obtained; for example, it is shown that if S is orientable of genus at least one, or if S is nonorientable of genus at least four, then z(S) is nonorientable of genus at least four, then z(S)≤χ(S). Here χ(S) denotes the chromatic number S. Exact results are obtained for the sphere, the Klein bottle, and for S. It is conjectured that z(S) is equal to the maximum n for which the graph G_n = K₁ ∪ K₂ ∪ … ∪ K_n embeds in S.     

Signed 2-independence in graphs

A function f : V→{−1,1} defined on the vertices of a graph G=(V,E) is a signed 2-independence function if the sum of its function values over any closed neighbourhood is at most one. That is, for every vV, f(N[v])1, where N[v] consists of v and every vertex adjacent to v. The weight of a signed 2-independence function is f(V)=∑f(v), over all vertices vV. The signed 2-independence number of a graph G, denoted α_s²(G), equals the maximum weight of a signed 2-independence function of G. In this paper, we establish upper bounds for α_s²(G) in terms of the order and size of the graph, and we characterize the graphs attaining these bounds. For a tree T, upper and lower bounds for α_s²(T) are established and the extremal graphs characterized. It is shown that α_s²(G) can be arbitrarily large negative even for a cubic graph G.     

Random graph orders

Let P _n be the order determined by taking a random graph G on {1, 2,..., n}, directing the edges from the lesser vertex to the greater (as integers), and then taking the transitive closure of this relation. We call such and ordered set a random graph order. We show that there exist constants c, and °, such that the expected height and set up number of P _n are sharply concentrated around cn and °n respectively. We obtain the estimates: .565<c<.610, and .034<°<.289. We also discuss the width, dimension, and first-order properties of P _n.     

Vertex‐distinguishing edge colorings of random graphs

A proper edge coloring of a simple graph G is called vertex‐distinguishing if no two distinct vertices are incident to the same set of colors. We prove that the minimum number of colors required for a vertex‐distinguishing coloring of a random graph of order n is almost always equal to the maximum degree Δ(G) of the graph. © 2002 John Wiley & Sons, Inc. Random Struct. Alg., 20, 89–97, 2002     

Some extremal results in cochromatic and dichromatic theory

For a graph G, the cochromatic number of G, denoted z(G), is the least m for which there is a partition of the vertex set of G having order m. where each part induces a complete or empty graph. We show that if {G_n} is a family of graphs where G_n has o(n² log²(n)) edges, then z(G_n) = o(n). We turn our attention to dichromatic numbers. Given a digraph D, the dichromatic number of D is the minimum number of parts the vertex set of D must be partitioned into so that each part induces an acyclic digraph. Given an (undirected) graph G, the dichromatic number of G, denoted d(G), is the maximum dichromatic number of all orientations of G. Let m be an integer; by d(m) we mean the minimum size of all graphs G where d(G) = m. We show that d(m) = θ(m² ln²(m)).     

The diameter of paired-domination vertex critical graphs

In this paper we continue the study of paired-domination in graphs introduced by Haynes and Slater (Networks 32 (1998), 199–206). A paired-dominating set of a graph G with no isolated vertex is a dominating set of vertices whose induced subgraph has a perfect matching. The paired-domination number of G, denoted by γ _pr(G), is the minimum cardinality of a paired-dominating set of G. The graph G is paired-domination vertex critical if for every vertex v of G that is not adjacent to a vertex of degree one, γ _pr(G − v) < γ _pr(G). We characterize the connected graphs with minimum degree one that are paired-domination vertex critical and we obtain sharp bounds on their maximum diameter. We provide an example which shows that the maximum diameter of a paired-domination vertex critical graph is at least 3/2 (γ _pr(G) − 2). For γ _pr(G) ⩽ 8, we show that this lower bound is precisely the maximum diameter of a paired-domination vertex critical graph. The first author was supported in part by the South African National Research Foundation and the University of KwaZulu-Natal, the second author was supported by the Natural Sciences and Engineering Research Council of Canada.