Library Header Image
LSE Theses Online London School of Economics web site

Connectivity properties of some transformation graphs

Trakultraipruk, Somkiat (2013) Connectivity properties of some transformation graphs. PhD thesis, London School of Economics and Political Science.

Download (1MB) | Preview


Many combinatorial problems can be formulated as \can we transform configuration 1 into configuration 2 if certain transformations are allowed?" In order to study such questions, we introduce a so-called transformation graph. This graph has the set of all possible configurations as its vertex set, and there is an edge between two configurations if one configuration can be obtained from the other by one of the allowed transformations. Then a question like \can we go from one configuration to another one" becomes a question about connectivity properties of transformation graphs. In this thesis, we study the following types of transformation graphs in particular: Labelled Token Graphs: Here configurations are arrangements of labelled tokens on a given graph, and we can go from one arrangement to another one by moving one token at a time along an edge of the given graph. We classify all cases when labelled token graphs are connected, and classify all pairs of arrangements that are in the same component. We also look at the problem how hard it is to determine the length of the shortest path between two arrangements. Strong k-Colour Graphs: For this transformation graph, the configurations are the proper vertex-colourings of a given graph with k colours, in which all k colours are actually used. We call such a colouring a strong k-colouring. We study the problem when we can transform any strong k-colouring into any other one by recolouring one vertex at a time, always maintaining a strong k-colouring. For certain classes of graphs, we can completely determine when the transformation graph of strong k-colourings is connected.

Item Type: Thesis (PhD)
Additional Information: © 2013 Somkiat Trakultraipruk
Library of Congress subject classification: Q Science > QA Mathematics
Sets: Departments > Mathematics
Supervisor: van den Heuvel, Jan and Brightwell, Graham

Actions (login required)

Record administration - authorised staff only Record administration - authorised staff only


Downloads per month over past year

View more statistics