A family of regular graphs of girth 5

Murty [A generalization of the Hoffman-Singleton graph, Ars Combin. 7 (1979) 191-193.] constructed a family of (p^m+2)-regular graphs of girth five and order 2p^2m, where p?5 is a prime, which includes the Hoffman-Singleton graph [A.J. Hoffman, R.R. Singleton, On Moore graphs with diameters 2 and 3, IBM J. (1960) 497-504]. This construction gives an upper bound for the least number f(k) of vertices of a k-regular graph with girth 5. In this paper, we extend the Murty construction to k-regular graphs with girth 5, for each k. In particular, we obtain new upper bounds for f(k), k?16.     

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?     

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.     

On the girth and diameter of generalized Johnson graphs

Let $v>k>i$ be non-negative integers. The generalized Johnson graph, $J(v,k,i)$, is the graph whose vertices are the $k$-subsets of a $v$-set, where vertices $A$ and $B$ are adjacent whenever $|A\cap B|=i$. In this article, we derive general formulas for the girth and diameter of $J(v,k,i)$. Additionally, we provide a formula for the distance between any two vertices $A$ and $B$ in terms of the cardinality of their intersection.     

Finding small regular graphs of girths 6, 8 and 12 as subgraphs of cages

Small k-regular graphs of girth g where g=6,8,12 are obtained as subgraphs of minimal cages. More precisely, we obtain (k,6)-graphs on 2(kq−1) vertices, (k,8)-graphs on 2k(q²−1) vertices and (k,12)-graphs on 2kq²(q²−1), where q is a prime power and k is a positive integer such that q≥k≥3. Some of these graphs have the smallest number of vertices known so far among the regular graphs with girth g=6,8,12.     

On the girth of extremal graphs without shortest cycles

Let EX(ν;{C₃,…,C_n}) denote the set of graphs G of order ν that contain no cycles of length less than or equal to n which have maximum number of edges. In this paper we consider a problem posed by several authors: does G contain an n+1 cycle? We prove that the diameter of G is at most n−1, and present several results concerning the above question: the girth of G is g=n+1 if (i) ν≥n+5, diameter equal to n−1 and minimum degree at least 3; (ii) ν≥12, ν∉{15,80,170} and n=6. Moreover, if ν=15 we find an extremal graph of girth 8 obtained from a 3-regular complete bipartite graph subdividing its edges. (iii) We prove that if ν≥2n−3 and n≥7 the girth is at most 2n−5. We also show that the answer to the question is negative for ν≤n+1+⌊(n−2)/2⌋.     

On the excess of vertex-transitive graphs of given degree and girth

We consider a restriction of the well-known Cage Problem to the class of vertex-transitive graphs, and consider the problem of finding the smallest vertex-transitive $k$-regular graphs of girth $g$. Counting cycles to obtain necessary arithmetic conditions on the parameters $(k,g)$, we extend previous results of Biggs, and prove that, for any given excess $e$ and any given degree $k\ge 4$, the asymptotic density of the set of girths $g$ for which there exists a vertex-transitive $(k,g)$-cage with excess not exceeding $e$ is 0.     

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     

Invariant Gaussian processes and independent sets on regular graphs of large girth

We prove that every 3‐regular, n‐vertex simple graph with sufficiently large girth contains an independent set of size at least 0.4361n. (The best known bound is 0.4352n.) In fact, computer simulation suggests that the bound our method provides is about 0.438n. Our method uses invariant Gaussian processes on the d‐regular tree that satisfy the eigenvector equation at each vertex for a certain eigenvalue . We show that such processes can be approximated by i.i.d. factors provided that . We then use these approximations for to produce factor of i.i.d. independent sets on regular trees. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 284–303, 2015     

Rumor spreading on random regular graphs and expanders

Broadcasting algorithms are important building blocks of distributed systems. In this work we investigate the typical performance of the classical and well‐studied push model. Assume that initially one node in a given network holds some piece of information. In each round, every one of the informed nodes chooses independently a neighbor uniformly at random and transmits the message to it. In this paper we consider random networks where each vertex has degree d ≥ 3, i.e., the underlying graph is drawn uniformly at random from the set of all d ‐regular graphs with n vertices. We show that with probability 1 ‐ o(1) the push model broadcasts the message to all nodes within (1 + o(1))C_d lnn rounds, where Particularly, we can characterize precisely the effect of the node degree to the typical broadcast time of the push model. Moreover, we consider pseudo‐random regular networks, where we assume that the degree of each node is very large. There we show that the broadcast time is (1 + o(1))Clnn with probability 1 ‐ o(1), where \begin{align*}C = \lim_{d\to\infty}C_d = \frac{1}{\ln2} + 1\end{align*}. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

