Source author record

Robert F. Bailey

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO math.GR

Catalog footprint

Research overview

12works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

On the Classification of Binary Completely Transitive Codes with Almost-Simple Top-Group

A code $C$ in the Hamming metric, that is, is a subset of the vertex set $V\varGamma$ of the Hamming graph $\varGamma=H(m,q)$ , gives rise to a natural distance partition $\{C,C_1,\ldots,C_ρ\}$ , where $ρ$ is the covering radius of $C$ . Such a code $C$ is called completely transitive if the automorphism group $\rm{Aut}(C)$ acts transitively on each of the sets $C$ , $C_1$ , \ldots, $C_ρ$ . A code $C$ is called $2$ -neighbour-transitive if $ρ\geq 2$ and $\rm{Aut}(C)$ acts transitively on each of $C$ , $C_1$ and $C_2$ . Let $C$ be a completely transitive code in a binary ( $q=2$ ) Hamming graph having full automorphism group $\rm{Aut}(C)$ and minimum distance $δ\geq 5$ . Then it is known that $\rm{Aut}(C)$ induces a $2$ -homogeneous action on the coordinates of the vertices of the Hamming graph. The main result of this paper classifies those $C$ for which this induced $2$ -homogeneous action is not an affine, linear or symplectic group. We find that there are $13$ such codes, $4$ of which are non-linear codes. Though most of the codes are well-known, we obtain several new results. First, a new non-linear completely transitive code is constructed, as well as a related non-linear code that is $2$ -neighbour-transitive but not completely transitive. Moreover, new proofs of the complete transitivity of several codes are given. Additionally, we answer the question of the existence of distance-regular graphs related to the completely transitive codes appearing in our main result.

preprint2020arXiv

On the 486-vertex distance-regular graphs of Koolen--Riebeek and Soicher

This paper considers three imprimitive distance-regular graphs with 486 vertices and diameter 4: the Koolen--Riebeek graph (which is bipartite), the Soicher graph (which is antipodal), and the incidence graph of a symmetric transversal design obtained from the affine geometry $\mathrm{AG}(5,3)$ (which is both). It is shown that each of these is preserved by the same rank-9 action of the group $3^5:(2\times M_{10})$ , and the connection is explained using the ternary Golay code.

preprint2016arXiv

On the metric dimension of imprimitive distance-regular graphs

A resolving set for a graph $Γ$ is a collection of vertices $S$ , chosen so that for each vertex $v$ , the list of distances from $v$ to the members of $S$ uniquely specifies $v$ . The metric dimension of $Γ$ is the smallest size of a resolving set for $Γ$ . Much attention has been paid to the metric dimension of distance-regular graphs. Work of Babai from the early 1980s yields general bounds on the metric dimension of primitive distance-regular graphs in terms of their parameters. We show how the metric dimension of an imprimitive distance-regular graph can be related to that of its halved and folded graphs, but also consider infinite families (including Taylor graphs and the incidence graphs of certain symmetric designs) where more precise results are possible.

preprint2015arXiv

On generalized Howell designs with block size three

