
A locally irregular graph is a graph whose adjacent vertices have distinct
degrees, a regular graph is a graph where each vertex has the same degree and a
locally regular graph is a graph where for every two adjacent vertices u, v,
their degrees are equal. In this work, we study the set of all problems which
are related to decomposition of graphs into regular, locally regular and/or
locally irregular subgraphs and we present some polynomial time algorithms,
NPcompleteness results, lower bounds and upper bounds for them. Among our
results, one of our lower bounds makes use of mutually orthogonal Latin squares
which is relatively novel.

In this paper we introduce a natural mathematical structure derived from
Samuel Beckett's play "Quad". We call this structure a binary BeckettGray
code. We enumerate all codes for $n \leq 6$ and give examples for $n=7,8$.
BeckettGray codes can be realized as successive states of a queue data
structure. We show that the binary reflected Gray code can be realized as
successive states of two stack data structures.

The de Bruijn torus (or grid) problem looks to find an $n$by$m$ binary
matrix in which every possible $j$by$k$ submatrix appears exactly once. The
existence and construction of these binary matrices was determined in the 70's,
with generalizations to $d$ary matrices in the 80's and 90's. However, these
constructions lacked efficient decoding methods, leading to new constructions
in the early 2000's. The new constructions develop crossshaped patterns
(rather than rectangular), and rely on a concept known as a half de Bruijn
sequence. In this paper, we further advance this construction beyond
crossshape patterns. Furthermore, we show results for universal cycle grids,
based off of the onedimensional universal cycles introduced by Chung,
Diaconis, and Graham, in the 90's. These grids have many applications such as
robotic vision, location detection, and projective touchscreen displays.

A covering array $CA(N; t,k,v)$ is an $N \times k$ array $A$ whose each cell
takes a value for a $v$set $V$ called an alphabet. Moreover, the set $V^t$ is
contained in the set of rows of every $N \times t$ subarray of $A$. The
parameter $N$ is called the size of an array and $CAN(t,k,v)$ denotes the
smallest $N$ for which a $CA(N; t,k,v)$ exists. It is well known that
$CAN(t,k,v) = {\rm \Theta}(\log_2 k)$~\cite{godbole_bounds_1996}. In this paper
we derive two upper bounds on $d(t,v)=\limsup_{k \rightarrow \infty}
\frac{CAN(t,k,v)}{\log_2 k}$ using the algorithmic approach to the Lov\'{a}sz
local lemma also known as entropy compression.

We consider the class of graphs for which the edge connectivity is equal to
the maximum number of edgedisjoint 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.

Karonski, Luczak, and Thomason (2004) conjectured that, for any connected
graph G on at least three vertices, there exists an edge weighting from {1,2,3}
such that adjacent vertices receive different sums of incident edge weights.
Bartnicki, Grytczuk, and Niwcyk (2009) made a stronger conjecture, that each
edge's weight may be chosen from an arbitrary list of size 3 rather than
{1,2,3}. We examine a variation of these conjectures, where each vertex is
coloured with a sequence of edge weights. Such a colouring relies on an
ordering of the graph's edges, and so two variations arise  one where we may
choose any ordering of the edges and one where the ordering is fixed. In the
former case, we bound the list size required for any graph. In the latter, we
obtain a bound on list sizes for graphs with sufficiently large minimum degree.
We also extend our methods to a list variation of irregularity strength, where
each vertex receives a distinct sequence of edge weights.

We provide a structural description of, and invariants for, maximum spanning
treepackable graphs, i.e. those graphs G for which the edge connectivity of G
is equal to the maximum number of edgedisjoint spanning trees in G. These
graphs are of interest for the ktree protocol of Itai and Rodeh [Inform. and
Comput. 79 (1988), 4359].

We propose a network protocol similar to the $k$tree protocol of Itai and
Rodeh [{\em Inform.\ and Comput.}\ {\bf 79} (1988), 4359]. To do this, we
define an {\em $t$uncoveringbybases} 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 uncoveringbybases is no larger than the number of edges in the
graph and we conjecture that this may be true in general.