A study of link graphs

Bin Jia

Published 2014-05-26Version 1

Graph theory is a branch of mathematics in which pair-wise relations between objects are studied. My PhD thesis, supervised by David R. Wood, introduces and investigates a new family of graphs, called link graphs, that generalises the notions of line graphs and path graphs. An s-link is a walk of length s such that consecutive edges are different. The s-link graph of a given graph G is the graph with vertices the s-links of G, and two vertices are adjacent if their corresponding s-links form an (s + 1)-link; Or equivalently, one corresponding s-link can be shunted to the other in one step. For example, the 1-link graph of G is the line graph of G. We give a characterisation for link graphs, which leads to algorithmic solutions to their recognition and determination problems, and implies that the recognition problem belongs to NP. Moreover, based on a recursive structure of linkgraphs, we obtain results about the chromatic number, Hadwiger number and isomorphism group of link graphs. We also obtain results about the uniqueness, tree-decomposition and better-quasi-ordering of the original graphs of a given link graph.