BZPEERReading, trust and collaboration for researchDiscover
Workspaces
Network
Opportunities
Account
Researcher profile
Grahame Erskine contributes to research discovery and scholarly infrastructure.
Trust snapshot
Actions
Identity and collaboration
Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.
Log in to claimDirect collaboration
Claim this author entity first to unlock direct invitations.
Research graph
Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
A graph $G$ of order $nv$ where $n\geq 2$ and $v\geq 2$ is said to be weakly $(n,v)$-clique-partitioned if its vertex set can be decomposed in a unique way into $n$ vertex-disjoint $v$-cliques. It is strongly $(n,v)$-clique-partitioned if in addition, the only $v$-cliques of $G$ are the $n$ cliques in the decomposition. We determine the structure of such graphs which have the largest possible number of edges.
An l-good sequencing of a Steiner triple system of order v, STS(v), is a permutation of the points of the system such that no l consecutive points in the permutation contains a block. It is known that every STS(v) with v > 3 has a 3-good sequencing. It is proved that every STS(v) with v >= 13 has a 4-good sequencing and every 3-chromatic STS(v) with v >= 15 has a 5-good sequencing. Computational results for Steiner triple systems of small order are also given.
The search for the smallest possible $d$-regular graph of girth $g$ has a long history, and is usually known as the cage problem. This problem has a natural extension to hypergraphs, where we may ask for the smallest number of vertices in a $d$-regular, $r$-uniform hypergraph of given (Berge) girth $g$. We show that these two problems are in fact very closely linked. By extending the ideas of Cayley graphs to the hypergraph context, we find smallest known hypergraphs for various parameter sets. Because of the close link to the cage problem from graph theory, we are able to use these techniques to find new record smallest cubic graphs of girths 23, 24, 28, 29, 30, 31 and 32.
A digraph $G$ is \emph{$k$-geodetic} if for any pair of (not necessarily distinct) vertices $u,v \in V(G)$ there is at most one walk of length $\leq k$ from $u$ to $v$ in $G$. In this paper we determine the largest possible size of a $k$-geodetic digraph with given order. We then consider the more difficult problem of the largest size of a strongly-connected $k$-geodetic digraph with given order, solving this problem for $k = 2$ and giving a construction which we conjecture to be extremal for larger $k$. We close with some results on generalised Turán problems for the number of directed cycles and paths in $k$-geodetic digraphs.
The degree-diameter problem seeks to find the maximum possible order of a graph with a given (maximum) degree and diameter. It is known that graphs attaining the maximum possible value (the Moore bound) are extremely rare, but much activity is focused on finding new examples of graphs or families of graph with orders approaching the bound as closely as possible. There has been recent interest in this problem as it applies to mixed graphs, in which we allow some of the edges to be undirected and some directed. A 2008 paper of Nguyen and Miller derived an upper bound on the possible number of vertices of such graphs. We show that for diameters larger than three, this bound can be reduced and we present a corrected Moore bound for mixed graphs, valid for all diameters and for all combinations of undirected and directed degrees.
Let $G$ be a finite group and $S$ a subset of $G$. Then $S$ is product-free if $S \cap SS = \emptyset$, and complete if $G^{\ast} \subseteq S \cup SS$. A product-free set is locally maximal if it is not contained in a strictly larger product-free set. If $S$ is product-free and complete then $S$ is locally maximal, but the converse does not necessarily hold. Street and Whitehead [J. Combin. Theory Ser. A 17 (1974), 219--226] defined a group $G$ as filled if every locally maximal product-free set $S$ in $G$ is complete (the term comes from their use of the phrase `$S$ fills $G$' to mean $S$ is complete). They classified all abelian filled groups, and conjectured that the finite dihedral group of order $2n$ is not filled when $n=6k+1$ ($k\geq 1$). The conjecture was disproved by two of the current authors in [Austral. J. Combin. 63 (3) (2015), 385--398], where we also classified the filled groups of odd order. In this paper we classify filled dihedral groups, filled nilpotent groups and filled groups of order $2^np$ where $p$ is an odd prime. We use these results to determine all filled groups of order up to 2000.
We consider the degree-diameter problem for Cayley graphs of dihedral groups. We find upper and lower bounds on the maximum number of vertices of such a graph with diameter 2 and degree $d$. We completely determine the asymptotic behaviour of this class of graphs by showing that both limits are asymptotically $d^2/2$.