Improving the capacity of radio spectrum: exploration of the acyclic orientations of a graph

The efficient use of radio spectrum depends upon frequency assignment within a telecommunications network. The solution space of the frequency assignment problem is best described by the acyclic orientations of the network. An acyclic orientation Ɵ of a graph (network) G is an orientation of the edges of the graph which does not create any directed cycles. We are primarily interested in how many ways this is possible for a given graph, which is the count of the number of acyclic orientations, a(G). This is just the evaluation of the chromatic polynomial of the graph χ(G; λ) at λ = -1. Calculating (and even approximating) the chromatic polynomial is known to be #P-hard, but it is unknown whether or not the approximation at the value -1 is. There are two key contributions in this thesis. Firstly, we obtain computational results for all graphs with up to 8 vertices. We use the data to make observations on the structure of minimal and maximal graphs, by which we mean graphs with the fewest and greatest number of acyclic orientations respectively, as well as on the distribution of acyclic orientations. Many conjectures on the structure of extremal graphs arise, of which we prove some in the theoretical part of the thesis. Secondly, we present a compression move which is monotonic with respect to the number of acyclic orientations, and with respect to various other parameters in particular cliques. This move gives us a new approach to classifying all minimal graphs. It also enables us to tackle the harder problem of identifying maximal graphs. We show that certain Turán graphs are uniquely maximal (Turán graphs are complete multipartite graphs with all vertex classes as equal as possible), and conjecture that all Turán graphs are maximal. In addition we derive an explicit formula for the number of acyclic orientations of complete bipartite graphs.

Name dc:type.qualificationname

phd

Level dc:type.qualificationlevel

doctoral

Grantor dc:publisher.institution

City, University of London

Year dc:date.issued

2017

Author dc:creator

• Schumacher, R.

• QA Mathematics