We consider a number of problems in graph theory, with the unifying theme being the properties of graphs which have a high degree of symmetry. In the degree-diameter problem, we consider the question of finding asymptotically large graphs of given degree and diameter. We improve a number of the current best published results in the case of Cayley graphs of cyclic, dihedral and general groups. In the degree-diameter problem for mixed graphs, we give a new corrected formula for the Moore bound and show non-existence of mixed Cayley graphs of diameter 2 attaining the Moore bound for a range of open cases. In the degree-girth problem, we investigate the graphs of Lazebnik, Ustimenko and Woldar which are the best asymptotic family identified to date. We give new information on the automorphism groups of these graphs, and show that they are more highly symmetrical than has been known to date. We study a related problem in group theory concerning product-free sets in groups, and in particular those groups whose maximal product-free subsets are complete. We take a large step towards a classification of such groups, and find an application to the degree-diameter problem which allows us to improve an asymptotic bound for diameter 2 Cayley graphs of elementary abelian groups. Finally, we study the problem of graphs embedded on surfaces where the induced map is regular and has an automorphism group in a particular family. We give a complete enumeration of all such maps and study their properties.

No description available.

We explore algorithmic aspects of two known combinatorial problems, Graph Colouring and Hamiltonian Cycle, by examining properties of their solution space. One can model the set of solutions of a combinatorial problem $P$ by the solution graph $R(P)$, where vertices are solutions of $P$ and there is an edge between two vertices, when the two corresponding solutions satisfy an adjacency reconfiguration rule. For example, we can define the reconfiguration rule for graph colouring to be that two solutions are adjacent when they differ in colour in exactly one vertex. The exploration of the properties of the solution graph $R(P)$ can give rise to interesting questions. The connectivity of $R(P)$ is the most prominent question in this research area. This is reasonable, since the main motivation for modelling combinatorial solutions as a graph is to be able to transform one into the other in a stepwise fashion, by following paths between solutions in the graph. Connectivity questions can be made binary, that is expressed as decision problems which accept a 'yes' or 'no' answer. For example, given two specific solutions, is there a path between them? Is the graph of solutions $R(P)$ connected? In this thesis, we first show that the diameter of the solution graph $R_{l}(G)$ of vertex $l$-colourings of k-colourable chordal and chordal bipartite graphs $G$ is $O(n^2)$, where $l > k$ and n is the number of vertices of $G$. Then, we formulate a decision problem on the connectivity of the graph colouring solution graph, where we allow extra colours to be used in order to enforce a path between two colourings with no path between them. We give some results for general instances and we also explore what kind of graphs pose a challenge to determine the complexity of the problem for general instances. Finally, we give a linear algorithm which decides whether there is a path between two solutions of the Hamiltonian Cycle Problem for graphs of maximum degree five, and thus providing insights towards the complexity classification of the decision problem.

Graphs are a very flexible tool within mathematics, as such, numerous problems can be solved by formulating them as an instance of a graph. As a result, however, some of the structures found in real world problems may be lost in a more general graph. An example of this is the 4-Colouring problem which, as a graph problem, is NP-complete. However, when a map is converted into a graph, we observe that this graph has structural properties, namely being (K_5, K_{3,3})-minor-free which can be exploited and as such there exist algorithms which can find 4-colourings of maps in polynomial time. This thesis looks at problems which are NP-complete in general and determines the complexity of the problem when various restrictions are placed on the input, both for the purpose of finding tractable solutions for inputs which have certain structures, and to increase our understanding of the point at which a problem becomes NP-complete. This thesis looks at four problems over four chapters, the first being Parallel Knock-Out. This chapter will show that Parallel Knock-Out can be solved in O(n+m) time on P_4-free graphs, also known as cographs, however, remains hard on split graphs, a subclass of P_5-free graphs. From this a dichotomy is shown on $P_k$-free graphs for any fixed integer $k$. The second chapter looks at Minimal Disconnected Cut. Along with some smaller results, the main result in this chapter is another dichotomy theorem which states that Minimal Disconnected Cut is polynomial time solvable for 3-connected planar graphs but NP-hard for 2-connected planar graphs. The third chapter looks at Square Root. Whilst a number of results were found, the work in this thesis focuses on the Square Root problem when restricted to some classes of graphs with low clique number. The final chapter looks at Surjective H-Colouring. This chapter shows that Surjective H-Colouring is NP-complete, for any fixed, non-loop connected graph H with two reflexive vertices and for any fixed graph H’ which can be obtained from H by replacing vertices with true twins. This result enabled us to determine the complexity of Surjective H-Colouring on all fixed graphs H of size at most 4.