In this paper, we examine a class of doubly resolvable combinatorial objects. Let $t, k, λ, s$ and $v$ be nonnegative integers, and let $X$ be a set of $v$ symbols. A generalized Howell design, denoted $t$ - $GHD_{k}(s,v;λ)$ , is an $s\times s$ array, each cell of which is either empty or contains a $k$ -set of symbols from $X$ , called a block, such that: (i) each symbol appears exactly once in each row and in each column (i.e.\ each row and column is a resolution of $X$ ); (ii) no $t$ -subset of elements from $X$ appears in more than $λ$ cells. Particular instances of the parameters correspond to Howell designs, doubly resolvable balanced incomplete block designs (including Kirkman squares), doubly resolvable nearly Kirkman triple systems, and simple orthogonal multi-arrays (which themselves generalize mutually orthogonal Latin squares). Generalized Howell designs also have connections with permutation arrays and multiply constant-weight codes. In this paper, we concentrate on the case that $t=2$ , $k=3$ and $λ=1$ , and write $GHD(s,v)$ . In this case, the number of empty cells in each row and column falls between 0 and $(s-1)/3$ . Previous work has considered the existence of GHDs on either end of the spectrum, with at most 1 or at least $(s-2)/3$ empty cells in each row or column. In the case of one empty cell, we correct some results of Wang and Du, and show that there exists a $GHD(n+1,3n)$ if and only if $n \geq 6$ , except possibly for $n=6$ . In the case of two empty cells, we show that there exists a $GHD(n+2,3n)$ if and only if $n \geq 6$ . Noting that the proportion of cells in a given row or column of a $GHD(s,v)$ which are empty falls in the interval $[0,1/3)$ , we prove that for any $π\in [0,5/18]$ , there is a $GHD(s,v)$ whose proportion of empty cells in a row or column is arbitrarily close to $π$ .

preprint2014arXiv

A note on packing spanning trees in graphs and bases in matroids

We consider the class of graphs for which the edge connectivity is equal to the maximum number of edge-disjoint spanning trees, and the natural generalization to matroids, where the cogirth is equal to the number of disjoint bases. We provide descriptions of such graphs and matroids, showing that such a graph (or matroid) has a unique decomposition. In the case of graphs, our results are relevant for certain communication protocols.

preprint2013arXiv

The metric dimension of small distance-regular and strongly regular graphs

A {\em resolving set} for a graph $Γ$ is a collection of vertices $S$ , chosen so that for each vertex $v$ , the list of distances from $v$ to the members of $S$ uniquely specifies $v$ . The {\em metric dimension} of $Γ$ is the smallest size of a resolving set for $Γ$ . A graph is {\em distance-regular} if, for any two vertices $u,v$ at each distance $i$ , the number of neighbours of $v$ at each possible distance from $u$ (i.e. $i-1$ , $i$ or $i+1$ ) depends only on the distance $i$ , and not on the choice of vertices $u,v$ . The class of distance-regular graphs includes all distance-transitive graphs and all strongly regular graphs. In this paper, we present the results of computer calculations which have found the metric dimension of all distance-regular graphs on up to 34 vertices, low-valency distance transitive graphs on up to 100 vertices, strongly regular graphs on up to 45 vertices, rank- $3$ strongly regular graphs on under 100 vertices, as well as certain other distance-regular graphs.

preprint2012arXiv

Packing spanning trees and the $k$ -tree protocol

We provide a structural description of, and invariants for, maximum spanning tree-packable graphs, i.e. those graphs G for which the edge connectivity of G is equal to the maximum number of edge-disjoint spanning trees in G. These graphs are of interest for the k-tree protocol of Itai and Rodeh [Inform. and Comput. 79 (1988), 43-59].

preprint2012arXiv

Resolving sets for Johnson and Kneser graphs

A set of vertices $S$ in a graph $G$ is a {\em resolving set} for $G$ if, for any two vertices $u,v$ , there exists $x\in S$ such that the distances $d(u,x) \neq d(v,x)$ . In this paper, we consider the Johnson graphs $J(n,k)$ and Kneser graphs $K(n,k)$ , and obtain various constructions of resolving sets for these graphs. As well as general constructions, we show that various interesting combinatorial objects can be used to obtain resolving sets in these graphs, including (for Johnson graphs) projective planes and symmetric designs, as well as (for Kneser graphs) partial geometries, Hadamard matrices, Steiner systems and toroidal grids.

preprint2011arXiv

Generalized covering designs and clique coverings

Inspired by the "generalized t-designs" defined by Cameron [P. J. Cameron, A generalisation of t-designs, Discrete Math. 309 (2009), 4835--4842], we define a new class of combinatorial designs which simultaneously provide a generalization of both covering designs and covering arrays. We then obtain a number of bounds on the minimum sizes of these designs, and describe some methods of constructing them, which in some cases we prove are optimal. Many of our results are obtained from an interpretation of these designs in terms of clique coverings of graphs.

