Maximum matchings in regular graphs

It was conjectured by Mkrtchyan, Petrosyan and Vardanyan that every graph $G$ with $\Delta \left(G\right)?\delta \left(G\right)\le 1$ has a maximum matching $M$ such that any two $M$-unsaturated vertices do not share a neighbor. The results obtained in Mkrtchyan et al. (2010), Petrosyan (2014) and Picouleau (2010) leave the conjecture unknown only for $k$-regular graphs with $4\le k\le 6$. All counterexamples for $k$-regular graphs $(k\ge 7)$ given in Petrosyan (2014) have multiple edges. In this paper, we confirm the conjecture for all $k$-regular simple graphs and also $k$-regular multigraphs with $k\le 4$.     

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.     

On the existence of 3-way k-homogeneous Latin trades

A $\mu$-way Latin trade of volume $s$ is a collection of $\mu$ partial Latin squares $T_1,T_2,\dots ,T_{\mu }$, containing exactly the same $s$ filled cells, such that, if cell $(i,j)$ is filled, it contains a different entry in each of the $\mu$ partial Latin squares, and such that row $i$ in each of the $\mu$ partial Latin squares contains, set-wise, the same symbols, and column $j$ likewise. It is called a $\mu$-way$k$-homogeneous Latin trade if, in each row and each column, $T_r$, for $1\le r\le \mu$, contains exactly $k$ elements, and each element appears in $T_r$ exactly $k$ times. It is also denoted as a $(\mu ,k,m)$ Latin trade, where $m$ is the size of the partial Latin squares.We introduce some general constructions for $\mu$-way $k$-homogeneous Latin trades, and specifically show that, for all $k\le m$, $6\le k\le 13$, and $k=15$, and for all $k\le m$, $k=4,5$ (except for four specific values), a $3$-way $k$-homogeneous Latin trade of volume $km$ exists. We also show that there is no $(3,4,6)$ Latin trade and there is no $(3,4,7)$ Latin trade. Finally, we present general results on the existence of $3$-way $k$-homogeneous Latin trades for some modulo classes of $m$.     

Equation-regular sets and the Fox–Kleitman conjecture

Given $k\ge 1$, the Fox–Kleitman conjecture from 2006 states that there exists a nonzero integer $b$ such that the $2k$-variable linear Diophantine equation

$\sum _{i=1}^k(x_i?y_i)=b$

is $(2k?1)$-regular. This is best possible, since Fox and Kleitman showed that for all $b\ge 1$, this equation is not $2k$-regular. While the conjecture has recently been settled for all $k\ge 2$, here we focus on the case $k=3$ and determine the degree of regularity of the corresponding equation for all $b\ge 1$. In particular, this independently confirms the conjecture for $k=3$. We also briefly discuss the case $k=4$.     

Strong vertex-magic and edge-magic labelings of 2-regular graphs of odd order using Kotzig completion

Let $G$ be a 2-regular graph with $2m+1$ vertices and assume that $G$ has a strong vertex-magic total labeling. It is shown that the four graphs $G\cup 2m{C}_3$, $G\cup (2m+2)C_3$, $G\cup m{C}_8$ and $G\cup (m+1)C_8$ also have a strong vertex-magic total labeling. These theorems follow from a new use of carefully prescribed Kotzig arrays. To illustrate the power of this technique, we show how just three of these arrays, combined with known labelings for smaller 2-regular graphs, immediately provide strong vertex-magic total labelings for 68 different 2-regular graphs of order 49.     

Locating a robber with multiple probes

We consider a game in which a cop searches for a moving robber on a connected graph using distance probes, which is a slight variation on one introduced by Seager (2012). Carragher, Choi, Delcourt, Erickson and West showed that for any $n$-vertex graph $G$ there is a winning strategy for the cop on the graph $G^{1∕m}$ obtained by replacing each edge of $G$ by a path of length $m$, if $m\ge n$ (Carragher et al., 2012). The present authors showed that, for all but a few small values of $n$, this bound may be improved to $m\ge n∕2$, which is best possible (Haslegrave et al., 2016). In this paper we consider the natural extension in which the cop probes a set of $k$ vertices, rather than a single vertex, at each turn. We consider the relationship between the value of $k$ required to ensure victory on the original graph with the length of subdivisions required to ensure victory with $k=1$. We give an asymptotically best-possible linear bound in one direction, but show that in the other direction no subexponential bound holds. We also give a bound on the value of $k$ for which the cop has a winning strategy on any (possibly infinite) connected graph of maximum degree $\Delta$, which is best possible up to a factor of $(1?o\left(1\right))$.     

Connectivity keeping stars or double-stars in 2-connected graphs

In Mader (2010), Mader conjectured that for every positive integer $k$ and every finite tree $T$ with order $m$, every $k$-connected, finite graph $G$ with $\delta \left(G\right)\ge ?\frac{3}{2}k?+m?1$ contains a subtree $T^{\prime }$ isomorphic to $T$ such that $G?V\left(T^{\prime }\right)$ is $k$-connected. In the same paper, Mader proved that the conjecture is true when $T$ is a path. Diwan and Tholiya (2009) verified the conjecture when $k=1$. In this paper, we will prove that Mader’s conjecture is true when $T$ is a star or double-star and $k=2$.     

Vertex partitions of non-complete graphs into connected monochromatic k-regular graphs

In a landmark paper, Erd?s et al. (1991) [3] proved that if $G$ is a complete graph whose edges are colored with $r$ colors then the vertex set of $G$ can be partitioned into at most $c{r}^{2}logr$ monochromatic, vertex disjoint cycles for some constant $c$. Sárközy extended this result to non-complete graphs, and Sárközy and Selkow extended it to $k$-regular subgraphs. Generalizing these two results, we show that if $G$ is a graph with independence number $\alpha \left(G\right)=\alpha$ whose edges are colored with $r$ colors then the vertex set of $G$ can be partitioned into at most ${\left(\alpha r\right)}^{c(\alpha rlog\left(\alpha r\right)+k)}$ vertex disjoint connected monochromatic$k$-regular subgraphs of $G$ for some constant $c$.