We look at aspects of error analysis for interpolation by translates of a basic function. In particular, we consider ideas of localisation and how they can be used to obtain improved error estimates. We shall consider certain seminorms and associated spaces of functions which arise in the study of such interpolation methods. These seminorms are naturally given in an indirect form, that is in terms of the Fourier Transform of the function rather than the function itself. Thus, they do not lend themselves to localisation. However, work by Levesley and Light [17] rewrites these seminorms in a direct form and thus gives a natural way of defining a local seminorm. Using this form of local seminorm we construct associated local spaces. We develop bounded, linear extension operators for these spaces and demonstrate how such extension operators can be used in developing improved error estimates. Specifically, we obtain improved L2 estimates for these spaces in terms of the spacing of the interpolation points. Finally, we begin a discussion of how this approach to localisation compares with alternatives.

Let p be any fixed polynomial time testable, non-trivial, hereditary property of graphs. Suppose that the vertices of a graph G are not necessarily linearly ordered but partially ordered, where we think of this partial order as a collection of (possibly exponentially many) linear orders in the natural way. In the first part of this thesis, we prove that the problem of deciding whether a lexicographically first maximal (with respect to one of these linear orders) subgraph of G satisfying p, contains a specified vertex is NP-complete. For some of these properties p we then show that by applying certain restrictions the problem still remains NP-complete, and show how the problem can be solved in deterministic polynomial time if the restrictions imposed become more severe. Let H be a fixed undirected graph. An H-colouring of an undirected graph G is a homomorphism from G to H. In the second part of the thesis, we show that, if the vertices of G are partially ordered then the complexity of deciding whether a given vertex of G is in a lexicographically first maximal H-colourable subgraph of G is NP-complete, if H is bipartite, and Sp2-complete, if H is non-bipartite. We then show that if the vertices of G are linearly, as opposed to partially, ordered then the complexity of deciding whether a given vertex of G is in the lexicographically first maximal H-colourable subgraph of G is P-complete, if H is bipartite, and DP2-complete, if H is non-bipartite. In the final part of the thesis we show that the results obtained can be paralleled in the setting of graphs where orders are given by degrees of the vertices.

An important method to construct aperiodic tilings is the method of canonical projection from higher dimensional lattices. Lattices are the orbits of special type of crystallographic groups. For example, Penrose tilings can be obtained from a lattice tiling of E5, by the cut-and project method. Developing a mathematical theory of crystallographic tilings and generalising the method of canonical projection to other crystallographic groups than lattices. Using this method one can hope to construct (interesting), completely new types of aperiodic tilings.

This thesis studies Temporal Graphs, also called Temporal Networks. More specifically, the project aimed to carry out research on the properties of Temporal Graphs, both in general and in specific classes of the model, as well as examine and develop algorithms for solving problems in temporal graph theory. Temporal graphs are graphs that change -often dramatically- as time progresses, however maintaining a fixed number of vertices. We investigate a range of different temporal graph models depending on the way these changes occur, e.g., in a deterministic or probabilistic fashion, in a discrete-time or continuous-time context, etc. In particular, we examine connectivity matters in a model of temporal graphs where changes happen at random discrete moments in time. Within this framework, we also investigated a model of continuous time and developed algorithms that solve connectivity problems in that model. Furthermore, we study temporal network design issues for the discrete-time model of temporal graphs, both in cases where changes happen deterministically and in cases where changes happen at random discrete-time moments. We also introduce and investigate temporal network flows, where we define the problem of computing a maximum flow in a given temporal network and discuss efficient ways of solving it.

Data Assimilation means to find a trajectory of a dynamical model that matches a given set of observations. A problem of data assimilation experiments is that there is no possibility of replication. This is due to the fact that truly 'out-of-sample' observations from the same underlying flow pattern but with independent errors are usually not available. A direct evaluation against the available observations is likely to yield optimistic results since the observations were already used to find the solution. A possible remedy is presented which simply consists of estimating the optimism, giving a more realistic picture of the out-of-sample performance. The approach is simple when applied to data assimilation algorithms employing linear error feedback. Moreover, the simplicity of this method allows the optimism to be calculated in operational settings. In addition to providing a more accurate picture of performance, this approach provides a simple and efficient means to determine the optimal feedback gain matrix. A key feature of data assimilation schemes which employ linear error feedback, is the feedback gain matrix used to couple the underlying dynamical system to the assimilating algorithm. A persistent problem in practice is to find a suitable feedback. Striking the right balance of coupling strength requires a reliable assessment of performance which is provided by our estimate of the out-of-sample error. Numerical and theoretical results demonstrate that in linear systems with gaussian perturbations, the feedback determined in this way will approach the optimal Kalman Gain in the limit of large observational windows.

No description available.