preprint2011arXiv

Generalized packing designs

Generalized $t$ -designs, which form a common generalization of objects such as $t$ -designs, resolvable designs and orthogonal arrays, were defined by Cameron [P.J. Cameron, A generalisation of $t$ -designs, \emph{Discrete Math.}\ {\bf 309} (2009), 4835--4842]. In this paper, we define a related class of combinatorial designs which simultaneously generalize packing designs and packing arrays. We describe the sometimes surprising connections which these generalized designs have with various known classes of combinatorial designs, including Howell designs, partial Latin squares and several classes of triple systems, and also concepts such as resolvability and block colouring of ordinary designs and packings, and orthogonal resolutions and colourings. Moreover, we derive bounds on the size of a generalized packing design and construct optimal generalized packings in certain cases. In particular, we provide methods for constructing maximum generalized packings with $t=2$ and block size $k=3$ or 4.

preprint2011arXiv

On the metric dimension of Grassmann graphs

The {\em metric dimension} of a graph $Γ$ is the least number of vertices in a set with the property that the list of distances from any vertex to those in the set uniquely identifies that vertex. We consider the Grassmann graph $G_q(n,k)$ (whose vertices are the $k$ -subspaces of $\mathbb{F}_q^n$ , and are adjacent if they intersect in a $(k-1)$ -subspace) for $k\geq 2$ , and find a constructive upper bound on its metric dimension. Our bound is equal to the number of 1-dimensional subspaces of $\mathbb{F}_q^n$ .

preprint2011arXiv

Uncoverings on graphs and network reliability

We propose a network protocol similar to the $k$ -tree protocol of Itai and Rodeh [{\em Inform.\ and Comput.}\ {\bf 79} (1988), 43--59]. To do this, we define an {\em $t$ -uncovering-by-bases} for a connected graph $G$ to be a collection $\mathcal{U}$ of spanning trees for $G$ such that any $t$ -subset of edges of $G$ is disjoint from at least one tree in $\mathcal{U}$ , where $t$ is some integer strictly less than the edge connectivity of $G$ . We construct examples of these for some infinite families of graphs. Many of these infinite families utilise factorisations or decompositions of graphs. In every case the size of the uncovering-by-bases is no larger than the number of edges in the graph and we conjecture that this may be true in general.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Robert F. Bailey

Research overview

Is this your work?

12 publications

On the Classification of Binary Completely Transitive Codes with Almost-Simple Top-Group

On the 486-vertex distance-regular graphs of Koolen--Riebeek and Soicher

On the metric dimension of imprimitive distance-regular graphs

On generalized Howell designs with block size three

A note on packing spanning trees in graphs and bases in matroids

The metric dimension of small distance-regular and strongly regular graphs

Packing spanning trees and the $k$ -tree protocol

Resolving sets for Johnson and Kneser graphs

Generalized covering designs and clique coverings

Generalized packing designs

On the metric dimension of Grassmann graphs

Uncoverings on graphs and network reliability

See the researcher in context

Building this map preview

Robert F. Bailey

Research overview

Is this your work?

12 publications

On the Classification of Binary Completely Transitive Codes with Almost-Simple Top-Group

On the 486-vertex distance-regular graphs of Koolen--Riebeek and Soicher

On the metric dimension of imprimitive distance-regular graphs

On generalized Howell designs with block size three

A note on packing spanning trees in graphs and bases in matroids

The metric dimension of small distance-regular and strongly regular graphs

Packing spanning trees and the kkk-tree protocol

Resolving sets for Johnson and Kneser graphs

Generalized covering designs and clique coverings

Generalized packing designs

On the metric dimension of Grassmann graphs

Uncoverings on graphs and network reliability

See the researcher in context

Building this map preview

Packing spanning trees and the $k$ -tree protocol