Colouring of generalized signed triangle-free planar graphs

We view an undirected graph $G$ as a symmetric digraph, where each edge $xy$ is replaced by two opposite arcs $e=(x,y)$ and $e^{?1}=(y,x)$. Assume $S$ is an inverse closed subset of permutations of positive integers. We say $G$ is $S$-$k$-colourable if for any mapping $\sigma :E\left(G\right)\to S$ with $\sigma (x,y)={\left(\sigma (y,x)\right)}^{?1}$, there is a mapping $f:V\left(G\right)\to \left[k\right]=\{1,2,\dots ,k\}$ such that ${\sigma }_e\left(f\left(x\right)\right)\ne f\left(y\right)$ for each arc $e=(x,y)$. The concept of $S$-$k$-colourable is a common generalization of several other colouring concepts. This paper is focused on finding the sets $S$ such that every triangle-free planar graph is $S$-3-colourable. Such a set $S$ is called TFP-good. Grötzsch’s theorem is equivalent to say that $S=\left\{id\right\}$ is TFP-good. We prove that for any inverse closed subset $S$ of $S_3$ which is not isomorphic to $\{id,\left(12\right)\}$, $S$ is TFP-good if and only if either $S=\left\{id\right\}$ or there exists $a\in \left[3\right]$ such that for each $\pi \in S$, $\pi \left(a\right)\ne a$. It remains an open question to determine whether or not $S=\{id,\left(12\right)\}$ is TFP-good.     

A generalization of Wallis-Fon-Der-Flaass construction of strongly regular graphs

In this paper the Wallis-Fon-Der-Flaass construction of strongly regular graphs is generalized. As a result new prolific series of strongly regular graphs are obtained. Some of them have new parameters. The author was partially supported by the Israeli Ministry of Absorption.     

Antimagic orientations of disconnected even regular graphs

A $labeling$ of a digraph $D$ with $m$ arcs is a bijection from the set of arcs of $D$ to $\{1,2,\dots ,m\}$. A labeling of $D$ is $antimagic$ if no two vertices in $D$ have the same vertex-sum, where the vertex-sum of a vertex $u\in V\left(D\right)$ for a labeling is the sum of labels of all arcs entering $u$ minus the sum of labels of all arcs leaving $u$. An orientation $D$ of a graph $G$ is $antimagic$ if $D$ has an antimagic labeling. Hefetz et al. (2010) raised the question: Does every graph admit an antimagic orientation? It had been proved that every 2$d$-regular graph with at most two odd components has an antimagic orientation. In this paper, we consider 2$d$-regular graphs with more than two odd components. We show that every 2$d$-regular graph with $k(3\le k\le 5d+4)$ odd components has an antimagic orientation. And we show that each 2$d$-regular graph with $k(k\ge 5d+5)$ odd components admits an antimagic orientation if each odd component has at least $2x_0+5$ vertices with $x_0=?\frac{k?(5d+4)}{2d?2}?$.     

On a conjecture of Brouwer involving the connectivity of strongly regular graphs

In this paper, we study a conjecture of Andries E. Brouwer from 1996 regarding the minimum number of vertices of a strongly regular graph whose removal disconnects the graph into non-singleton components.We show that strongly regular graphs constructed from copolar spaces and from the more general spaces called Δ-spaces are counterexamples to Brouwer?s Conjecture. Using J.I. Hall?s characterization of finite reduced copolar spaces, we find that the triangular graphs T(m), the symplectic graphs Sp(2r,q) over the field Fq (for any q prime power), and the strongly regular graphs constructed from the hyperbolic quadrics O⁺(2r,2) and from the elliptic quadrics O⁻(2r,2) over the field F₂, respectively, are counterexamples to Brouwer?s Conjecture. For each of these graphs, we determine precisely the minimum number of vertices whose removal disconnects the graph into non-singleton components. While we are not aware of an analogue of Hall?s characterization theorem for Δ-spaces, we show that complements of the point graphs of certain finite generalized quadrangles are point graphs of Δ-spaces and thus, yield other counterexamples to Brouwer?s Conjecture.We prove that Brouwer?s Conjecture is true for many families of strongly regular graphs including the conference graphs, the generalized quadrangles GQ(q,q) graphs, the lattice graphs, the Latin square graphs, the strongly regular graphs with smallest eigenvalue −2 (except the triangular graphs) and the primitive strongly regular graphs with at most 30 vertices except for few cases.We leave as an open problem determining the best general lower bound for the minimum size of a disconnecting set of vertices of a strongly regular graph, whose removal disconnects the graph into non-singleton components.