BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
A graph G of order nv where n≥2 and v≥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∈V(G) there is at most one walk of length ≤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∩SS=∅, and complete if G∗⊆S∪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≥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 2np 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 d2/2.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.