Document TypePhD thesis
Access StatusNo attached file available
© 2015 Dr. Bin Jia
Graph theory is a branch of mathematics where pair-wise relations between objects are studied. This thesis introduces a new family of graphs, called link graphs, that extends the notions of line graphs and path graphs. We investigate the combinatorial and algorithmic properties of link graphs. Let s be a nonnegative integer. An s-link is a walk of length s in which consecutive edges are different. We identify an s-link with its reverse sequence. The s-link graph Ls(G) of a graph G is the graph whose vertices are the s-links of G, such that two vertices of Ls(G) are adjacent if and only if their corresponding s-links of G are the initial and final subsequences of some (s + 1)-link of G. For example, if G is a simple graph, then L0(G) is isomorphic to G, L1(G) is the line graph of G, and L2(G) is the 2-path graph of G. We give a characterisation that yields upper bounds for the chromatic number of link graphs. By investigating the shunting of s-links in G, we show that the Hadwiger number of a nonempty Ls(G) is at least that of G. Hugo Hadwiger (1943) conjectured that the Hadwiger number of a graph is at least the chromatic number of that graph. The conjecture has been proved by Reed and Seymour (2004) for line graphs, and hence 1-link graphs. We prove the conjecture for a wide class of link graphs. A graph G is an s-root of a graph H if H is isomorphic to Ls(G). We show that every s-root of a finite graph is a certain combination of a finite minimal (up to the subgraph relation) s-root and trees of bounded diameter. Then we bound from above the number, size, order and maximum degree of minimal s-roots of a finite graph. Further, results about tree-decompositions and better-quasi-orderings of s-roots are obtained. Based on the characterisation for link graphs and the investigation of minimal roots, algorithms are developed to solve the recognition and determination problems for s-link graphs. This implies that the recognition problem with bounded s belongs to NP. In the special case of s = 1, we characterised all pairs of graphs with isomorphic 1-link graphs. This allows us to solve the recognition and determination problems for 1-link graphs in linear time. Further, we present a linear time algorithm that, for each finite graph H, finds all pairs (G, s) such that G is a simple s-root of H of minimum degree at least 3. Moreover, we prove that there is at most one such pair with s > 0 such that G is not 3-regular of girth 4. And if such a pair exists, then the automorphism groups of G and H are isomorphic.
Keywordslink; link graph; graph colouring; graph minor; Hadwiger’s conjecture; recognition problem; determination problem; NP problem
- Click on "Export Reference in RIS Format" and choose "open with... Endnote".
- Click on "Export Reference in RIS Format". Login to Refworks, go to References => Import References