Random perfect matchings in regular graphs

We prove that in all regular robust expanders $G$, every edge is asymptotically equally likely contained in a uniformly chosen perfect matching $M$. We also show that given any fixed matching or spanning regular graph $N$ in $G$, the random variable $|M\cap E(N)|$ is approximately Poisson distributed. This in particular confirms a conjecture and a question due to Spiro and Surya, and complements results due to Kahn and Kim who proved that in a regular graph every vertex is asymptotically equally likely contained in a uniformly chosen matching. Our proofs rely on the switching method and the fact that simple random walks mix rapidly in robust expanders.     

Small subgraphs of random regular graphs

The main aim of this short paper is to answer the following question. Given a fixed graph H, for which values of the degree d does a random d-regular graph on n vertices contain a copy of H with probability close to one?     

Distribution of subgraphs of random regular graphs

We obtain the asymptotic distribution of the number of copies of a fixed subgraph H in a random d‐regular graph, provided H is strictly balanced and d = d(n) is chosen so that the expected number of copies of H tends to infinity (but not too quickly), and the expected number of copies sharing edges with two other copies is bounded. The proof of asymptotic normality of the distribution uses a method of factorial moments for variables with unbounded means that was recently derived by the authors. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Coedge regular graphs without 3-stars

We describe coedge regular graphs such that antineighborhoods of their vertices are coedge regular graphs with the same value of the parameterμ. As a consequence of the main theorem, we obtain a classification of coedge regular graphs without 3-stars. Translated fromMatematicheskie Zametki, Vol. 60, No. 4, pp. 495–503, October, 1996. This research was supported by the Russion Foundation for Basic Research under grants No. 93-01-01529 and No. 94-01-00802a.     

Efficient edge domination in regular graphs

An induced matching of a graph G is a matching having no two edges joined by an edge. An efficient edge dominating set of G is an induced matching M such that every other edge of G is adjacent to some edge in M. We relate maximum induced matchings and efficient edge dominating sets, showing that efficient edge dominating sets are maximum induced matchings, and that maximum induced matchings on regular graphs with efficient edge dominating sets are efficient edge dominating sets. A necessary condition for the existence of efficient edge dominating sets in terms of spectra of graphs is established. We also prove that, for arbitrary fixed p≥3, deciding on the existence of efficient edge dominating sets on p-regular graphs is NP-complete.     

Packing vertices and edges in random regular graphs

In this paper we consider the problem of finding large collections of vertices and edges satisfying particular separation properties in random regular graphs of degree r, for each fixed r ≥ 3. We prove both constructive lower bounds and combinatorial upper bounds on the maximal sizes of these sets. The lower bounds are proved by analyzing a class of algorithms that return feasible solutions for the given problems. The analysis uses the differential equation method proposed by Wormald [Lectures on Approximation and Randomized Algorithms, PWN, Wassaw, 1999, pp. 239–298]. The upper bounds are proved by direct combinatorial means. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

A note on regular Ramsey graphs

We prove that there is an absolute constant C>0 so that for every natural n there exists a triangle‐free regular graph with no independent set of size at least \({{C}}\sqrt{{{n}}\log{{n}}}\). © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 244–249, 2010     

5-chromatic strongly regular graphs

In this paper, we begin the determination of all primitive strongly regular graphs with chromatic number equal to 5. Using eigenvalue techniques, we show that there are at most 43 possible parameter sets for such a graph. For each parameter set, we must decide which strongly regular graphs, if any, possessing the set are 5-chromatic. In this way, we deal completely with 34 of these parameter sets using eigenvalue techniques and computer enumerations.     

Modularity in random regular graphs and lattices

Given a graph G, the modularity of a partition of the vertex set measures the extent to which edge density is higher within parts than between parts; and the modularity of G is the maximum modularity of a partition.We give an upper bound on the modularity of r-regular graphs as a function of the edge expansion (or isoperimetric number) under the restriction that each part in our partition has a sub-linear numbers of vertices. This leads to results for random r-regular graphs. In particular we show the modularity of a random cubic graph partitioned into sub-linear parts is almost surely in the interval (0.66, 0.88).The modularity of a complete rectangular section of the integer lattice in a fixed dimension was estimated in Guimer et. al. [R. Guimerà, M. Sales-Pardo and L.A. Amaral, Modularity from fluctuations in random graphs and complex networks, Phys. Rev. E 70 (2) (2004) 025101]. We extend this result to any subgraph of such a lattice, and indeed to more general graphs.     

Embedding arbitrary finite simple graphs into small strongly regular graphs

It is well known that any finite simple graph Γ is an induced subgraph of some exponentially larger strongly regular graph Γ (e.g., [2, 8]). No general polynomial‐size construction has been known. For a given finite simple graph Γ on υ vertices, we present a construction of a strongly regular graph Γ on O(υ⁴) vertices that contains Γ as its induced subgraph. A discussion is included of the size of the smallest possible strongly regular graph with this property. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 1–8, 2000     

Smallest close to regular bipartite graphs without an almost perfect matching

A graph G is close to regular or more precisely a （d, d ＋ k）-graph, if the degree of each vertex of G is between d and d ＋ k. Let d ≥ 2 be an integer, and let G be a connected bipartite （d, d＋k）-graph with partite sets X and Y such that ｜X｜- ｜Y｜＋1. If G is of order n without an almost perfect matching, then we show in this paper that·n ≥ 6d ＋7 when k = 1,·n ≥ 4d＋ 5 when k = 2,·n ≥ 4d＋3 when k≥3.Examples will demonstrate that the given bounds on the order of G are the best possible.     

Retarded regular graphs are regular or semiregular

A graph G is said to be retarded regular if there is a positive integral number s such that the number of walks of length s starting at vertices of G is a constant function. Regular and semiregular graphs are retarded regular with s?=?1 and s\!≤ \!2, respectively. We prove that any retarded regular connected graph is either regular or semiregular.     

Highly connected multicoloured subgraphs of multicoloured graphs

Suppose the edges of the complete graph on n vertices, E(K_n), are coloured using r colours; how large a k-connected subgraph are we guaranteed to find, which uses only at most s of the colours? This question is due to Bollobás, and the case s=1 was considered in Liu et al. [Highly connected monochromatic subgraphs of multicoloured graphs, J. Graph Theory, to appear]. Here we shall consider the case s2, proving in particular that when s=2 and r+1 is a power of 2 then the answer lies between 4n/(r+1)-17kr(r+2k+1) and 4n/(r+1)+4, that if r=2s+1 then the answer lies between and , and that phase transitions occur at s=r/2 and . We shall also mention some of the more glaring open problems relating to this question.     

New conjectures on perfect matchings in cubic graphs

We propose three new conjectures on perfect matchings in cubic graphs. The weakest conjecture is implied by a well-known conjecture of Berge and Fulkerson. The other two conjectures are a strengthening of the first one. All conjectures are trivially verified for 3-edge-colorable cubic graphs and by computer for all snarks of order at most 34.