Source author record

Andrea C. Burgess

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

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

5works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Mutually orthogonal cycle systems

An ${\ell}$ -cycle system ${\mathcal F}$ of a graph $Γ$ is a set of ${\ell}$ -cycles which partition the edge set of $Γ$ . Two such cycle systems ${\mathcal F}$ and ${\mathcal F}'$ are said to be {\em orthogonal} if no two distinct cycles from ${\mathcal F}\cup {\mathcal F}'$ share more than one edge. Orthogonal cycle systems naturally arise from face $2$ -colourable polyehdra and in higher genus from Heffter arrays with certain orderings. A set of pairwise orthogonal $\ell$ -cycle systems of $Γ$ is said to be a set of mutually orthogonal cycle systems of $Γ$ . Let $μ(\ell,n)$ (respectively, $μ'(\ell,n)$ ) be the maximum integer $μ$ such that there exists a set of $μ$ mutually orthogonal (cyclic) $\ell$ -cycle systems of the complete graph $K_n$ . We show that if $\ell\geq 4$ is even and $n\equiv 1\pmod{2\ell}$ , then $μ'(\ell,n)$ , and hence $μ(\ell,n)$ , is bounded below by a constant multiple of $n/\ell^2$ . In contrast, we obtain the following upper bounds: $μ(\ell,n)\leq n-2$ ; $μ(\ell,n)\leq (n-2)(n-3)/(2(\ell-3))$ when $\ell \geq 4$ ; $μ(\ell,n)\leq 1$ when $\ell>n/\sqrt{2}$ ; and $μ'(\ell,n)\leq n-3$ when $n \geq 4$ . We also obtain computational results for small values of $n$ and $\ell$ .

preprint2020arXiv

The Firebreak Problem

Suppose we have a network that is represented by a graph $G$ . Potentially a fire (or other type of contagion) might erupt at some vertex of $G$ . We are able to respond to this outbreak by establishing a firebreak at $k$ other vertices of $G$ , so that the fire cannot pass through these fortified vertices. The question that now arises is which $k$ vertices will result in the greatest number of vertices being saved from the fire, assuming that the fire will spread to every vertex that is not fully behind the $k$ vertices of the firebreak. This is the essence of the {\sc Firebreak} decision problem, which is the focus of this paper. We establish that the problem is intractable on the class of split graphs as well as on the class of bipartite graphs, but can be solved in linear time when restricted to graphs having constant-bounded treewidth, or in polynomial time when restricted to intersection graphs. We also consider some closely related problems.

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 $π$ .

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.

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.