THE LONDON SCHOOL OF ECONOMICS AND POLITICAL SCIENCE
Connectivity Properties of Some Transformation Graphs
Somkiat Trakultraipruk
A thesis submitted to the Department of Mathematics of the London School of Economics for the degree of Doctor of Philosophy, London, January 2013
To my parents
1
Declaration I certify that the thesis I have presented for examination for the MPhil/PhD degree of the London School of Economics and Political Science is solely my own work other than where I have clearly indicated that it is the work of others (in which case the extent of any work carried out jointly by me and any other person is clearly identified in it). The copyright of this thesis rests with the author. Quotation from it is permitted, provided that full acknowledgement is made. This thesis may not be reproduced without my prior written consent. I warrant that this authorisation does not, to the best of my belief, infringe the rights of any third party.
2
Abstract 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 socalled 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 kColour Graphs: For this transformation graph, the configurations are the proper vertexcolourings of a given graph with k colours, in which all k colours are actually used. We call such a colouring a strong kcolouring. We study the problem when we can transform any strong kcolouring into any other one by recolouring one vertex at a time, always maintaining a strong kcolouring. For
3
certain classes of graphs, we can completely determine when the transformation graph of strong kcolourings is connected.
4
Acknowledgements This thesis would not have been possible without the guidance and help of several individuals who in one way or another contributed and extended their valuable assistance in the preparation and completion of this study. First, I would like to thank my first and second supervisors, Professor Jan van den Heuvel and Professor Graham Brightwell (Department of Mathematics, London School of Economics and Political Science, United Kingdom), whose encouragement and assistance helped me to complete this study. Professor Mark Ellingham, Professor Ralph McKenzie, and Professor Michael D. Plummer (Department of Mathematics, Vanderbilt University, United States), who supported me through my Master’s degree. Associate Professor Wanida Hemakul and Assistant Professor Chariya Uiyyasathian (Department of Mathematics, Chulalongkorn University, Thailand), who offered constant support and guidance, and are the people who made it possible for me to study in both the US and UK. I will always owe them a huge debt of gratitude. Mr Somsak Anansuvanchai, Ms Tassanee Arayatragullikit, Mr Banchar Arnonkijpanich, Assistant Professor Vannee Netsinghanart, Mr Somkiat Panoi, Associate Professor Tiang Poomsaard, and Mr Jirayuth Wathveerapong (Department of Mathematics, Khon Kaen University, Thailand), who were a big influence on me during my first degree, and I will always be grateful to them for their advice and encouragement. 5
Mr Som Prangnakhon, Mr Suthep Prasong, Ms Kobkue Ratchakit, and Mr Manote Ratchakit (Nangrong School, Buriram, Thailand), who encouraged my interest in Mathematics and English through their excellent teaching, fostering in me the desire to pursue both to a higher level. Development and Promotion of Science and Technology Talents Project (DPST), Higher Education Strategic Scholarships for Frontier Research Network (SFR), and The Royal Thai Government, who have supported me throughout my studies, and without their assistance, it would not have been possible for me to have gone as far as I have in my academic career. Jorge, Ahmad, Yavor, Pa Van, P’Noi, all my friends in London and Leeds, and friends at Old Siam, Thai Cottage, Thai Square, Manorom, The Cos Bar, and The Bok Bar, who made my time in the UK unforgettable. Thank you for your support and friendship. P’Mee, P’Phong, P’Noi, P’Jang, P’Top, P’Aekk, and all my friends at Siam Cuisine and Siam Cafe, who helped and advised me in personal and professional matters. Thank you for making my time in the US so enjoyable. Noi, Joe, Yok, Saaw, Nui, Palm, and David, who are my best friends forever. Thank you for always being there, and for always making me smile. (”,) Ming and Oomimm, I will never forget the time we spent together and the happiness that brought me. Jeck Heng and Sim Muay, who have always given me good advice. Finally, I would like to thank the people I love the most, Tia, Maa, Ree, Mart, and Pen, whose support and love have guided me through the good times and the bad. There are no seconds in the day in which I don’t love you.
6
Contents Abstract
3
Acknowledgements
5
Contents
7
1 Introduction 8 1.1 Preliminaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.2 Outline of the Thesis . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2 Labelled Token Graphs 2.1 Literature . . . . . . . . . . . . 2.2 Main Results on Connectivity of 2.3 Proof of Theorem 2.2 . . . . . . 2.4 Proof of Theorem 2.3 . . . . . .
. . . . . . . . . Labelled Token . . . . . . . . . . . . . . . . . .
. . . . . Graphs . . . . . . . . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
19 21 23 28 42
3 Miscellaneous Results on Labelled Token Graphs 50 3.1 Complexity of Finding Shortest Paths in Labelled Token Graphs . . 50 3.2 Connectivity of Labelled Token Graphs and Forbidden Minors . . . 57 4 Strong kColour Graphs 4.1 Literature . . . . . . . . . . . . . . . . . . . . . . . 4.2 General Results on Connectivity of Strong kColour 4.3 The Strong kColour Graph of Paths . . . . . . . . 4.4 The Strong kColour Graph of Cycles . . . . . . . . 4.5 The Strong 3Colour Graph of Trees . . . . . . . . 4.6 Discussion . . . . . . . . . . . . . . . . . . . . . . .
. . . . . Graphs . . . . . . . . . . . . . . . . . . . .
. . . . . .
. . . . . .
. . . . . .
. . . . . .
63 65 66 71 76 83 86
Bibliography
87
A Appendix
91
7
Chapter 1
Introduction The primary focus of this thesis is to study “Transformation Graphs”. But what are they? And why should we study them? It might be good to start the thesis by answering these two questions. We may answer the first question by using the following definition. Let O be a collection of objects and T a collection of transformations, where each transformation changes one object into another object. The transformation graph has O as its vertex set, and there is an edge between two objects if one object can be obtained from the other by some transformation from T . With the definition above, it may not be that clear what transformation graphs really are. So here we give some examples of transformation graphs. The graph T G(v, e) Let G(v, e) be the class of all graphs with v vertices and e edges. Define the graph T G(v, e) to be the graph having G(v, e) as its vertex set, and two vertices are adjacent if one vertex can be obtained from the other by adding an edge and deleting another edge. The (∆, n)Graph Let G(∆, n) be the class of all graphs with n vertices, and with maximum degree ∆. Define the (∆, n)Graph to be the graph having G(∆, n) as its vertex set, and two vertices are adjacent if one vertex can be obtained from the other by either adding or deleting an edge. 8
We can see that these two examples have the vertex sets coming from the class of graphs with some specific properties. However, there are some other transformation graphs, getting the vertex sets from different ways, e.g., Token Graphs. Token Graphs (FabilaMonroy et al. [11]) For a graph G and positive integer k, let the token graph Fk (G) be the graph whose vertices are ksubsets of V (G), and two ksubsets are adjacent in Fk (G) if their symmetric difference (the set of vertices which are in either of the sets but not in both sets) is a pair of adjacent vertices in G. We have extended the study of FabilaMonroy et al. by generalising the problem to any number of tokens. Additionally, tokens can be identical or different. For more details, see Labelled Token Graphs in Chapter 2. Next, we will answer the second question, “why should we study transformation graphs?”. A possible answer is the following. In some problems, we cannot solve them directly, or they are not easy to be solved directly, but when we transform them to other problems, they might be solved easier. The 15puzzle is a sliding puzzle that consists of 15 squares numbered from 1 to 15 that are placed in a 4 × 4 box leaving one position out of the 16 empty. The object of the puzzle is to reposition the squares from a given arrangement into the configuration β shown in Figure 1.1 by making sliding moves that use the empty space. Example 1.1 Let α and β be the two configurations of the 15puzzle problem, which are shown in Figure 1.1. Is it possible to reach β from α?
This question can be easily answered by using labelled token graphs, and the answer will be “NO”. See the arguments at the end of Chapter 2. 9
2 6 10 14
1 5 11 15
4 3 8 7 12 9 13
1 5 9 13
2 6 10 14
3 4 7 8 11 12 15
Figure 1.1: Configurations α and β of the 15Puzzle
1.1
Preliminaries
In this section we present some mathematical terminology and notation, which are used in this thesis. Most of them will be standard and can be found in any textbook on graph theory, such as [10] and [27].
Basic Concepts in Graph Theory A graph G is defined by two finite sets V (G) and E(G), where an element of V (G) is called a vertex, and an element of E(G) is called an edge. Each edge is a twoelement subset of V (G). An edge between vertices u and v is denoted by uv. The degree of a vertex v in G, denoted by dG (v), is the number of edges of G incident with v. We omit the subscript G when it is clear from the context. The numbers of vertices and edges in G are denoted by n(G) and e(G), respectively. A walk on n vertices is a sequence v1 , v2 , . . . , vn of vertices where any two consecutive vertices are adjacent. A path on n vertices, denoted by Pn , is a walk with n vertices such that the vertices are all different. The size and the length 10
of Pn are n and n − 1, respectively. A cycle on n vertices, denoted by Cn , is a sequence v1 , v2 , . . . , vn , vn+1 , where any two consecutive vertices are adjacent, and the vertices are all different except v1 = vn+1 . The distance between two vertices in a graph is the length of a shortest path connecting them. A graph is connected if for any two vertices there is a path between them. A subgraph of a graph G is a graph H such that V (H) ⊆ V (G) and E(H) ⊆ E(G). A spanning subgraph of G is a subgraph with vertex set V (G). An induced subgraph of a graph G is a graph H such that for any pair of vertices x and y of H, xy is an edge of H if and only if xy is an edge of G. A component is a maximal connected subgraph. A vertex cut of a graph G is a set of vertices S such that G\S has more components than G, where G\S denotes the graph obtained after deleting the vertices in S, together with the edges incident with these vertices. If S = {v} is a vertex cut, we call v a cutvertex. An edge e is a cutedge of G if G\{e} (the graph obtained after deleting the edge e) has more components than G. A block is a maximal connected subgraph without cutvertices. A graph is kconnected if it has at least k + 1 vertices and there is no vertex cut with k − 1 or fewer vertices. Here is a theorem about kconnected graphs, which can be found in any textbook of graph theory. Theorem 1.2 (Global Version of Menger’s Theorem) A graph G with n(G) ≥ k + 1 is kconnected if and only if for every u, v ∈ V (G) there exist k internally disjoint paths from u to v.
11
The graph Cartesian product GH of graphs G and H is the graph such that V (GH) = {(u, v) : u ∈ V (G) and v ∈ V (H)}, and two vertices (u1 , v1 ) and (u2 , v2 ) are adjacent in GH if and only if either u1 = u2 and v1 is adjacent with v2 in H, or v1 = v2 and u1 is adjacent with u2 in G. A grid graph is the graph Cartesian product of two paths. A complete graph is a graph where any two vertices are adjacent. We denote a complete graph with n vertices by Kn . A bipartite graph is a graph without odd cycles. For a bipartite graph, we can partition the vertices into two sets X and Y such that every edge has one end vertex in X and one in Y . A complete bipartite graph has an edge from every vertex in X to every vertex in Y . We denote the complete bipartite graph with p vertices in X and q vertices in Y by Kp,q . A planar graph is a graph that can be drawn on the plane such that its edges intersect only at their endpoints. A tree is a connected graph with no cycles. And the graph θ0 is the graph shown in Figure 1.2. vr6 vr5
J
r Jr v1 rJ v v4 Jr 0 r
v2
v3
Figure 1.2: The graph θ0
Permutation Groups A permutation of a set is a bijection from that set onto itself. The set of all permutations of any given set S forms a group, with composition of functions as product and the identity as identity element. This group is the symmetric group of S. A transposition is a permutation which exchanges two elements and keeps all others fixed. Note that every permutation can be written as a product of transpositions. A permutation is odd if it can be written as a product of an odd 12
number of transpositions; otherwise, it is an even permutation. Since bijections have inverses, so do permutations. The inverse of a permutation α, denoted by α−1 , is the permutation such that α(x) = y if and only if α−1 (y) = x for any elements x, y.
Complexity and Algorithms In this thesis we need a number of concepts from algorithmic complexity theory. The formal definitions of these concepts would be beyond the scope of this thesis. In this section we give some informal descriptions only; more formal definitions can be found in any textbook such as [9] and [14]. The time complexity of an algorithm quantifies the amount of time taken by the algorithm to run as a function of the length of the string representing the input. The time complexity of an algorithm is commonly expressed using big O notation, which is defined as the following. For functions f, g : Z+ → R, we say that f (n) = O(g(n)) (pronounced f (n) is big O g(n)) if there are constants N ≥ 1 and C > 0 such that for all n ≥ N we have f (n) ≤ Cg(n). For example, if the time required by an algorithm on all inputs of size n is at most 7n3 + 5n, its time complexity is said to be O(n3 ). An algorithm is said to be of polynomial time if its running time is upper bounded by a polynomial expression in the size of the inputs for the algorithm, i.e., if the time complexity is O(nk ) for some constant k, where n is the size of the inputs. A decision problem is a problem whose output is a single Boolean value: YES or NO. Let A and B be two decision problems. A reduction from A to B is a function f which transforms inputs of A to equivalent inputs of B. That is given an input x 13
to the problem A, f will produce an input f (x) to the problem B, such that x is a “YES” input of A if and only if f (x) is a “YES” input of B. This reduction can be used to define complexity classes on a set of problems. Intuitively, if a problem A is reducible to a problem B, then an algorithm for solving B efficiently (if it existed) could also be used as a subroutine to solve A efficiently provided the reduction can be done efficiently as well. Thus solving A cannot be harder than solving B. The set P is the set of decision problems that can be solved in polynomial time, and the set NP is the set of decision problems with the following properties: if the answer is “YES”, then there is a certificate of that yesanswer which can be checked in polynomial time. A problem is NPhard if a polynomialtime algorithm for the problem would imply a polynomialtime algorithm for every problem in NP. A problem is NPcomplete if it is both NP hard and an element of NP. Note that to prove a problem is NP complete, all we need to do are: (1) showing that the problem is in NP, (2) reducing a known NP complete problem to it, and (3) showing that the reduction is a polynomialtime computable function. To give some examples of NP complete problems, we define a Boolean formula to be an expression written using only AND, OR, NOT, variables, and parentheses; ¯ A literal is either a variable or its negation. e.g., (a ∨ b ∨ c¯) ∧ ((a ∧ ¯b) ∨ (c ∧ d)). A Boolean formula is in conjunctive normal form if it is a conjunction (AND) of several clauses, each of which is a disjunction (OR) of one or more literals; e.g., (a ∨ b ∨ c¯) ∧(b ∨ c¯) ∧ (¯ a ∨ d) ∧ (a ∨ ¯b ∨ d).  {z } clause
The following are NP complete problems.
14
SAT Input: A Boolean formula; Question: Is there a truth assignment for the variables which satisfies the formula? 3SAT Input: A Boolean formula which is in conjunctive normal form with 3 literals per clause; Question: Is there a truth assignment for the variables which satisfies the formula? 3ExactCover m Input: A set U = {ui }3n i=1 and a collection S = {sj }j=1 of 3element subsets of U ;
Question: Is there a subcollection S 0 ⊆ S such that every element in U occurs in exactly one member of S 0 ? The complement of a decision problem is the decision problem, which results from replacing the problem by the negation of that problem. For example, one important problem is to consider if a number is a prime number. Its complement is to ask if a number is a composite number (a number which is not prime). A decision problem is a member of coNP if and only if its complement is in NP. Each coNPcomplete problem is the complement of an NP complete problem. A decision problem is in PSPACE if it can be solved by an algorithm using polynomial storage space. A decision problem is PSPACEcomplete if it is in PSPACE, and every problem in PSPACE can be reduced to it in polynomial time.
Minors Let G be a graph. A vertexdeletion of G means removing a vertex from the vertex set of G and removing all edges incident to it. An edgedeletion of G means
15
removing an edge from the edge set of G. An edgecontraction of an edge uv means replacing the vertices u and v by a new vertex w, then joining w to all vertices that were adjacent to u or v, and finally replacing any multiple edges which arise by a single edge. A graph H is a minor of a graph G if H can be obtained from G by a sequence of vertexdeletions, edgedeletions, and edgecontractions. Note that in the definition, we allow a sequence of length zero, so every graph is a minor of itself. In this thesis, it is common to assume that all graphs are connected. Then if H is a minor of a connected graph G, H can be obtained from G by a sequence of edgedeletions and edgecontractions only (since a vertexdeletion can be obtained by an edgecontraction and some edgedeletions in a connected graph).
Orderings A relation ≤ on a set X is a quasiordering if it is reflexive (x ≤ x for all x ∈ X) and transitive (if x ≤ y and y ≤ z, then x ≤ z for all x, y, z ∈ X). And ≤ is a wellquasiordering if it is a quasiordering, and for any infinite sequence of elements x0 , x1 , x2 , . . . from X, there are two indices i < j such that xi ≤ xj . Note that sometimes we use x ≥ y to denote y ≤ x, and y < x to denote y ≤ x and y 6= x. A quasiordering is without infinite descent if there are no infinite strictly decreasing sequences x1 > x2 > x3 > · · · . An antichain A ⊆ X is a subset such that no two elements in A are comparable. Let P be a property defined on elements of a set X. We say that P is closed under a quasiordering ≤ (or ≤closed ) if for every two elements x, y ∈ X we have that if x has property P and y ≤ x, then y also has property P . 16
Let ≤ be a wellquasiordering on a set X, and P a ≤closed property on X. Then an element x ∈ X is said to be P forbidden if it is a minimal element in X under ≤, which does not have property P .
Labelled Token Graphs Let G be a graph, and k1 , k2 , . . . , kp positive integers for some p ∈ Z+ . We assume we have k1 + k2 + · · · + kp labelled tokens, where there are ki tokens with label i, for i = 1, 2, . . . , p. A token configuration is an arrangement of all these tokens on the vertices of G such that no two tokens are placed on the same vertex. The labelled token graph of G with a multiset of tokens (k1 , k2 , . . . , kp ) is the graph whose vertices correspond to all possible different token configurations, and two token configurations are adjacent if one token configuration can be reached from the other by moving one token along an edge of G. We denote the labelled token graph by T (G; (k1 , k2 , . . . , kp )).
Strong kColour Graphs For a positive integer k, a kvertexcolouring of a graph G is a function f : V (G) → {1, 2, . . . , k}. A colouring is proper if adjacent vertices have different labels. A graph is kcolourable if it has a proper kvertexcolouring. The smallest number of colours needed to colour a graph is called its chromatic number. The strong kcolour graph of a graph G and integer k, denoted by Sk (G), is the graph that has the proper kvertexcolourings of G using exactly k colours as its vertices, and two such colourings are joined by an edge if they differ in the colour on one vertex only.
17
1.2
Outline of the Thesis
In Chapter 2, we work on labelled token graphs, and we prove two main theorems. The first theorem gives sufficient and necessary conditions of labelled token graphs being disconnected. The other main result tells exactly the situation whether two given token configurations are in the same component of a labelled token graph or not. Chapter 3 contains some miscellaneous results on labelled token graphs. We first consider the computational hardness of finding the shortest path between two token configurations in labelled token graphs. Then we propose another way to prove being disconnected of labelled token graphs by considering whether a given graph contains certain forbidden minors or not, and we prove that the number of these forbidden minors is finite for all the numbers of tokens. In the last chapter, we study strong kcolour graphs. We give some general results and characterise when strong kcolour graphs are connected for some classes of graphs. In the appendix, we talk about the graph θ0 again because it is the only 2connected nonbipartite graph so that not all its labelled token graphs are connected. We show the components of labelled token graphs of θ0 in a compact form, which will be described later. The results in Chapter 2 are joint work with Professor Graham Brightwell and Professor Jan van den Heuvel, whilst the results in Chapter 3 are joint work with Professor Jan van den Heuvel. Chapter 4 can be found in [25], and we are preparing publication of the results from Chapters 2 and 3 in [4] and [26], respectively.
18
Chapter 2
Labelled Token Graphs There are many problems and games, concerned with moving objects around. Examples are puzzle games, transportation, manufacturing, scheduling, control flow and management of memory in computing systems. These problems have been extensively studied. Let G be a graph, and k1 , k2 , . . . , kp positive integers for some positive integer p. We have a number of classes of tokens, say k1 tokens with label 1, k2 tokens with label 2, etc. Tokens with the same label are indistinguishable. A token configuration is an arrangement of all tokens on vertices of G such that no two tokens are placed on the same vertex. We use Greek letters α, β,. . . for token configurations, and we denote by α(v) = t that in the token configuration α, the vertex v contains a token with label t. A vertex which does not contain any token is said to be unoccupied, and we sometimes say that it contains an empty token, denoted by φ. The labelled token graph of G with a multiset of tokens (k1 , k2 , . . . , kp ) is the graph whose vertices correspond to token configurations, and two token configurations are adjacent if one token configuration can be reached from the other by moving one token along an edge of G. We denote the labelled token graph as T (G; (k1 , k2 , . . . , kp )), and we always assume that k1 ≥ k2 ≥ · · · ≥ kp . For convenience purposes, when the tokens are all different (k1 = k2 = · · · = kp = 1), we will denote T (G; (k1 , k2 , . . . , kp )) as T (G; p).
19
To calculate the number of vertices in T (G; (k1 , k2 , . . . , kp )) of a given graph G and positive integers k1 , k2 , . . . , kp , let k = k1 + k2 + · · · + kp . We assume that k ≤ n(G) − 1 to avoid trivial cases. Then n(G)! . (n(G) − k)!k1 !k2 ! · · · kp !
n(T (G; (k1 , k2 , . . . , kp ))) =
When all tokens are different, we have that n(T (G; p)) =
n(G)! . (n(G) − p)!
Next, we calculate the number of edges in labelled token graphs. Here we consider only the case that all tokens are different. For general cases, we cannot find a similar formula easily. Since moving a token along each edge of G represents (p1)(n(G)−2)! edges in T (G; p), we have that ((n(G)−2)−(p−1))! p · (n(G) − 2)! . e(T (G; p)) = e(G) · (n(G) − p − 1)!
With only one token, the resulting labelled token graph is isomorphic to G, i.e., T (G; 1) ∼ = G. When there are n(G) − 1 different tokens, a token configuration is a bijective mapping f : v1 , v2 , . . . , vn(G) → {1, 2, . . . , n(G) − 1, φ}. Thus we may consider a token configuration as a permutation of the set of tokens. As standard, we denote the inverse of a permutation α by α−1 , and use the same notation for the type of token configurations in this paragraph.
20
2.1
Literature
In this thesis we use the term “token” as a description for a moveable object. Other literatures looking at similar problems use terms such as agent, pebble, bean, robot, or vehicle to describe the moveable object. Some papers consider problems in which the tokens are all different [1, 18, 28], whilst others consider problems where all tokens are the same [11]. We study problems in which tokens can be identical or distinct, which can be also seen in [13, 16]. And the rules of moving tokens in those studies may be the same or different. For example, in [1, 11, 16, 18, 28], a token can be moved from one vertex to one of its unoccupied neighbours. Wilson [28] generalised the classic problem, the 15Puzzle, on 2connected graphs with n vertices and n − 1 different tokens. Theorem 2.1 (Wilson [28]) Let G be a 2connected graph, which is not a cycle or the graph θ0 . Then the token graph T (G; n(G) − 1) is connected, unless G is bipartite. In the latter case, T (G; n(G) − 1) has exactly two components, and token configurations α and β are in the same component if and only if they have unoccupied vertices at even distance in G and αβ −1 is an even permutation, or they have unoccupied vertices at odd distance in G and αβ −1 is an odd permutation. The labelled token graph T (θ0 ; 6) has six components.
Kornhauser et al. [18] followed on from Wilson’s study by generalising the problem for all graphs and any number of tokens. They also presented a polynomial time algorithm and gave O(n3 ) upper and lower bounds for deciding the reachability of any two token configurations.
21
Auletta et al. [1] also studied on the reachability of any two token configurations, but focused on trees. They gave a linear decision algorithm for those cases. Goraly and Hassin [16] studied problems where tokens can be identical or distinct, as described earlier. They proved that the reachability of any two token configurations can be decided in linear time. FabilaMonroy et al. [11] introduced the word “Token Graph”, which we use in this thesis although they only consider the case that all tokens are identical. They gave tight lower and upper bounds on the diameter, and tight lower bounds on the connectivity of their token graphs. They also gave some results on cliques, chromatic numbers, and Hamiltonian paths of their token graphs. Fujita et al. [13] generalised the problems of moving tokens by defining a move to be an exchange of two tokens with distinct labels on the two endvertices of a common edge (where an unoccupied vertex is supposed to have an empty token). They studied connectivity properties of such token graphs. Wu and Grumbach [29] studied on motion planning on directed graphs (graphs whose every edge has a direction from one vertex to the other). Their objective is to move a special token (called robot) from a source vertex to another destination vertex while the other tokens are considered as just obstacles. They proved that this problem on acyclic (without any directed cycles) strongly connected directed graphs can be decided in time O(nm), where n and m are the numbers of vertices and edges, respectively. And it can be decided in time O(n2 m) on any directed graphs.
22
2.2
Main Results on Connectivity of Labelled Token Graphs
One of our main results is showing and proving sufficient and necessary conditions of being disconnected of labelled token graphs. If p = 1, then the tokens are all the same. Thus the labelled token graph is disconnected if and only if the original graph is disconnected. So we always assume that p ≥ 2. Under that assumption, if n(G) = 2, the labelled token graph is disconnected. Hence we also assume that n(G) ≥ 3. Let G be a connected graph. A separating path of size one in G is a cutvertex. A separating path of size two in G is a cutedge P = v1 v2 such that both components of G − v1 v2 have at least two vertices. A separating path of size l ≥ 3 in G is an induced path P = v1 v2 . . . vl−1 vl such that G\{v2 , v3 , . . . , vl−1 } has exactly two components, one contains v1 and the other contains vl , and each of which has at least two vertices. When a separating path P is of size at least two, we say that G has two Pcomponents (the components described above). Theorem 2.2 Let G be a graph with n(G) ≥ 3, and k1 ≥ k2 ≥ · · · ≥ kp positive integers for some integer p ≥ 2. Then T (G; (k1 , k2 , . . . , kp )) is disconnected if and only if at least one of the following conditions holds:
1. G is disconnected; 2. k1 + k2 + · · · + kp = n(G); 3. G is a path; 4. G is a cycle with p = 2 and k2 ≥ 2, or G is a cycle with p ≥ 3; 23
5. G is the graph θ0 (shown in Figure 2.1), and (k1 , k2 , . . . , kp ) is one of the following: (2,2,2), (2,2,1,1), (2,1,1,1,1), or (1,1,1,1,1,1); 6. G is a 2connected bipartite graph other than a cycle, k1 + k2 + · · · + kp = n(G) − 1, and k1 = k2 = · · · = kp = 1 (tokens are all different); 7. G is a connected graph with connectivity 1 other than a path, containing a separating path of size n(G) − (k1 + k2 + · · · + kp ). vr6
vr5
r r Jr v1 J v0 v4 Jr r
v2 v3
J
Figure 2.1: The graph θ0
The other main result answers whether two given token configurations α and β are in the same component of the labelled token graph or not. We can see that α and β are in the same component if and only if on each component Gi of G, αGi (the token configuration on Gi induced by α) is reachable from βGi . Hence without loss of generality, we can again assume that G is connected. Next, if k1 +k2 +· · ·+kp = n(G), different token configurations are in different components of the labelled token graph. So we also suppose that k1 + k2 + · · · + kp ≤ n(G) − 1. According to the graph θ0 in Figure 2.1, a token configuration α of θ0 is standard if v1 is unoccupied in α, and it is (s,t)standard if it is standard and the tokens s and t are placed on the vertices v6 and v5 , respectively. We call the cycle v1 v2 v3 v4 v0 on θ0 as the lower 5cycle, the cycle v1 v0 v4 v5 v6 as the upper 5cycle, and the cycle v1 v2 v3 v4 v5 v6 as the outside 6cycle. Let G be a connected graph with connectivity 1, n(G) − (k1 + k2 + · · · + kp ) = l ≥ 2, and P1 , P2 , . . . , Pm all the separating paths of size l in G. For each i = 1, 2, . . . , m, let Gi,1 and Gi,2 be the two Pi components of G. Given a token 24
configuration α, let αi be a token configuration obtained from α by moving some tokens (if necessary) to make all the vertices on Pi unoccupied. Let G be a connected graph with connectivity 1, n(G) − (k1 + k2 + · · · + kp ) = 1, and B a block in G. Then B contains at least one cutvertex of G. Let vB be one of these cutvertices. Given a token configuration α, let αvB be a token configuration obtained from α by moving some tokens (if necessary) to make vB unoccupied. We denote the multiset of all the tokens used in a token configuration α by τ (α). For example, if α is any of the token configurations in Figure 2.4, then τ (α) = {1, 1, 2, 2, 3, 3} = (2, 2, 2). Theorem 2.3 Let G be a connected graph with n(G) ≥ 3, k1 ≥ k2 ≥ · · · ≥ kp positive integers for some integer p ≥ 2, and k1 + k2 + · · · + kp ≤ n(G) − 1. Then two token configurations α and β are in the same component of T (G; (k1 , k2 , . . . , kp )) if and only if at least one of the following conditions holds:
1. T (G; (k1 , k2 , . . . , kp )) is connected; 2. G is a path, and the orders of tokens on G of α and β are the same; 3. G is a cycle, and the cyclic orders of tokens on G of α and β are the same; 4. G is the graph θ0 , and (a) (k1 , k2 , . . . , kp ) = (2, 2, 2) or (2, 2, 1, 1), and for any (1,1)standard token configurations α0 and β 0 which can be reached from α and β, respectively, we have that α0 and β 0 are in the same group from the following two groups:
25
Group a1 : (1,1)standard token configurations of which the cyclic order of tokens on the lower 5cycle is (2, 2, s, t), where s, t ∈ {3, 4}. I.e., token configurations which have the following forms: 1r 1r
J r
r Jr t J 2
Jr r
2
s
1r 1r
J
r r Jrs J t
Jr r
2
1r 1r
J r
r Jr2 J s
Jr r
t
2
2
1r 1r
J r
r Jr2 J 2
Jr r
s
t
Group a2 : (1,1)standard token configurations of which the cyclic order of tokens on the lower 5cycle is (2, s, 2, t), where s, t ∈ {3, 4}, (b) (k1 , k2 , . . . , kp ) = (2, 1, 1, 1, 1), and for any (1,1)standard token configurations α0 and β 0 which can be reached from α and β, respectively, we have α0 and β 0 are in the same group from the following three groups: Group b1 : (1,1)standard token configurations of which the cyclic order of tokens on the lower 5cycle is (2, 3, 4, 5) or (2, 5, 4, 3); Group b2 : (1,1)standard token configurations of which the cyclic order of tokens on the lower 5cycle is (2, 4, 3, 5) or (2, 5, 3, 4); Group b3 : (1,1)standard token configurations of which the cyclic order of tokens on the lower 5cycle is (2, 3, 5, 4) or (2, 4, 5, 3); (c) (k1 , k2 , . . . , kp ) = (1, 1, 1, 1, 1, 1), and for any (1,6)standard token configurations α0 and β 0 which can be reached from α and β, respectively, we have α0 and β 0 are in the same group from the following six groups: Group c1 : (1,6)standard token configurations of which the cyclic order of tokens on the lower 5cycle is (2, 3, 4, 5); Group c2 : (1,6)standard token configurations of which the cyclic order of tokens on the lower 5cycle is (2, 5, 4, 3); Group c2 : (1,6)standard token configurations of which the cyclic order of tokens on the lower 5cycle is (2, 4, 3, 5); 26
Group c4 : (1,6)standard token configurations of which the cyclic order of tokens on the lower 5cycle is (2, 5, 3, 4); Group c5 : (1,6)standard token configurations of which the cyclic order of tokens on the lower 5cycle is (2, 3, 5, 4); Group c6 : (1,6)standard token configurations of which the cyclic order of tokens on the lower 5cycle is (2, 4, 5, 3). 5. G is a 2connected bipartite graph other than a cycle, there are n(G) − 1 different tokens, and one of the following holds: (a) α and β have their unoccupied vertices at even distance in G, and αβ −1 is an even permutation; (b) α and β have their unoccupied vertices at odd distance in G, and αβ −1 is an odd permutation. 6. G is a connected graph with connectivity 1 other than a path, n(G)−(k1 +k2 + · · · + kp ) = l ≥ 2, P1 , P2 , . . . , Pm are all the separating paths of size l in G, and τ (αi Gi,1 ) = τ (βi Gi,1 ) and τ (αi Gi,2 ) = τ (βi Gi,2 ) for all i = 1, 2, . . . , m. 7. G is a connected graph with connectivity 1 other than a path, n(G) − (k1 + k2 + · · · + kp ) = 1, for each block B in G, τ (αvB B ) = τ (βvB B ), and at least one of the following conditions holds: (a) T (B; τ (αvB B )) is connected; (b) B is a cycle, and the cyclic orders of tokens of αvB B and βvB B are the same; (c) B is the graph θ0 , and αvB B and βvB B satisfy 4(a), 4(b), or 4(c) above; (d) B is a 2connected bipartite graph other than a cycle, there are n(B)−1 different tokens in αvB B and βvB B , and αvB B · (βvB B )−1 is an even permutation. 27
2.3
Proof of Theorem 2.2
In some figures which follow, we add a subscript to a label to see how the tokens are moved; however, tokens with the same label (but with different subscripts) should be interpreted as being indistinguishable. Let α be any token configuration of a graph G, and v1 and v2 vertices on G. Let β be a token configuration of G such that β(v1 ) = α(v2 ), β(v2 ) = α(v1 ), and β(v) = α(v) for all v 6= v1 , v2 . We say that tokens α(v1 ) and α(v2 ) can be improperly swapped in α if there is a sequence of moves to get β from α. We call such a swap an improperly emptytoken swap when we improperly swap a token with an empty token. Note that if the tokens are all different, an improper swap of two tokens is just swapping the positions of them. In Figure 2.2, we can see that in α the tokens 2 and 3 can be improperly swapped by moving the tokens on the cycle until we get the token configuration β. 1r2
1r1 3r
@ @r B β Br r
2 r α @r B Br r 12 3 @
11
2
Figure 2.2: Token configurations α and β
Lemma 2.4 Let G be a connected graph, and k1 , k2 , . . . , kp positive integers for some integer p. Then T (G; (k1 , k2 , . . . , kp )) is connected if and only if any two tokens in any token configuration can be improperly swapped.
Proof. If the labelled token graph is connected, then any two tokens in any token configuration can be improperly swapped since improper swap is a special case of transformation from one token configuration to another one in the labelled 28
token graph. On the other hand, we suppose that any two tokens in any token configuration can be improperly swapped. Given any two token configurations α and β, we can assume that the sets of all unoccupied vertices in α and β are the same (otherwise, we move some tokens in β to get another token configuration which we want and then call it β). Then β is reachable from α by a sequence of improper swaps of two tokens.
Since we can improperly swap two tokens by doing three consecutive improperly emptytoken swaps, we get the following lemma. Lemma 2.5 Let G be a connected graph, and k1 , k2 , . . . , kp positive integers for some integer p. Then T (G; (k1 , k2 , . . . , kp )) is connected if and only if any token and any empty token in any token configuration can be improperly emptytoken swapped.
The following Properties are easily proved by using Lemma 2.4. Proposition 2.6 Let p ≤ q, and ki ≤ li for all i. If T (G; (l1 , l2 , . . . , lq )) is connected, then the token graph T (G; (k1 , k2 , . . . , kp )) is connected. Proposition 2.7 For each i = 1, 2, . . . , p, we refine ki as a summation of positive integers, say ki = ki,1 + ki,2 + · · · + ki,ni for some positive integer ni . Let (l1 , l2 , . . . , lq ) be the nonincreasing reordering of (k1,1 , k1,2 , . . . , k1,n1 , . . . , kp,1 , kp,2 , . . . , kp,np ), where q = n1 +n2 +· · ·+np . If T (G; (l1 , l2 , . . . , lq )) is connected, then T (G; (k1 , k2 , . . . , kp )) is connected.
29
Proposition 2.8 Let H be a connected graph, which contains a subgraph G. If T (G; (k1 , k2 , . . . , kp )) is connected, then T (H; (k1 , k2 , . . . , kp )) is connected. Lemma 2.9 Let G be a cycle. Then T (G; (k1 , k2 , . . . , kp )) is connected if and only if p = 1, or if p = 2, k1 ≤ n(G) − 2, and k2 = 1.
Next, we consider the graph θ0 . According to Figure 2.1, we call v1 and v4 middle vertices of θ0 . Applying an operation U (respectively, L) on a standard token configuration α is making 5 moves of the tokens on the upper (respectively, lower) 5cycle anticlockwise to get another standard token configuration (see Figure 2.3 for examples). 1r1 1r2
J
r r Jr2 J 21 2 Jr r
31
32
1r2 2r2
J U
r r Jr2 J 11 1 Jr r
31
1r1 1r2
J
r r Jr2 J 21 2 Jr r
32
31
32
1r1 1r2
L r r JJr 3 J 22 2 Jr r
21
31
Figure 2.3: Operations U and L
On a standard token configuration, making 6 moves of the tokens on the outside 6cycle anticlockwise can be replaced by using the operation U and then L. Thus two standard token configurations are in the same component of the labelled token graph if and only if one configuration can be obtained from the other by a finite sequence of operations U and L. Lemma 2.10 The labelled token graphs T (θ0 ; (2, 2, 2)), T (θ0 ; (2, 2, 1, 1)), T (θ0 ; (2, 1, 1, 1, 1)), and T (θ0 ; (1, 1, 1, 1, 1, 1)) are all disconnected.
30
Proof. By Proposition 2.7, if T (θ0 ; (2, 2, 2)) is disconnected, then the other labelled token graphs are also disconnected. So it suffices to show that T (θ0 ; (2, 2, 2)) is disconnected. Note that every token configuration in T (θ0 ; (2, 2, 2)) has a path to 6! 2!2!2!
some standard token configuration. There are
= 90 standard token configu
rations in total, which are shown in Figures 2.4 and 2.5.
1 1
1 1
2 2
L,L
2 2 3
3
L
2 2
U,L,U,L,L
3 3 2
2
L
3 3
3 3 1
1 1 3
L
3 3
U,L,U,L,L
L,L
1
3
L
L,L
1 1 2
2
L
2 1 2 1 L
1 1
1 1
2 2
2 2
3 3
3 3
3 3 2 2
2 2 3 3
1 1 3 3
3 3 1 1
2 2 1 1
1 1 2 2
U
U
U
U
U
U
1 3
1 2
2 1
2 3
3 2
3 1
1 3 2 2
1 2 3 3
2 1 3 3
2 3 1 1
3 2 1 1
3 1 2 2
L
L
L
L
L
L
1 3
1 2
2 1
2 3
3 2
3 1
3 2 1 2
2 3 1 3
1 3 2 3
3 1 2 1
2 1 3 1
1 2 3 2
U
U
U
U
U
U
3 2
2 3
1 3
3 1
2 1
1 2
1 3 1 2
1 2 1 3
2 1 2 3
2 3 2 1
3 2 3 1
3 1 3 2
U,L
U,L
U,L
U,L
U,L
U,L
2 3
3 2
3 1
1 3
1 2
2 1
1 2 3 1
1 3 2 1
2 3 1 2
2 1 3 2
3 1 2 3
3 2 1 3
L
L
L
L
L
L
2 3
3 2
3 1
1 3
1 2
2 1
2 1 1 3
3 1 1 2
3 2 2 1
1 2 2 3
1 3 3 2
2 3 3 1
U
U
U
U
U
U
3 1
2 1
1 2
3 2
2 3
1 3
2 2 1 3
3 3 1 2
3 3 2 1
1 1 2 3
1 1 3 2
2 2 3 1
U
U
U
U
U
U
1 2
1 3
2 3
2 1
3 1
3 2
3 2 1 3
2 3 1 2
1 3 2 1
3 1 2 3
2 1 3 2
1 2 3 1
L
L
L
L
L
L
1 2
1 3
2 3
2 1
3 1
3 2
2 3 3 1
3 2 2 1
3 1 1 2
1 3 3 2
1 2 2 3
2 1 1 3
Figure 2.4: The 60 standard token configurations of Group a1 in T (G; (2, 2, 2))
We can see that standard token configurations in the same figure are in the same component since they are joined by a path which can be generated by the given 31
1 1
1 1
2 2
L
2 3 2
3
U
2 2
U,L,L,U
3 2 3
2
U
3 3
1 3 1
3 1 3
U
3 3
U,L,U,U
L
3
1
U
L
1 2 1
2
2 1 1 2
U
U
1 3
1 2
2 3
2 1
3 2
3 1
1 2 3 2
1 3 2 3
2 1 3 1
2 3 1 3
3 1 2 1
3 2 1 2
L
L
L
L
L
L
1 3
1 2
2 3
2 1
3 2
3 1
2 2 1 3
3 3 1 2
1 1 2 3
3 3 2 1
1 1 3 2
2 2 3 1
L
L
L
L
L
L
1 3
1 2
2 3
2 1
3 2
3 1
2 3 2 1
3 2 3 1
1 3 1 2
3 1 3 2
1 2 1 3
2 1 2 3
L
L
L
L
L
L
1 3
1 2
2 3
2 1
3 2
3 1
3 1 2 2
2 1 3 3
3 2 1 1
1 2 3 3
2 3 1 1
1 3 2 2
Figure 2.5: The 30 standard token configurations of Group a2 in T (G; (2, 2, 2))
operations. Thus T (θ0 ; (2, 2, 2)) has at most 2 components. As described previously, two standard token configurations are in the same component if and only if one can be obtained from the other by using operations U and L only. However, by applying the operations U and L to each standard token configuration in Figures 2.4 and 2.5, we always get another token configuration in the same figure. Therefore, T (θ0 ; (2, 2, 2)) is not connected and has 2 components.
By considering all the standard token configurations, we find that T (θ0 ; (2, 2, 1, 1)) has 2 components, T (θ0 ; (2, 1, 1, 1, 1)) has 3 components, and T (θ0 ; (1, 1, 1, 1, 1, 1)) has 6 components. The last case was already proved by Wilson [28]. Lemma 2.11 The labelled token graph T (θ0 ; (3, 1, 1, 1)) is connected.
Proof. We prove by using Lemma 2.4. Let {11 , 12 , 13 , 2, 3, 4} be the multiset of tokens, and α any token configuration in T (θ0 ; (3, 1, 1, 1)).
32
First, we show that a token 1 can be improperly swapped with a token different from 1. The following are the steps to improperly swap the tokens 11 and 2. For other pairs, we can do in a similar way. Step 1: Move tokens so that 3 occupies v0 . Step 2: Move tokens on the 6cycle until 4 is on a middle vertex, and the other middle vertex is unoccupied. Then move 3 to this vertex. Step 3: Move tokens on the 5cycle which 2 is on until 1 and 2 are on the middle vertices, so we now have that 11 , 12 , 13 , and 2 are on the same 5cycle. Step 4: Improperly swap 11 and 2. Step 5: Move all the tokens we moved in the previous steps backward to make 3 and 4 go back to their initial positions. Next, we show that any two tokens i, j ∈ {2, 3, 4} can be improperly swapped. Here we show only that the tokens 2 and 3 can be improperly swapped. For other pairs, we can so do in a similar way. Let α(vx ) = 11 , α(vy ) = 2, and α(vz ) = 3 for some x, y, z ∈ {0, 1, . . . , 6}. We first improperly swap 11 and 2. Note that now 11 may or may not be on vy . We then improperly swap the token 1 occupying vy with 3. Finally, we improperly swap the token 1 occupying vz with 2. Lemma 2.12 The labelled token graph T (θ0 ; (1, 1, 1, 1, 1)) is connected.
Proof. We prove by using Lemma 2.4.
Let α be any token configuration in
T (θ0 ; (1, 1, 1, 1, 1)), and t1 and t2 tokens in α. We first move some tokens to make t1 occupy v0 . Then rotate the tokens on the outer cycle until there is an unoccupied vertex, which is adjacent to t1 , t2 , and another unoccupied vertex. We 33
now can easily swap t1 and t2 . Then move all the tokens we moved in the previous steps backward until we get the token configuration, which is the same as α except that t1 and t2 are swapped.
We now have all the lemmas which we need for the case G is the graph θ0 . Next, we consider 2connected graphs, and finally just connected graphs. Lemma 2.13 Let G be a 2connected graph different from a cycle or the graph θ0 , k1 + k2 + · · · + kp ≤ n(G) − 1, and k1 ≥ 2. Then T (G; (k1 , k2 , . . . , kp )) is connected.
Proof. It is enough to show the case k1 + k2 + · · · + kp = n(G) − 1 only. By Theorem 2.1, we only have to consider the case that G is bipartite, and we have that T (G; (k1 , k2 , . . . , kp )) has at most two components. Let α and β be any token configurations in T (G; (k1 , k2 , . . . , kp )). By considering all tokens are different, let α0 and β 0 be token configurations in T (G; n(G) − 1) induced by α and β, respectively. Case 1: α0 and β 0 have their unoccupied vertices at odd distance. If α0 (β 0 )−1 is an odd permutation, we are done. Suppose this is not the case. Let α0 be the same token configuration as α except that the tokens 11 and 12 are swapped. Thus α0 and β are in the same component of T (G; (k1 , k2 , . . . , kp )). Then we are done since α and α0 are the same token configuration in T (G; (k1 , k2 , . . . , kp )). Case 2: α0 and β 0 have their unoccupied vertices at even distance. Similar to Case 1, if α0 (β 0 )−1 is an even permutation, then we are done. Otherwise, let α0 be the same token configuration as α except that the tokens 11 and 12 are swapped.
34
Lemma 2.14 Let G be a 2connected graph different from a cycle. If k ≤ n(G) − 2, then T (G; k) is connected.
Proof. By Lemma 2.12, we have that T (θ0 ; (1, 1, 1, 1, 1)) = T (θ0 ; 5) is connected. Then, by Proposition 2.6, we are done if G is the graph θ0 . Now we suppose that G is not θ0 . By Lemma 2.13, T (G; ( 2, 1, . . . , 1 )) is connected. Then T (G; k) is also  {z } n(G) − 2 terms
connected by Proposition 2.6. Lemma 2.15 Let H be a 2connected graph, and G the graph obtained from H by adding one vertex, which is connected to a vertex of H. Then T (G; n(G) − 2) is connected.
Proof. Let uv be the added edge, where d(u) = 1 and d(v) ≥ 2, and α any token configuration in T (G; n(G) − 2). Case 1: The graph H is a cycle. We may assume that in α all tokens are on the cycle (otherwise, we can move some tokens to get it since G is connected). It is enough to show that any two consecutive tokens on the cycle can be swapped. Suppose we want to swap consecutive tokens t1 and t2 . Then we move the tokens on the cycle until v is unoccupied and is between t1 and t2 . Note that u is now unoccupied. Then we can easily swap t1 and t2 by moving through the vertex u. Case 2: The graph H is not a cycle. By Lemma 2.14, T (H; n(H) − 2) is connected. Thus any two tokens in αH can be swapped. Since H is 2connected, dH (v) ≥ 2. Let x and y be neighbors of v in H. Since G is connected, we may assume that v and x are the two unoccupied vertices 35
in α. We can see that the tokens on u and on y can be swapped by moving through the vertex x. Hence any two tokens in α can be swapped, so we are done. Lemma 2.16 Let G1 and G2 be 2connected graphs containing a vertex v1 and v2 , respectively, and G the graph resulting from combining G1 and G2 by identifying the vertices v1 and v2 . Then T (G; n(G) − 2) is connected.
Proof. Let u1 be a vertex in G1 which is adjacent to v1 , and u2 a vertex in G2 which is adjacent to v2 . Let v be the vertex in G, which results from identifying the vertices v1 and v2 . Thus v is adjacent to u1 and u2 in G. Let H1 and H2 be the subgraphs of G induced by V (G1 ) ∪ {u2 } and V (G2 ) ∪ {u1 }, respectively. By Lemma 2.15, T (H1 ; n(H1 ) − 2) and T (H2 ; n(H2 ) − 2) are connected. Let α be any token configuration in T (G; n(G) − 2). We can assume that v and u1 are unoccupied in α; otherwise, we can move some tokens in α to get another token configuration such that v and u1 are unoccupied. Since T (H1 ; n(H1 ) − 2) is connected, any two tokens on the vertices of H1 in α can be swapped. Also, since T (H2 ; n(H2 ) − 2) is connected, any two tokens on the vertices of H2 in α can be swapped. Since H1 and H2 share the token on u2 , any two tokens in α can be swapped.
The blockcutvertex graph of a connected graph G, denoted by bc(G), is the graph whose vertices are the blocks and cutvertices of G, and the edges of bc(G) join cutvertices with those blocks to which they belong. An endblock of G is a block, which is of degree 1 in bc(G). Thus every endblock contains only one cutvertex of G. Lemma 2.17 Let G be a connected graph with connectivity 1, and l a positive integer. If G does 36
not contain a separating path of size l, then there exists an endblock B in G such that G\(V (B)\{vB }) is connected and does not contain a separating path of size l, where vB is the cutvertex of G in B.
Proof. Let B0 be any endblock in G. Take an endblock B of maximum distance from B0 in bc(G). Thus G\(V (B)\{vB }) is connected, where vB is the cutvertex of G in B. Suppose for a contradiction that G\(V (B)\{vB }) has a separating path P of size l. Since G has no separating path of size l, vB is an interior vertex of P . Then there are two P components. One component contains B0 , and the other contains another endblock, which is farther from B0 than B is. This is a contradiction.
We call an endblock B according to Lemma 2.17, a good endblock.
Proof of Theorem 2.2. (⇐) It is easy to see that if G is disconnected, k1 + k2 + · · · + kp = n(G), or G is a path, then T (G; (k1 , k2 , . . . , kp )) is disconnected. By Lemmas 2.9, 2.10, and Theorem 2.1, we are done when the fourth, fifth, or sixth condition holds. Next, we suppose that G is a connected graph with connectivity 1, other than a path, n(G) − (k1 + k2 + · · · + kp ) = l ≥ 1, and G contains a separating path P = v1 v2 . . . vl . If l = 1, let G1 ∗ be any component of G\v1 , and G1 and G2 the subgraphs of G induced by V (G1 ∗ )∪{v1 } and V (G)\V (G1 ∗ ), respectively. If l ≥ 2, let G1 and G2 be the two P components of G such that G1 contains v1 and G2 contains vl . We prove the labelled token graph is disconnected by showing that there are two token configurations, which are in different components of T (G; (k1 , k2 , . . . , kp )). Case 1: n(G1 ) ≥ k1 . 37
Let α be a token configuration such that v1 , v2 , . . . , vl are all unoccupied, and all the tokens with label 1 are in G1 \v1 . Let u be a vertex such that α(u) = 1, and v a vertex in G2 \vl . Thus α(v) = c for some c 6= 1. Let β be the same token configuration as α except that β(u) = c and β(v) = 1. Since the token 1 on u in α cannot be moved to the vertex v (it can go as far as to vl ), β is not reachable from α. Case 2: n(G1 ) < k1 . Let α be a token configuration such that v1 , v2 , . . . , vl are all unoccupied, and each vertex in G1 \v1 contains a token 1. Let u ∈ V (G1 )\{v1 } (so α(u) = 1), and v a vertex in G2 \vl such that α(v) = c for some c 6= 1. Let β be the same token configuration as α except that β(u) = c and β(v) = 1. Since the token c on v in α cannot be moved to the vertex u (it can go as far as to v1 ), β is not reachable from α. (⇒) We prove necessity by contrapositive. Suppose that all the conditions 17 do not hold. Thus G is connected, k1 + k2 + · · · + kp ≤ n(G) − 1, and G is not a path. Lemma 2.9 completes the proof when G is a cycle. If G is the graph θ0 , we have T (θ0 ; (3, 1, 1, 1)) and T (θ0 ; (1, 1, 1, 1, 1)) are connected by Lemmas 2.11 and 2.12. For the other numbers of tokens, we are done by Properties 2.6 and 2.7. If G is a 2connected graph, then we are done by Theorem 2.1 and Lemmas 2.13 and 2.14. We now suppose that G is a connected graph with connectivity 1, which does not contain a separating path of size l, where l = n(G) − (k1 + k2 + · · · + kp ). Since G has connectivity 1, G contains a separating path of size 1. Thus l ≥ 2. We will prove that T (G; n(G) − l) is connected by induction on the number of blocks in G, and then we will have T (G; (k1 , k2 , . . . , kp )) is connected by Proposition 2.7. Base Step: There are two blocks in G. 38
Since G is not a path, G has to be a graph in Lemma 2.15 or 2.16. Then T (G; n(G) − 2) is connected. Since l ≥ 2, T (G; n(G) − l) is also connected. Induction Step: There are m ≥ 3 blocks in G. Let B be a good endblock in G and H the subgraph of G induced by [V (G)\V (B)]∪ {vB }, where vB is the cutvertex of G in B. By Lemma 2.17, we have that H is connected and has no separating path of size l. It is easy to see that H has m − 1 ≥ 2 blocks, so H has connectivity 1. Then by the induction hypothesis, T (H; n(H) − l) is connected. Let vB0 be a vertex of H which is adjacent to vB , and B 0 the subgraph of G induced by V (B)∪{vB0 }. By Lemma 2.15, T (B 0 ; n(B 0 )−2) is connected, so T (G; n(B 0 )−2) is connected by Proposition 2.8. Case 1: n(H) ≤ l. Then n(G)−l = (n(H)+n(B 0 )−2)−l ≤ (l +n(B 0 )−2)−l = n(B 0 )−2. Therefore, T (G; n(G) − l) is connected by Proposition 2.6. Case 2: n(H) ≥ l + 1. We claim that H is not a path. Indeed, if H is the path v1 v2 · · · vl+1 · · · vm for some m ≥ l + 1, then v2 v3 · · · vl+1 is a separating path of size l in G, which is a contradiction. If dH (vB ) ≥ 2, choose u = vB , x = vB0 , and y another neighbour of vB in H. Otherwise, let u be the vertex nearest to vB in H such that dH (u) ≥ 3 (u exists since H is not a path). Then there is only one path from u to vB , and it is of size less than l since G does not contain a separating path of size l. Then let x and y be neighbours of u in H which are farther from vB than u is.
39
Let α be any token configuration in T (G; n(G) − l). We can assume that in α, there are n(B 0 ) − 2 tokens on B 0 such that vB and vB0 are unoccupied, and there are n(H) − l ≥ 1 tokens on H such that x and the vertices on the path from u to vB are all unoccupied while the vertex y is occupied. Otherwise, we can always move some tokens to get a token configuration with such properties from α since G is connected. Since T (B 0 ; n(B 0 ) − 2) and T (H; n(H) − l) are connected, any two tokens on B 0 and any two tokens on H can be improperly swapped in α. So we need to show only that in α there is a token on B 0 and a token on H which can be swapped. Let t1 be the token which occupies y, and t2 the token on B 0 which is on a neighbour of vB . We now can improperly swap the tokens t1 and t2 by moving through the vertex x. This completes the proof of Theorem 2.2.
We go back to Lemma 2.14 now. The proof of this lemma as previously given uses the result of Theorem 2.1, which was proved by using algebraic methods. Here we give another proof, using graph theoretical methods only.
Another Proof of Lemma 2.14. We prove the lemma by using Lemma 2.5. Let G be a 2connected graph different from a cycle, α any token configuration with at most n(G) − 2 different tokens, v any unoccupied vertex in α, and u any occupied vertex in α, say u contains a token t. We will show that in α, the tokens t and φ (the empty token on v) can be improperly emptytoken swapped. Since G is 2connected, there are two internally disjoint paths P1 and P2 between u and v. If one of these two paths does not contain any token, then we can easily move t from u to v, so we are done. Suppose this is not the case. Since k ≤ n(G)−2, there is an unoccupied vertex w such that w 6= v. Let s1 and s2 be the tokens which are nearest to v on P1 and P2 , respectively. 40
Case 1: There is a vertex of G which is not on P1 ∪ P2 . Subcase 1.1: The vertex w is not on P1 ∪ P2 . Take a path Pw from w to some vertex x on P1 ∪ P2 . Let y be the vertex on Pw which is adjacent to x. Then do the following (if necessary), (1) move the tokens on Pw forward to w to make y unoccupied, (2) move the tokens on P1 ∪ P2 in anticlockwise direction until t is at x, (3) move t from x to y along Pw , (4) move the tokens on P1 ∪ P2 in anticlockwise direction until x is between the tokens s1 and s2 , (5) move t from y back to x along Pw , (6) move the tokens on P1 ∪ P2 in clockwise direction until they are at their destination positions, (7) move the tokens which we moved in (1) back to their initial positions. Subcase 1.2: The vertex w is on P1 ∪ P2 , but there is another vertex z which is not on P1 ∪ P2 . We can suppose that the vertices which are not on P1 ∪ P2 are all occupied by tokens. Otherwise, we are done by Subcase 1.1. Take a path Pz from z to some vertex x on P1 ∪ P2 . Let s be the token on Pz which is the nearest to x but not on x. To use Subcase 1.1, we will move s to the vertex w. We do the following (if necessary), (1) move the tokens on P1 ∪ P2 in anticlockwise direction until the free space on w arrives at x, 41
(2) move s to x along Pz , (3) move the tokens on P1 ∪ P2 in clockwise direction until s arrives at w. Now we can use Subcase 1.1 to move t from u to v, and then we move the token s back to its initial position. Case 2: All vertices are on P1 ∪ P2 . Since G is not a cycle, there exists a chord xy on P1 ∪ P2 for some x, y ∈ V (G). We move the tokens on P1 ∪ P2 in anticlockwise direction until the token t arrives at x or the empty token φ (on v initially) arrives at y. At the time of arrival, we may assume that t is on a vertex z1 , and φ is on a vertex z2 . If z1 = x and z2 = y, we can easily move t from x to y along the chord, and then move the tokens on P1 ∪P2 in clockwise direction until we get the wanted token configuration. Otherwise, we can find two internally disjoint paths P10 and P20 from z1 to z2 such that there is another vertex which is not on P10 ∪ P20 . By Case 1, we can move t from z1 to z2 . Finally, we move the tokens on P1 ∪ P2 in clockwise direction until t arrives at v, and the other tokens are back to their initial positions.
2.4
Proof of Theorem 2.3
Note that in this section, we use some terminology and notation from the previous section. According to the graph θ0 in Figure 2.1, we denote a token configuration α of θ0 which has α(vi ) = ti for all i = 0, 1, . . . , 6, by [t0 , t1 , t2 , t3 , t4 , t5 , t6 ]. For example, if α is the top left token configuration in Figure 2.4, then α = [2, φ, 2, 3, 3, 1, 1]. Let G be a connected graph with connectivity 1, n(G) − (k1 + k2 + · · · + kp ) = 1, and vB a cutvertex of a block B in G. Given a token configuration α, we can
42
see that even though αvB is not unique, τ (αvB B ) is unique. This means tokens in τ (αvB B ) can be moved to vertices in B only. We get the following lemma. Lemma 2.18 Let G be a connected graph with connectivity 1, n(G) − (k1 + k2 + · · · + kp ) = 1, and α and β token configurations of G. Then α is reachable from β if and only if αvB B is reachable from βvB B for every block B in G.
Proof of Theorem 2.3. (⇐) It is easy to see that α and β are in the same component of T (G; (k1 , k2 , . . . , kp )) if one of the first three conditions holds. Suppose that G is the graph θo and (k1 , k2 , . . . , kp ) = (2, 2, 2). We have proved that T (θ0 ; (2, 2, 2)) is not connected and has 2 components. One component contains 60 standard token configurations, shown in Figure 2.4 (and some other token configurations). We can see that all the (1,1)standard token configurations of which the cyclic order of tokens on the lower 5cycle is (2, 2, 3, 3) are in this component. The other component contains 30 standard token configurations, shown in Figure 2.5 (and some other token configurations), and all the (1,1)standard token configurations of which the cyclic order of tokens on the lower 5cycle is (2, 3, 2, 3) are in this component. Thus, if α0 and β 0 are in the same group (stated in 4(a) in the theorem), then α and β are in the same component of T (θ0 ; (2, 2, 2)). Next, we suppose that (k1 , k2 , . . . , kp ) = (2, 2, 1, 1). We relabel the two tokens with label 3 in all standard token configurations in Figure 2.4 into two possible ways, say using labels 3 and 4. Then we get two copies of Figure 2.4. One copy contains the standard token configuration [2, φ, 2, 3, 4, 1, 1], and the other contains [2, φ, 2, 4, 3, 1, 1]. We do a similar relabelling in Figure 2.5, so we get two copies of Figure 2.5. One copy contains [2, φ, 3, 2, 4, 1, 1], and the other contains [2, φ, 4, 2, 3, 1, 1]. Next, we prove that the standard token configurations from the
43
two copies of Figure 2.4 are in the same component of T (θ0 ; (2, 2, 1, 1)) by showing a path from [2, φ, 2, 3, 4, 1, 1] to [2, φ, 2, 4, 3, 1, 1]. This path can be obtained by the following sequence of operations: L, L, U, L, U, L, U, L, U, U, L, L, U, U, U . Similarly, we give a path from [2, φ, 3, 2, 4, 1, 1] to [2, φ, 4, 2, 3, 1, 1] to show that the standard token configurations from the two copies of Figure 2.5 are in the same component. This path can be obtained by the following sequence of operations: L, U, L, L, U, L, U, L, U, U, L, U, L, L, L, U, U, U, L, U, U, U . Thus we have two groups of standard token configurations in T (θ0 ; (2, 2, 1, 1)) such that standard token configurations which are in the same group are in the same component of T (θ0 ; (2, 2, 1, 1)). We can see that one group, called Group A1 , contains all the (1,1)standard token configurations of which the cyclic order of tokens on the lower 5cycle is (2, 2, 3, 4) or (2, 2, 4, 3). And the other group, called Group A2 , contains all the (1,1)standard token configurations of which the cyclic order of tokens on the lower 5cycle is (2, 3, 2, 4) or (2, 4, 2, 3). Hence, if α0 and β 0 are in the same group (stated in 4(a) in the theorem), then α and β are in the same component of T (θ0 ; (2, 2, 1, 1)). Now we suppose that (k1 , k2 , . . . , kp ) = (2, 1, 1, 1, 1). Then we relabel the two tokens with label 2 in all standard token configurations in Group A1 into two possible ways, say using labels 2 and 5. So we get two copies of standard token configurations from Group A1 , called Groups B1 and B2 , and two copies of standard token configurations from Group A2 , called Groups B30 and B300 . Without loss of generality, we suppose that Group B30 contains [2, φ, 4, 5, 3, 1, 1], and Group B300 contains [5, φ, 4, 2, 3, 1, 1]. Then we show that there are three groups of standard token configurations in T (θ0 ; (2, 1, 1, 1, 1)) such that standard token configurations in the same group are in the same component. For this, it suffices to show a path from [2, φ, 4, 5, 3, 1, 1] to [5, φ, 4, 2, 3, 1, 1], obtained by the sequence of operations: L, U, L, L, U, L, U, L, U, U, L, L, U, U, L, L, L, U, U, U, L, L, L, U, U, U, L, L, U, U, U, L, 44
L, L. Then we use B3 to denote the group formed from the combination of B30 and B300 . Again, if α0 and β 0 are in the same group (stated in 4(b) in the theorem), then α and β are in the same component of T (θ0 ; (2, 1, 1, 1, 1)). We next suppose that (k1 , k2 , . . . , kp ) = (1, 1, 1, 1, 1, 1). By relabelling the two tokens with label 1 in all standard token configurations in Groups B1 , B2 , and B3 into two possible ways, say using labels 1 and 6, we get two copies of standard token configurations from each group. So we now have six groups of standard token configurations such that standard token configurations in the same group are in the same component of T (θ0 ; (1, 1, 1, 1, 1, 1)). Similarly, if α0 and β 0 are in the same group (stated in 4(c) in the theorem), then α and β are in the same component of T (θ0 ; (1, 1, 1, 1, 1, 1)). Thus we are now done when G is the graph θ0 . When G is a 2connected bipartite graph other than a cycle and there are n(G)−1 different tokens, we are done by Theorem 2.1. Next, we suppose that G is a connected graph with connectivity 1, other than a path, n(G) − (k1 + k2 + · · · + kp ) = l ≥ 2, P1 , P2 , . . . , Pm are all the separating paths of size l in G, and τ (αi Gi,1 ) = τ (βi Gi,1 ) and τ (αi Gi,2 ) = τ (βi Gi,2 ) for all i = 1, 2, . . . , m. We prove that α and β are in the same component of the labelled token graph by induction on the number of separating paths of size l in G. Base Step: There is only one separating path P1 = v1,1 v1,2 . . . v1,l of size l in G. Let G1,1 and G1,2 be the two P1 components of G. If G1,1 or G1,2 is a path, then it has to be a path of length 2; otherwise, there are at least two separating paths of size l in G. Let G01,1 and G01,2 be the subgraphs of G induced by V (G1,1 ) ∪ {v1,2 , v1,3 , . . . , v1,l } and V (G1,2 ) ∪ {v1,1 , v1,2 , . . . , v1,l−1 }, respectively. Then G01,1 and G01,2 do not contain a separating path of size l, τ (α1 G01,1 ) = τ (β1 G01,1 ), and τ (α1 G01,2 ) = τ (β1 G01,2 ). If G1,1 is a path of length 2, then there is only one token on 45
α1 G01,1 and β1 G01,1 , so α1 G01,1 = β1 G01,1 . Obviously, α1 G01,1 is reachable from β1 G01,1 . Suppose G1,1 is not a path, so G01,1 is not a path. Since l ≥ 2, G01,1 cannot be a cycle, the graph θ0 , or a 2connected bipartite graph. Since G01,1 does not contain a separating path of size l, its labelled token graph is connected by Theorem 2.2. Thus α1 G01,1 is reachable from β1 G01,1 . Similarly, α1 G01,2 is reachable from β1 G01,2 . We can conclude that α1 is reachable from β1 , so α is reachable from β. Induction Step: There are m ≥ 2 separating paths of size l in G. For each i = 1, 2, . . . , m let Pi = vi,1 vi,2 . . . vi,l , Gi,1 and Gi,2 the two Pi components, and G0i,1 and G0i,2 the subgraphs of G induced by V (Gi,1 ) ∪ {vi,2 , vi,3 , . . . , vi,l } and V (Gi,2 ) ∪ {vi,1 , vi,2 , . . . , vi,l−1 }, respectively. Then there exists a separating path Pj for some j such that one of G0j,1 and G0j,2 does not contain a separating path of size l. Without loss of generality, we may assume that j = 1 and G01,1 does not contain a separating path of size l. By the same arguments used in the base step, we can have that α1 G01,1 is reachable from β1 G01,1 . Let H be the subgraphs of G induced by V (G)\(V (G1,1 )\{v1,1 }). Thus there are m − 1 separating paths of size l in H. By the induction hypothesis, we have that α1 H is reachable from β1 H . We can conclude that α1 is reachable from β1 , so α is reachable from β. Finally, we suppose that the condition 7 of the theorem holds. By using the previous cases, we can conclude that αvB B is reachable from βvB B for every block B in G. Hence α is reachable from β by Lemma 2.18. (⇒) We prove necessity by contrapositive. Suppose that all the conditions 17 do not hold. We then show that α and β are in different components of the labelled token graph. It is easy to get the result if G is a path or a cycle.
46
First, we suppose G is the graph θ0 . Since T (G; (k1 , k2 , . . . , kp )) is not connected, (k1 , k2 , . . . , kp ) is (2,2,2), (2,2,1,1), (2,1,1,1,1), or (1,1,1,1,1,1) by Theorem 2.2. As we described previously, two standard token configurations are in the same component if and only if one configuration can be obtained from the other by a finite sequence of operations U and L only. By applying the operations U and L to each standard token configuration in each group (the groups we constructed previously such as Groups A1 and A2 ), we always get another token configuration in the same group. Thus, if α0 and β 0 are in different groups (the groups we stated in the condition 4 of the theorem such as Groups a1 and a2 ), then α and β are in different components of the labelled token graph. When G is 2connected, we are done by Theorem 2.1 and Lemmas 2.13 and 2.14. Next, we suppose that G is a connected graph with connectivity 1, other than a path, n(G) − (k1 + k2 + · · · + kp ) = l ≥ 2, and there is a separating path P1 = v1,1 v1,2 . . . v1,l such that τ (α1 G1,1 ) 6= τ (β1 G1,1 ) or τ (α1 G1,2 ) 6= τ (β1 G1,2 ). Without loss of generality, we may assume that τ (α1 G1,1 ) 6= τ (β1 G1,1 ). Hence there is a token t which appears in α1 G1,1 more often than in β1 G1,1 . To get β1 from α1 , we need to move at least one token t on G1,1 in α1 into some vertex in V (G1,2 )\{v1,l }. This is impossible because of the separating path P1 , so β1 is not reachable from α1 . Hence α and β are in different components of the labelled token graph. Finally, we suppose that G is a connected graph with connectivity 1, other than a path, n(G) − (k1 + k2 + · · · + kp ) = 1, and there is a block B such that τ (αvB B ) 6= τ (βvB B ) or it does not satisfy any cases in the condition 7. Case 1: τ (αvB B ) 6= τ (βvB B ).
47
Then there is a token t which appears in αvB B more often than in βvB B . To get βvB from αvB , we need to move at least one token t on B in αvB into some vertex in V (G)\V (B), which is impossible. Hence βvB is not reachable from αvB , so α and β are in different components Case 2: None of the cases 7(a), 7(b), 7(c), or 7(d) holds. We may assume that τ (αvB B ) = τ (βvB B ); otherwise, we are done by Case 1. If B is a path, it has to be of length 2 since it is a block. Then there is only one token in αvB B , so T (B; τ (αvB B )) is connected. This contradicts the assumption that B does not satisfy any cases in the condition 7. Thus B is a block different from a path. By using the previous cases, we can conclude that αvB B is not reachable from βvB B . Thus α is not reachable from β by Lemma 2.18.
Now, we go back to Example 1.1. According to Figure 1.1, is it possible to reach β from α? To get the answer, we first transform the 15Puzzle to the grid graph P4 × P4 . Then we get the corresponding token configurations α0 and β 0 of α and β, respectively, shown in Figure 2.6.
2
1
4
3
1
2
3
4
6
5
8
7
5
6
7
8
10 11 12
9
9
10 11 12
14 15 13
13 14 15
Figure 2.6: Corresponding token configurations α0 and β 0
We can see that α0 and β 0 have empty spaces at distance zero, and α0 (β 0 )−1 = (1 2)(3 4)(5 6)(7 8)(9 10)(9 11)(9 12)(13 14)(13 15) is an odd permutation. By 48
Theorem 2.3, since P4 × P4 is a 2connected bipartite graph different from a cycle, α0 and β 0 are in different components of the labelled token graph. Thus we cannot go from α to β.
49
Chapter 3
Miscellaneous Results on Labelled Token Graphs 3.1
Complexity of Finding Shortest Paths in Labelled Token Graphs
In this section, we consider the computational hardness of finding the shortest path between any two token configurations in labelled token graphs. Goldreich [15] proved that the problem of finding the shortest path between two token configurations in labelled token graphs such that all the tokens are different is NP hard by reducing 3ExactCover to it. Papadimitriou et al. [21] proved that the problem of finding the shortest sequence of moves to move the special token from one vertex to another vertex is NP hard (the other tokens are considered as just obstacles). They proved by reducing from the problem 3SAT in which each literal occurs at most twice. We now introduce the following problem, which is called the ShortestTokenMoveSequence (STMS) problem: Input: A connected graph G, a multiset of tokens (k1 , k2 , . . . , kp ), two token configurations α and β, and a positive integer N ;
50
Question: Is there a path of length at most N from α to β in the labelled token graph T (G; (k1 , k2 , . . . , kp ))? Theorem 3.1 Restricted to the case that the multiset of tokens is (k) (i.e., all tokens are the same), the problem STMS is in P.
Proof. Given two token configurations α and β of k identical tokens on G, let U = {u1 , u2 , . . . , uk } be the set of vertices containing a token in α, and V = {v1 , v2 , . . . , vk } be the one in β. We form a complete bipartite graph Kk,k with the parts U and V . We define the weight of each edge ui vj to be the length of a shortest path from ui to vj in G. It is wellknown that a perfect matching with minimum weight can be found in polynomial time (for instance, using the Hungarian method; see, e.g., Schrijver [24]). Let M be such a minimumweight perfect matching. Without loss of generality, we may assume that M = {u1 v1 , u2 v2 , . . . , uk vk }. For each i, let Pi be the path corresponding to the edge ui vi , wi the weight of ui vi , and W the total weight in M . It is obvious that to get β from α, we need at least W steps. Next, we show that we can find a path from α to β in the labelled token graph of length exactly W by induction on the total weight W . Base Step: W = 0. Then U = V , so α and β are the same token configuration. Thus there is of course a path of length 0 from α to β in the labelled token graph. Induction Step: W ≥ 1. Then there is an edge in M having nonzero weight. Without loss of generality, we may assume that the edge u1 v1 has weight w1 > 0 (i.e., u1 6= v1 ). 51
Case 1: V (P1 ) ∩ U = {u1 }. Then we move the token from u1 along P1 to v1 . Let α0 be the token configuration we just got and M 0 the perfect matching obtained from M which corresponds to α0 and β. We can see that M 0 has minimum weight in this new situation (otherwise, M is not a minimum weight perfect matching), and the total weight of M 0 is W − w1 . By the induction hypothesis, there is a path of length W − w1 in the labelled token graph from α0 to β. Combining the paths from α to α0 and from α0 to β gives us the wanted path of length W . Case 2: [V (P1 ) ∩ U ]\{u1 } = 6 φ. Without loss of generality, we may assume that u2 is the vertex in [V (P1 )∩U ]\{u1 } nearest to v1 . Note that the path from u1 to u2 along P1 and the path P2 have the vertex u2 in common only. Otherwise, there are paths from u1 to v2 and from u2 to v1 that give another perfect matching having smaller weight than M . Subcase 2.1: u2 6= v1 . Then we define the new paths P12 and P21 as follows. Let P12 be the path formed by going from u1 along P1 to u2 and then continue along P2 to v2 (since the path from u1 to u2 along P1 and the path P2 intersect only at u2 , P12 is a path), while P21 is just the path from u2 along P1 to v1 . It is clear that the sum of the lengths of P12 and P21 is the same as the sum for P1 and P2 . We now form a new perfect matching with the minimum weight by removing the edges u1 v1 and u2 v2 and adding the edges u1 v2 and u2 v1 , corresponding to the paths P12 and P21 , respectively. We can see that u2 is the only vertex in V (P21 ) ∩ U . Since u2 6= v1 , the edge u2 v1 has nonzero weight. Then we just follow the steps in Case 1 by moving the token from u2 along P21 to v1 . Subcase 2.2: u2 = v1 . 52
Thus u2 6= v2 . Again, if V (P2 ) ∩ U = {u2 }, we are done by following the steps in Case 1. If it is not the case, then we follow the steps in Case 2. We may assume that u3 is the vertex in [V (P2 ) ∩ U ]\{u2 } nearest to v2 . Then P3 cannot contain u1 or u2 ; otherwise, we can find another perfect matching having smaller weight than M . If u3 6= v2 , we are done using Subcase 2.1. Otherwise, we continue with u4 . We keep doing this until we get some l ∈ {1, 2, . . . , k} such that V (Pl ) ∩ U = {ul } and ul 6= vl . This must happen since U is finite. Then we finish the proof by following the steps in Case 1 (move the token from ul to vl along Pl ).
Recall that Goldreich [15] proved STMS is NP complete for the case Wilson considered (i.e., the tokens are all different). So somewhere between all tokens the same and all tokens different, the problem switches from being in P to being NP complete. The following theorem shows that it happens as soon as not all tokens are identical. We prove this by applying the ideas of the proof of Theorem 1 of Papadimitriou et al. [21] by reducing from the problem 3SAT. In their proof, they only move the unique special token from one vertex to the destination vertex and do not mind where the other tokens are at the end. In our proof, at the end we need to move the other tokens to their destinations as well. Theorem 3.2 Restricted to the case that there is one special token and the other tokens are all identical, the problem STMS is NPcomplete.
Proof. Recall that Kornhauser et al. [18] proved that the problem to decide if there is a path between any two token configurations, is decidable in polynomial time. They also showed that at most O((n(G))3 ) moves are needed between any two reachable token configurations. This shows that STMS is in NP.
53
To prove that the problem STMS is NP hard, we use a reduction from 3SAT. Given an instance of a 3SAT Boolean formula which is in conjunctive normal form, we construct a graph G, token configurations α and β, and choose a number N as follows (see Figures 3.1 and 3.2 for an example). The graph G consists of p variable gadgets (the cycles on the left), where p is the number of variables in the formula, q clause gadgets (the vertices on the right), where q is the number of clauses in the formula, a destination vertex (the rightmost vertex) called v2 , and some paths starting from vertices on variable gadgets. Let M be the maximum number of occurrence of any literal in the formula. For each variable x, we form a variable gadget by two paths corresponding to each variable and its negated form, called Px and Px¯ . The path Px contains vertices x1 , x2 , . . . , xM which separate the path into M + 1 parts, each of length 3r, where r = c(p + q) for some positive integer c so that 2r2 > 5M rp + 3rp + 5rq + 3r (c is large enough). Similarly, the path Px¯ contains vertices x¯1 , x¯2 , . . . , x¯M which separate the path into M + 1 parts, each of length 3r. Since M is the maximum number of the number of occurrence of each literal in the formula, x and x¯ occur in at most M clauses. For each appearance of x in the clauses, we form a path of length 2r from a vertex in {¯ x1 , x¯2 , . . . , x¯M } to the corresponding clause gadget. For each vertex in {¯ x1 , x¯2 , . . . , x¯M } which does not have a path to any clause gadget, we construct a path of length r from it to a new vertex. We create M paths starting from the vertices on Px¯ so that they are mutually disjoint. Similarly, we form M disjoint paths starting from the vertices on Px . We construct token configurations α and β of G corresponding to the given formula in similar way as the example shown in Figures 3.1 and 3.2 (this example corresponds to the formula (x ∨ y ∨ z) ∧ (x ∨ y ∨ z) ∧ (x ∨ y ∨ z)), and choose
54
N = 5M rp + 3rp + 5rq + 3r. Note that the special token has label t, and all the other tokens are identical.
v1
t V V
Variable Gadgets
V V
V
V
v2
Clause Gadgets
A vertex without a token A vertex with a token A path of length 1r, filled with tokens except for the vertex of degree one A path of length 2r, filled with tokens except for the middle vertex A path of length 3r with no tokens at interior vertices
Figure 3.1: Starting token configuration α of G, corresponding to the formula (x ∨ y ∨ z) ∧ (x ∨ y ∨ z) ∧ (x ∨ y ∨ z)
Now, we claim that the formula is satisfiable if and only if we can reach β from α within N steps. First, we suppose that the formula is satisfiable. We will show that within N steps, we can move the token t from the vertex v1 to the vertex v2 , passing through all the variable gadgets and the clause gadgets, and finally move the other tokens to their final positions. Consider a variable x, and suppose x is set to be “true” in a feasible assignment. We will move the token t through the variable gadget of x along the path Px . We need r steps for each token on Px to be cleared out by pushing the tokens to the end of the rlength paths or to the middle of the 2rlength paths. Note that
55
v1
t V V
Variable Gadgets
V V
V
V
v2
Clause Gadgets
A vertex without a token A vertex with a token A path of length 1r, filled with tokens except for the vertex of degree three A path of length 2r, filled with tokens except for the vertex of degree three A path of length 3r with no tokens at interior vertices
Figure 3.2: Final token configuration β of G, corresponding to the formula (x ∨ y ∨ z) ∧ (x ∨ y ∨ z) ∧ (x ∨ y ∨ z)
any other way requires at least 3r steps. If x is “false”, we do the same via the path Px . Next, we will move t through each clause gadget occupied by a token initially. Since every clause is satisfied, at least one of the three 2rlength paths connected to each clause gadget has the middle vertex still unoccupied. Then we can move the token on each clause gadget off in r steps by pushing the tokens to the middle on this path, and then t can pass that clause gadget. Hence we can bring the token t from v1 to v2 in [M rp + (M + 1)(3r)p] + [rq + (q + 1)(3r)] steps, and we need rq+M rp steps to move the other tokens to their final destinations. Therefore, we can get β from α in exactly N steps. Conversely, suppose that for every choice of the variables to be true or false, at 56
least one of the clauses is not satisfied. In the step of moving the token on this clause gadget off from the route of t, we need at least 2r steps because the middle vertices of all the three 2rlength paths ending at that clause gadget are no longer empty. Thus the total number of steps to get β from α is more than N steps. Note that to let the token t make a short cut along a path packed with tokens, we need at least 2r2 > N steps. Since the reduction from the given instance of a 3SAT Boolean formula to the graph G, token configurations α and β, and integer N can be done in polynomial time, we can conclude that STMS is NP hard, and therefore is NP complete. Corollary 3.3 The problem STMS remains NPcomplete for any other multiset of tokens which does not restrict the total number of tokens and allow at least two types of tokens.
3.2
Connectivity of Labelled Token Graphs and Forbidden Minors
In this section, we give another way to consider whether the labelled token graph of a given graph G with a multiset of tokens (k1 , k2 , . . . , kp ) is disconnected by considering the existence of some forbidden minors. The details can be found in the following theorem. Theorem 3.4 For each multiset of tokens (k1 , k2 , . . . , kp ), there exists a finite collection of connected graphs H1 , H2 , . . . , Hn , such that for each connected graph G with n(G) > k1 + k2 + · · · + kp we have
57
T (G; (k1 , k2 , . . . , kp )) is disconnected ⇔ G has none of H1 , H2 , . . . , Hn as a minor. As a consequence, for each multiset (k1 , k2 , . . . , kp ), there exists a polynomial time algorithm (in n(G)) to decide if the labelled token graph of a given graph is disconnected.
Below, we give some theorems which will be used in the proof of Theorem 3.4. They are wellknown and can be found, e.g., in [10]. Proposition 3.5 A relation ≤ is a wellquasiordering on a set X if and only if it is a quasiordering without infinite descent and without infinite antichains on elements of X. Theorem 3.6 (Robertson & Seymour [23]) The minor ordering is wellquasiordered on the class of finite graphs. Proposition 3.7 Let ≤ be a wellquasiordering on a set X, and P a ≤closed property on elements of X. Then the set of P forbidden elements is finite.
By Proposition 3.5 and Theorem 3.6, we can see that the minor ordering is a quasiordering without infinite descent and without infinite antichains on finite graphs. Since the class of finite connected graphs is a subset of the class of finite graphs, there is neither infinite descent nor infinite antichains on connected graphs under minor ordering. Hence the minor ordering is wellquasiordered on the class of finite connected graphs as well. Combining this result with Proposition 3.7 gives the following corollary. Corollary 3.8 If P is a minorclosed property on connected graphs, then the set of P forbidden 58
minors is finite.
For example, let P be the property of being planar on connected graphs. It is easy to see that P is minorclosed. Hence there are a finite number of P forbidden minors. According to Wagner’s theorem, the P forbidden minors are the complete graph K5 and the complete bipartite graph K3,3 . Theorem 3.9 (Robertson & Seymour [22]) Given a fixed graph H, there exists a polynomial time algorithm to decide if a given graph has H as a minor or not. Corollary 3.10 If P is a minorclosed property on connected graphs, then there exists a polynomial time algorithm to decide whether a given graph has property P .
Proof of Theorem 3.4. To prove the theorem, it suffices to show that the property of being disconnected of labelled token graphs on connected graphs is closed under minor ordering. We then use Corollary 3.10 to complete the rest of the proof. Let (k1 , k2 , . . . , kp ) be a multiset of tokens, G a connected graph, H a connected minor of G, and k < n(H) ≤ n(G), where k = k1 + k2 + · · · + kp . Suppose T (G; (k1 , k2 , . . . , kp )) is disconnected. We will show that T (H; (k1 , k2 , . . . , kp )) is disconnected by showing the following. Claim 1: The graph H can be obtained from G by a sequence of edge contractions first and then edge deletions. For each X ∈ V (H), let the branch set of X, VX , be the set of vertices of G, which are contracted to X. Note that the subgraph of G induced by VX is connected 59
for all X ∈ V (H), and for all Y, Z ∈ V (H), Y Z ∈ E(H) if and only if there are S y ∈ VY , z ∈ VZ such that yz ∈ E(G). Now let U = V (G)\ X∈V (H) VX . Choose v ∈ U such that v is adjacent to some vertex in some branch set. Then we add v to one of these branch sets and keep doing this process until U is empty. We can do this because G is connected and U is finite. Then we can obtain the graph H from G by first contracting all edges in each subgraph induced by each branch set, and then removing all edges which do not appear in H. Note that since G and H are connected, each operation in the sequence to obtain H transforms a connected graph to a connected graph. Claim 2: Assume F is a connected graph containing an edge uv, k < n(F ), and T (F ; (k1 , k2 , . . . , kp )) is disconnected. Then T (F/uv; (k1 , k2 , . . . , kp )) is disconnected. Note that F/uv is connected. Let α and β be token configurations of F , which are in different components of T (F ; (k1 , k2 , . . . , kp )). We may assume that in both α and β there is at most one vertex of u and v occupied by a token. Otherwise, since F is connected and k < n(F ), we can move some tokens in α (in β) to obtain another token configuration of F in which there is at most one vertex of u and v with a token on it. Let α0 and β 0 be the token configurations of F/uv induced by α and β, respectively. Then if there is a path from α0 to β 0 in T (F/uv; (k1 , k2 , . . . , kp )), we can also construct a path from α to β in T (F ; (k1 , k2 , . . . , kp )), which is a contradiction. Hence T (F/uv; (k1 , k2 , . . . , kp )) is disconnected. Claim 3: Assume F is a connected graph containing an edge e, F −e is connected, k < n(F ), and T (F ; (k1 , k2 , . . . , kp )) is disconnected. Then T (F −e; (k1 , k2 , . . . , kp )) is disconnected.
60
Note that each token configuration of F is a token configuration of F − e. Since T (F ; (k1 , k2 , . . . , kp )) is disconnected, we can find token configurations α and β of F which are in different components of T (F ; (k1 , k2 , . . . , kp )). Then they are in different components of T (F − e; (k1 , k2 , . . . , kp )). Hence T (F − e; (k1 , k2 , . . . , kp )) is disconnected.
Next, we give some examples of P forbidden minors, where P is the property of being disconnected of labelled token graphs on connected graphs. Example 3.11 If the multiset of tokens is (1, 1), then there are two P forbidden minors:
s
s @ @s
s s
s
s
If the multiset of tokens is (1, 1, 1), then there are five P forbidden minors: s @s s @ @ @s
s
s
s @ @s
s
s
s
s s @ @s @ @s
s
s s
s
s s s
s
s
If the multiset of tokens is (2, 1), then there are four P forbidden minors: s s @ @s @ @s
s
s
s
s @ @s
s
s
s s
s
61
s
s
s s s
s
s
For the case the multiset of tokens is (1, 1, 1, 1), the following graphs are P forbidden minors, but we are not sure yet if this is the complete list of P forbidden minors. s s s
s
s
s
s
s @ @s s
s
s @s s s @ P
[email protected] P @ Ps
s @ @s s s
s s s
s s @s s @ @ @s @ @s
s
s
s
s
s
s s s
s s @ @s
s
s
s
s @ @s s
s
s
s
s s s @ @s
s
s s s @ @s s
s
s
s
s
s
s
s
s s
62
s
s s @ @s @ @s
s
s @ @s s
s
s
s s @ @s @s s @ s s @ @s
s
Chapter 4
Strong kColour Graphs For a positive integer k and a graph G, the kcolour graph of G (introduced by Cereceda et al. [5]) is the graph that has the proper kvertexcolourings of G as its vertices, and two vertices are joined by an edge if they differ in colour on only one vertex of G. We denote the kcolour graph of G by Ck (G). We now introduce a subgraph of Ck (G), the strong kcolour graph of G, denoted by Sk (G). Its vertex set contains only proper kcolourings in which all k colours actually appear, and we call such a colouring a strong kcolouring. Questions regarding the connectivity of a kcolour graph have applications in reassignment problems of the channels used in cellular networks; see, e.g., [2, 17]. For some applications, it is required that all channels in a range are actually used. Such a labelling is sometimes called a “nohole” or “consecutive” labelling; see, e.g., [12, 19]. In terms of colourings, this corresponds to a strong kcolouring. And asking questions about the possibility to reassign channels in a cellular network can be done in such a way that all available channels are actually used. These problems can be expressed in finding paths in strong kcolour graphs. Questions related to the connectivity of a kcolour graph have been studied extensively : [5, 6, 8, 20]. In this note we initiate similar research on the connectivity of strong kcolour graphs : Given a positive integer k and a graph G, is Sk (G) connected? As an example, in Figures 4.1 and 4.2, we show the strong 3colour
63
graphs of the paths with 4 and 5 vertices, respectively. One is not connected while the other is connected.
Figure 4.1: The strong colour graph S3 (P4 )
Figure 4.2: The strong colour graph S3 (P5 )
We usually use lower case Greek letters α, β, γ, . . . to denote specific colourings, and lower case Latin a, b, c, . . . to denote specific colours. And to avoid trivial cases, we will always assume that k is greater than or equal to the chromatic number of G, and the number of vertices of G is at least k + 1.
64
4.1
Literature
The following are known results on kcolour graphs. We make them our goal to study on strong kcolour graphs. However, this thesis contains only some first results on strong kcolour graphs Cereceda et al. [5] gave some results on the connectivity of kcolour graphs such as if G is a graph with chromatic number k ∈ {2, 3}, then Ck (G) is not connected. On the other hand, they gave some graphs with chromatic number k ≥ 4 for which Ck (G) is not connected, and some kchromatic graphs for which Ck (G) is connected. In [6], they characterised the bipartite graphs for which C3 (G) is connected. They also proved that the problem to decide the connectedness of the 3colour graph of a bipartite graph is coNP complete In [7], they considered the problem of finding a path between two vertex 3colourings in 3colour graphs. They proved that it needs polynomial time to decide whether there is a path between them or not. They also showed that if a path exists, the algorithm uses O(n2 ) steps. Bonsma and Cereceda [3] proved that the problem to decide whether there is a path between two vertex kcolourings in kcolour graphs is PSPACE complete for all k ≥ 4. They also proved that the problem remains PSPACE complete for some specific graphs and the number k such as planar graphs with 4 ≤ k ≤ 6, or bipartite planar graphs with k = 4.
65
4.2
General Results on Connectivity of Strong kColour Graphs
For all k ≥ 2 and m, n ≥ 1, let α be a strong kvertexcolouring of a complete bipartite graph Km,n . Each colour that appears in one part of the partition cannot be used in the other part. Now we choose one colour from each part and recolour the graph by swapping these two colours on each vertex coloured with one of these colours. Let β be the resulting colouring, so β is strong as well. It is easy to see that there is no path in Sk (Km,n ) from α to β. Thus Sk (Km,n ) is not connected for all k ≥ 2 and m, n ≥ 1. This gives the following lemma. Lemma 4.1 Let G be a connected, kcolourable graph such that Sk (G) is connected, with k ≥ 2. Then V (G) ≥ k + 1, and G does not contain a complete bipartite graph as a spanning subgraph. Theorem 4.2 Let G be a connected, kcolourable graph such that Sk (G) is connected, with k ≥ 2. Suppose the graph G∗ is obtained from G by adding a new vertex v ∗ and joining it to j vertices in V (G), with 1 ≤ j ≤ k − 2. Then Sk (G∗ ) is connected.
We will show in the next section that the strong 3colour graph of the nvertex path, S3 (Pn ), is connected if and only if n ≥ 5. Now we add a new vertex and join it to the first and the last vertex of the path, forming to an (n + 1)vertex cycle. We will show in Section 4.4 that the strong 3colour graph of the nvertex cycle, S3 (Cn ), is not connected for all n. This example shows that the restriction j ≤ k − 2 of Theorem 4.2 is optimal.
66
Proof of Theorem 4.2. Let α∗ and β ∗ be strong kcolourings of G∗ . We show that there always exists a walk in Sk (G∗ ) from α∗ to β ∗ . We say that a colouring of G∗ is good if all k colours appear on V (G). First, we suppose that α∗ and β ∗ are good. By ignoring the vertex v ∗ , let α and β be the strong kcolourings of G obtained from α∗ and β ∗ , respectively. Since Sk (G) is connected, there is a path from α to β in Sk (G). We just follow the recolouring steps of that path to form a walk from α∗ to β ∗ in Sk (G∗ ). The only extra steps happen when we want to recolour a neighbour u of v ∗ to the same colour as v ∗ . Since dG∗ (v ∗ ) = j ≤ k − 2, we can always recolour v ∗ to a colour different from any of the colours appearing in its neighbourhood and its current colour. After recolouring v ∗ , we can recolour u, and continue the walk. This walk in Sk (G∗ ) finishes in a colouring in which the vertices in V (G) have the same colour as they have in β ∗ . If necessary, we can do one recolouring of v ∗ to its colour in β ∗ , completing the walk in Sk (G∗ ) from α∗ to β ∗ . If α∗ is not good, then below we show that we can always find a path in Sk (G∗ ) from α∗ to some good colouring (and if necessary, we do the same for β ∗ ). Together with the method described in the previous paragraph, this completes the proof. So we now assume that in α∗ every vertex of G has received one of k − 1 colours while v ∗ has the remaining colour. Let W be the set of vertices in V (G) that do not have a unique colour in G for the colouring α∗ . Since V (G) ≥ k + 1, W is not empty. Case 1: There is a vertex w ∈ W not adjacent to v ∗ . By the definition of W , there is a vertex w0 ∈ W such that w and w0 have the same colour in α∗ . Then we recolour w to the same colour as v ∗ . The resulting colouring is good. 67
Case 2: All vertices in W are adjacent to v ∗ . Additionally, define U = N (v ∗ )\W . and X = V (G)\N (v ∗ ). Note that all vertices in X have a unique colour in α∗ . Subcase 2.1: There is a vertex x ∈ X which is not adjacent to some vertex w ∈ W. Again, there is a vertex w0 ∈ W such that w and w0 have the same colour in α∗ . Then we first recolour w to the same colour as x, and then recolour x to the same colour as v ∗ . Again, this gives a good colouring.
Subcase 2.2: Every vertex in X is adjacent to every vertex in W . By Lemma 4.1, U is not empty (otherwise, the pair (X, W ) would form the parts of a spanning complete bipartite subgraph of G). Suppose there is some vertex u ∈ U which is not adjacent to some vertex w ∈ W and not adjacent to some vertex x ∈ X. Then we can recolour w to the colour of u (this is possible since there is another vertex w0 ∈ W with the same colour as w). Then recolour u to the same colour as x, and finally x to the same colour as v ∗ . It is easy to check that the remaining colouring is good. So we are left with the case that each vertex in U is adjacent to every vertex in W or to every vertex in X. Let UW be the set of vertices in U which are adjacent to every vertex in W , and UX = U \ UW . Then the pair (X ∪ UW , W ∪ UX ) forms the parts of a spanning complete bipartite subgraph of G. This case is impossible by Lemma 4.1. Theorem 4.3 Let G be a connected kcolourable graph so that Sk (G) is connected, with k ≥ 2. 68
Let v be a vertex of G with neighbourhood N (v). Suppose the graph G∗ is obtained from G by adding a new vertex v ∗ and joining v ∗ to the vertices in N ∗ for some N ∗ ⊆ N (v), N ∗ 6= ∅. Then Sk (G∗ ) is connected. Proof. Let α∗ and β ∗ be strong kcolourings of G∗ . We show that there always exists a walk in Sk (G∗ ) from α∗ to β ∗ . We say that a colouring of G∗ is good if v and v ∗ are labelled with the same colour. First suppose that α∗ and β ∗ are good. By ignoring the vertex v ∗ , let α and β be the strong kcolourings of G obtained from α∗ and β ∗ , respectively. Since Sk (G) is connected, there is a path from α to β in Sk (G). We just follow the recolouring steps of that path to form a walk from α∗ to β ∗ in Sk (G∗ ). The only extra step happens when we recolour v. In the next step we immediately recolour v ∗ to the same colour as v just received. It is easy to check that all these recolourings are allowed and give a walk in Sk (G∗ ) from α∗ to β ∗ , completing the proof. Assume that α∗ is not good. Below we show that we always can find a path in Sk (G∗ ) from α∗ to some good colouring (and if necessary, we do the same for β ∗ ). Together with the method described in the previous paragraph, this completes the proof. If there is a vertex u ∈ V (G) \ {v} with the same colour as v ∗ , then we just recolour v ∗ to the same colour as v. This gives a good colouring. So we now suppose that in α∗ every vertex of G has received one of k − 1 colours while v ∗ has the remaining colour. Remind that v and v ∗ received different colours in α∗ . Let W be the set of vertices in V (G) that did not receive a unique colour in G for the colouring α∗ . Since V (G) ≥ k + 1, W is not empty.
69
Case 1: There is a vertex w ∈ W not adjacent to v ∗ . By the definition of W , there is a vertex w0 ∈ W such that w and w0 have the same colour in α∗ . Hence we can recolour w to the same colour as v ∗ , and then recolour v ∗ to the same colour as v. The resulting colouring is good. Case 2: All vertices in W are adjacent to v ∗ . Additionally, define U = N (v ∗ )\W . and X = V (G)\N (v ∗ ). Note that all vertices in X have a unique colour in α∗ . Subcase 2.1: There is a vertex x ∈ X which is not adjacent to some vertex w ∈ W. Again, there is a vertex w0 ∈ W such that w and w0 have the same colour in α∗ . Then we first recolour w to the same colour as x. Then recolour x to the same colour as v ∗ , and finally recolour v ∗ to the same colour as v. Again, this gives a good colouring. Subcase 2.2: Every vertex in X is adjacent to every vertex in W . By Lemma 4.1, U is not empty (otherwise, the pair (X, W ) would form the parts of a spanning complete bipartite subgraph of G). Suppose there is some vertex u ∈ U that is not adjacent to some vertex w ∈ W and not adjacent to some vertex x ∈ X. Then we can recolour w to the colour of u (this is possible since there is another vertex w0 ∈ W with the same colour as w). Then recolour u to the same colour as x, x to the same colour as v ∗ , and finally recolour v ∗ to the same colour as v. It is easy to check that the remaining colouring is good. So we are left with the case that each vertex in U is adjacent to every vertex in W or to every vertex in X. Let UW be the set of vertices in U which are adjacent to 70
every vertex in W , and UX = U \ UW . Then the pair (X ∪ UW , W ∪ UX ) forms the parts of a spanning complete bipartite subgraph of G. This case is impossible by Lemma 4.1.
It is easy to see that in a normal colour graph Ck (G), there always is a path from any proper kvertexcolouring to some strong kvertexcolouring. This gives the following lemma. Lemma 4.4 If Sk (G) is connected, then Ck (G) is also connected.
4.3
The Strong kColour Graph of Paths
In this section, we prove that the strong kcolour graph of a path with n vertices, Sk (Pn ), is connected if and only if k ≥ 3, n ≥ 5, and n ≥ k + 1. First, suppose we colour a path Pn , n ≥ 2, with two colours. It is easy to see that there are only two strong 2vertexcolourings of Pn , and they are not adjacent in S2 (Pn ). Thus S2 (Pn ) is not connected for all n ≥ 2. For k = 3, we have already seen in Figures 4.1 and 4.2 that S3 (P4 ) is not connected, but S3 (P5 ) is connected. It is somewhat more work to show that S4 (P5 ) is connected. Proposition 4.5 The strong colour graph S4 (P5 ) is connected. Proof. In any strong 4colouring of P5 , there are only two vertices with the same colour. Let α be a strong 4colouring of P5 = v1 v2 . . . v5 . We call α an astandard colouring if α(v1 ) = α(v5 ) = a. 71
a b c d a s
s
s
v1
s
s
v5
Figure 4.3: An astandard colouring
We will prove the proposition by showing the following three steps. Step 1: There is a path from (a, b, c, d, a) to any other astandard colouring. We will first show that there is a path from (a, b, c, d, a) to (a, c, b, d, a) : a b c d a
a b c d b
r r r r r

c d c a b
a d c d b
r r r r r

c d b a b
r r r r r

r r r r r

r r r r r
r r r r r

a d b a c
r r r r r
a c b d c 

c d b a c
r r r r r
a d b d c
a d c a b
r r r r r

r r r r r

a c b d a 
r r r r r
By symmetry, there is a path from (a, b, c, d, a) to (a, b, d, c, a) as well. Now we consider astandard colourings as permutations of {b, c, d}. Note that all these permutations can be generated by the transpositions (b, c) and (c, d). Therefore, since we can find a path from (a, b, c, d, a) to (a, c, b, d, a), and from (a, b, c, d, a) to (a, b, d, c, a), there is a path from (a, b, c, d, a) to any other astandard colouring. Step 2: There is a path between any two types of standard colourings. First, here is a path from an astandard colouring α to an α(v3 )standard colouring : a b c d a r r r r r
c b c d a 
r r r r r
c b a d a 
r r r r r
c b a d c 
r r r r r
Next, a path from an astandard colouring α to an α(v2 )standard colouring :
72
a b c d a
d b c d a
r r r r r

d a c b d
d b c b a
r r r r r

b a c b d
r r r r r

r r r r r
d a c b a 
b a c a d
r r r r r

r r r r r
r r r r r

b d c a d 
r r r r r

b d c a b
r r r r r
By symmetry, there is also a path from an astandard colouring α to an α(v4 )standard colouring. Step 3: Each strong 4colouring has a path to some standard colouring. Let α be a strong 4colouring of P5 . Then α has one of the following forms : a b c d a r r r r r
a b c a d r r r r r
a b a c d r r r r r
b a c d a r r r r r
b a c a d r r r r r
b c a d a r r r r r
The first form already is an astandard colouring; for the second and the third ones we just recolour the vertex v1 to d; while for the fourth and the sixth ones we just recolour the vertex v5 to b. Finally, for the fifth form the following is a path to a bstandard colouring : b a c a d r r r r r
b d c a d 
r r r r r
b d c a b 
r r r r r
It is straightforward to see that appropriate renaming of the colours and sequence of the paths in Steps 1 – 3 will transform any strong 4colouring of P5 into any other strong 4colouring.
We extend the last result by showing that Sk (Pk+1 ) is connected, for all k ≥ 4. Proposition 4.6 For all k ≥ 4, Sk (Pk+1 ) is connected. 73
Proof. We prove by induction on k. We have already shown the proposition is true for k = 4. Let α and β be strong kcolourings of Pk+1 = v1 v2 . . . vk+1 , for some k ≥ 5. We can assume that in α, the vertex vk+1 has a unique colour. Otherwise, there is another vertex vi such that α(vi ) = α(vk+1 ). Then just recolour vi to a colour different from α(vk+1 ). Without loss of generality, we may assume that this unique colour on vk+1 in α is a. If the vertex vk+1 is the only vertex coloured a in β as well, then we can just remove vk+1 . Let α0 and β 0 be the strong kcolourings of Pk = v1 v2 . . . vk obtained from α and β, respectively. By the induction hypothesis, Sk−1 (Pk ) is connected. Then there is a path from α0 to β 0 in Sk−1 (Pk ). Using the same steps on Pk+1 gives a path from α to β in Sk (Pk+1 ). We now assume that in β, vk+1 is not coloured a, or it is not the only vertex coloured a. We distinguish 4 cases. Case 1: In β, vk+1 is coloured a, but there is a second vertex vi coloured a as well. Then we just recolour vi to another colour different from a. Thus vk+1 is now the only vertex coloured a. We are done by the paragraph above. Case 2: In β, vk+1 and some other vertex vi have the same colour b 6= a, while a third vertex vj is coloured a. Subcase 2.1: vk+1 and vj are not adjacent. Then we just recolour vk+1 to a, and we are back to Case 1.
74
Subcase 2.2: vk+1 and vj are adjacent, i.e., j = k. We call a colouring of Sk (Pk+1 ) good if we can recolour vi to a colour which is not in {β(vk−1 ), β(vk ) = a, β(vk+1 ) = b}. Note that β is good when k ≥ 6, or k = 5 and i 6= 2. If β is good, we can recolour vi to the colour β(vl ) for some l ∈ / {i − 1, i, i + 1, k − 1, k, k + 1}, to obtain the strong kcolouring γ. Let δ be the strong kcolouring of Pk+1 , obtained from γ by swapping the colours of vi and vk . By ignoring the vertex vk+1 , we can consider γ and δ as strong (k − 1)colourings of Pk . Since Sk−1 (Pk ) is connected, there is a path between these two colourings. We then apply this path to a path in Sk (Pk+1 ) from γ to δ. Next, we will form a path from δ to a colouring in which vertex vk+1 is the only vertex coloured a, and then we will have a path from β to this colouring. So we are done by Case 1. In δ, we first recolour vl to β(vk+1 ) = b and then recolour vk+1 to a. Finally, we recolour the vertex vi (which is previously coloured a) to another colour. We now suppose that β is not good, i.e., k = 5 and i = 2. Then here is a path from β to a colouring in which vk+1 is the only vertex coloured a. c b d e a b
r r r r r r
c a d e a b 
r r r r r r
c a d e d b 
c a b e d a r r r r r r
r r r r r r
c a b e d b 
r r r r r r

c e b e d a 
r r r r r r
Case 3: In β, vi and vj are coloured a for some i, j 6= k + 1. Without loss of generality, we may assume that vi is not adjacent to vk+1 . Then we recolour vi to β(vk+1 ), and we are back to Case 2.
75
Case 4: In β, vi and vj have the same colour b 6= a, a third vertex v` is coloured a, for some i, j, ` 6= k + 1. Without loss of generality, we may assume that vi is not adjacent to vk+1 . Then we recolour vi to β(vk+1 ), and we are back to Case 2.
By combining these propositions, we get the promised result on the strong colour graph of paths. Theorem 4.7 The strong colour graph Sk (Pn ) is connected if and only if k ≥ 3, n ≥ 5 and n ≥ k + 1.
Proof. We already have seen that S3 (P4 ) and S2 (Pn ), n ≥ 3, are not connected, while S3 (P5 ) and Sk (Pk+1 ), k ≥ 4, are connected. Applying Theorem 4.2 completes the proof.
4.4
The Strong kColour Graph of Cycles
In this section we want to show that the strong kcolour graph of a cycle with n vertices, Sk (Cn ), is connected if and only if k ≥ 4, n ≥ 6 and n ≥ k + 1. Before we prove the theorem, we give some propositions, which will be used in the proof. To orient a cycle means to orient each edge on the cycle so that a directed cycle → − is obtained. If C is a cycle, then by C we denote the cycle with one of the two possible orientations. Given a 3colouring α using colours {1, 2, 3}, the weight of
76
an edge e = uv oriented from u to v is
→ α) = w(− uv,
+1, if α(u)α(v) ∈ {12, 23, 31}; −1, if α(u)α(v) ∈ {21, 32, 13}.
→ − → − The weight W ( C , α) of an oriented cycle C is the sum of the weights of its oriented edges. Proposition 4.8 (Cereceda et al. [5]) → − Let α be a 3colouring of a graph G that contains a cycle C. If W ( C , α) 6= 0, then Ck (G) is not connected. Proposition 4.9 For all n ≥ 3, S3 (Cn ) is not connected.
Proof. By Lemmas 4.4 and 4.8, it is enough to find a strong 3colouring α with − → W (Cn , α) 6= 0. If n = 3 ` for some positive integer `, the pattern 1,2,3,1,2,3,...,1,2,3 − → provides a 3colouring α of Cn with W (Cn , α) = n 6= 0. For n = 4, it is easy to see that S3 (C4 ) is the graph with 12 isolated vertices. If n = 3 ` + 1 > 4, then − → we use the pattern 1,2,3,1,2,3,...,1,2,3,2, which gives W (Cn , α) = n − 4 6= 0. Finally, if n = 3 ` + 2 ≥ 5, we use the pattern 1,2,3,1,2,3,...,1,2,3,1,2, so we get − → W (Cn , α) = n − 2 6= 0. Proposition 4.10 The strong colour graph S4 (C5 ) is not connected.
Proof. For any strong 4colouring of the 5cycle C5 , there are only two vertices having the same colour. Thus each strong 4vertexcolouring of C5 can be recoloured only on these two vertices, and each of these two vertices can be recoloured to only
77
one new colour (since the two different colours of their neighbours are forbidden). This means each colouring has degree two in S4 (C5 ). Straightforward counting shows that S4 (C5 ) has 120 vertices. But each colouring in S4 (C5 ) is contained in a cycle of length 20. To see this, we start with some strong 4colouring of C5 and then recolour : a b a c d r r r r r
a b d c d 
a c d a b
r r r r r
b a c d a r r r r r
c d a b a r r r r r
r r r r r

r r r r r

r r r r r

r r r r r

r r r r r

c d c b a 
c b a b d
r r r r r

b a c d c 
b d c b a
r r r r r
r r r r r
d c b a c 
b a b d c
r r r r r
c d a b d 
r r r r r

b d c d a 
a c d c b 
d c b a b
r r r r r
d a b d c 
r r r r r

d c d a b 
d a b a c
r r r r r
a b d c b
r r r r r
r r r r r

c b a c d 
r r r r r

a b a c d r r r r r
By symmetry, we immediately get that S4 (C5 ) is a disjoint union of six copies of C20 , so it is not connected. Proposition 4.11 The strong colour graph S5 (C6 ) is connected.
Proof. In any strong 5colouring of the 6cycle C6 , there are only two vertices having the same colour. Let α be a strong 5colouring of C6 = v1 v2 . . . v5 v6 v1 . We call α an astandard colouring if α(v1 ) = α(v3 ) = a. a b a c d e s
s
s
v1
s
s
s
v6
Figure 4.4: An astandard colouring
We will prove the proposition by showing the following three steps. 78
Step 1: There is a path from (a, b, a, c, d, e) to any other astandard colourings. First, we will show that there is a path from (a, b, a, c, d, e) to (a, c, a, b, d, e) : a b a c d e
a b e c d e
r r r r r r

a b e c d c
r r r r r r
a c e b d c
r r r r r r

a c e b d e
r r r r r r

a b e b d c
r r r r r r

r r r r r r

a c a b d e
r r r r r r

By symmetry, there is also a path from (a, b, a, c, d, e) to (a, e, a, c, d, b). Next, we show that there is a path from (a, b, a, c, d, e) to (a, d, a, c, b, e) : a b a c d e
a b e c d e
r r r r r r

a d e c e b
a b e c d b
r r r r r r

a d b c e b
r r r r r r

b d b a e c


r r r r r r


r r r r r r

r r r r r r

a d e a b c
r r r r r r
a d e c b e 
r r r r r r
a d b a e c
r r r r r r
b d e a b c
r r r r r r
a d e c b c

a d b c e c
r r r r r r
b d e a e c
r r r r r r
a d e c d b
r r r r r r

r r r r r r

a d a c b e 
r r r r r r
Now we consider astandard colourings as permutations of {b, c, d, e}. Note that all these permutations can be generated by the transpositions (b, c), (b, d) and (b, e). Therefore, since we can find a path from (a, b, a, c, d, e) to (a, c, a, b, d, e), from (a, b, a, c, d, e) to (a, e, a, c, d, b), and from (a, b, a, c, d, e) to (a, d, a, c, b, e), there is a path from (e, a, e, b, c, d) to any other astandard colourings. Step 2: There is a path between any two types of standard colourings. First, here is a path from an astandard colouring α to an α(v5 )standard colouring : a b a c d e
r r r r r r
a b d c d e 
r r r r r r
a b d c a e 
79
r r r r r r
d b d c a e 
r r r r r r
Next, a path from an astandard colouring α to an α(v4 )standard colouring : a b a c d e
r r r r r r
c b a c d e 
c b a e d e
r r r r r r

r r r r r r
c b a e d a r r r r r r


c b c e d a r r r r r r
By symmetry, there is also a path from an astandard colouring α to an α(v6 )standard colouring. And finally, a path from an astandard colouring α to an α(v2 )standard colouring : a b a c d e
r r r r r r
d b a c d e 
d c a d b e
r r r r r r
d b a c b e
r r r r r r

b c a d b e 
r r r r r r
r r r r r r
d c a c b e 
b c a d a e 
r r r r r r
r r r r r r

b c b d a e 
r r r r r r
Step 3: Each colouring has a path to some standard colouring. Let α be a strong 5colouring of C6 . Then α has one of the following forms : a b a c d e
r r r r r r
a b c a d e
r r r r r r
b a c d e a r r r r r r
a b c d a e
r r r r r r
b c a d a e
b a c a d e
r r r r r r
b c a d e a
r r r r r r
r r r r r r
b a c d a e
r r r r r r
b c d a e a r r r r r r
The first form is already an astandard colouring. For the second and the third forms, we just recolour vertex v1 to c, and for the seventh and eight forms, we just recolour vertex v3 to b. For all the remaining colourings, we can find a path of length two to some standard colouring. We will leave checking that to the reader. It is straightforward to see that appropriate renaming of the colours and sequence of the paths in Steps 1 – 3 will transform any strong 5colouring of P6 into any other strong 5colouring.
80
Theorem 4.12 The strong colour graph Sk (Cn ) is connected if and only if k ≥ 4, n ≥ 6, and n ≥ k + 1.
Proof. We already have seen that S3 (Cn ), n ≥ 3 and S4 (C5 ) are disconnected. By Theorems 4.2 and 4.7 we can obtain that Sk (Cn ) is connected for all k ≥ 4, n ≥ 6, and n ≥ k + 2. Since S5 (C6 ) is connected, all that is left to prove is that Sk (Ck+1 ) is connected for all k ≥ 6. Let k ≥ 6 and let α and β be strong kcolourings of Ck+1 = v1 v2 . . . vk+1 v1 . In α, there will be a vertex, say v1 , which has an unique colour, say colour a. We say that a strong kcolouring of Ck+1 is good if v1 is the only vertex in Ck+1 , which is coloured a. Thus α is good. If β is good as well, then remove v1 , and let α0 and β 0 be the strong (k−1)colourings of Pk obtained from α and β, respectively. Since k ≥ 6, by Proposition 4.6 there is a path in Sk−1 (Pk ) from α0 to β 0 . Using the same steps gives a path from α to β in Ck+1 . So suppose that β is not good. As we colour the k + 1 vertices of Ck+1 with k colours, there are only two vertices having the same colour. We distinguish five cases. Case 1: In β, v1 is coloured a, but there is a second vertex vi coloured a as well. Then just recolour vi to another colour. The resulting colouring is good, and we are done by the paragraph above.
81
Case 2: In β, v1 and some other vertex vi have the same colour b 6= a, while a third vertex vj with j 6= 2, k + 1 is coloured a. Then we first recolour v1 to a, and then recolour vj to another colour. Again, this gives a good colouring, so we are done. Case 3: In β, v1 and some other vertex vi have the same colour b 6= a, while a third vertex vj with j ∈ {2, k + 1} is coloured a. Without loss of generality, we may assume that j = k + 1. Subcase 3.1: We have i ≥ 5. Now first recolour vertex vi to colour β(v3 ), then recolour v3 to β(vk+1 ) = a, vk+1 to β(v4 ), v4 to β(v1 ) = b, v1 to a, and finally recolour v3 to some colour different from a. It is easy to check that the remaining colouring is good. Subcase 3.2: We have i ∈ {3, 4}. Recall that j = k + 1 ≥ 7. Now first recolour vertex vi to colour β(v6 ), then recolour v6 to β(v1 ) = b. Now v1 and v6 have the same colour b, so we are back to Subcase 3.1. Case 4: In β, v1 has a unique colour b 6= a, while there are two vertices vi and vj coloured a. Subcase 4.1: We have {i, j} = {2, k + 1}. Now first recolour vertex v2 to β(v4 ), and then recolour v4 to β(v1 ) = b. Then we are back to Subcase 3.2. Subcase 4.2: We have {i, j} = 6 {2, k + 1}. Without loss of generality, we may assume that i 6= 2, k+1. Then we can recolour vi 82
to β(v1 ) = b. This means that v1 and vi have the same colour b 6= a, so we are back to Case 2 or 3. Case 5: In β, v1 has a unique colour b 6= a, there is a unique vertex vi coloured a, and two vertices vj and v` have the same colour c 6= a, b. Subcase 5.1: We have {j, `} = {2, k + 1}. Since k + 1 ≥ 7, we must have i 6= 3 or i 6= k. Without loss of generality, assume that i 6= 3. Then recolour v2 to β(vi ) = a. This brings us back to Case 4. Subcase 5.2: We have {j, `} = 6 {2, k + 1}. Without loss of generality, assume that j 6= 2, k + 1. Then we can recolour vj to β(v1 ) = b. This means that v1 and vj have the same colour b 6= a, and then we are back to Case 2 or 3.
4.5
The Strong 3Colour Graph of Trees
The aim of this section is to classify the trees T for which the strong 3colour graph S3 (T ) is connected. For this we need to consider some special trees. First, in Section 4.2 we saw that the strong kcolour graph of a complete bipartite graph is not connected, so S3 (K1,n ) is disconnected for all n ≥ 2. For n ≥ 1 and p, q ≥ 2, let I, Ψn and Φp,q be the graphs sketched in Figure 4.5, respectively.
83
x1
x2
x3
s
s
s
x4
x5
x6
s
s
v1 v2
s
s s ppp Z Z JJ Z Z Js s
vn
u1 u2
s
s s ppp Z Z JJ Z Z Js
v0
up s
s
@ @s s s
p p p @
s
w1 w2
wq
Figure 4.5: The graphs I, Ψn , and Φp,q
It is straightforward to check that in any strong 3colouring of Ψn we cannot recolour the vertex v0 to another colour so that the resulting 3colouring is strong again. Hence the strong colour graph S3 (Ψn ) is disconnected for all n ≥ 1. Proposition 4.13 The strong 3colour graph S3 (I) is connected.
Proof. Let α be a strong 3colouring of the graph I, with vertex set {x1 , x2 , . . . , x6 } as shown in Figure 4.5. We call α an (a, b)colouring if α(x2 ) = a and α(x5 ) = b. Easy counting shows that for fixed a and b, there are 15 (a, b)colourings (there are 2 choices for each of the other 4 vertices, but one of the resulting 16 3colourings is not strong). As there are 6 choices for a pair (a, b) from 3 colours, there are a total of 90 strong 3colourings of I. We will prove the proposition by combining the following two steps. Step 1: For given a and b, there is a path containing all (a, b)colourings.
b a b
b a c
r r r
c b a
b a c
r r r
r r r 
r r r
c b a
c a c
r r r

r r r
c a c
r r r

a b a
r r r
a b a
84
b a c
r r r

r r r
a b c
r r r

r r r
a b c

b a c
c a c
r r r r r r
c a c
r r r

c b c
r r r
c a b
r r r

c b c
r r r

c b a b a b
r r r
r r r
a b c

r r r
r r r
r r r

c b c
r r r

c b c
c a b
r r r

b a b
r r r
c b a c a b
r r r
c a b
r r r
r r r

a b c
r r r
a b a
Step 2: There is a path containing at least one strong 3colouring from each type of colourings.
c b a
c b a
r r r r r r
c b a
r r r

r r r
a b a
r r r

r r r
a c a
r r r

r r r
a c b
r r r

r r r
r r r

r r r
b c b
b a b
c a b
c a b
c a b
c a b
a c b
a c b
a c b
b c b
b a b
b a c
r r r r r r
r r r

c a c
r r r
c b c
r r r

r r r
r r r

a b c
a b c
b a c

r r r
a b c
r r r

r r r

a b c
b a c
r r r r r r
r r r
r r r

r r r

a b a
r r r
a c a
These two steps, together with appropriate renaming of the colours, will give all that is needed to transform any strong 3colouring of I into any other strong 3colouring. Theorem 4.14 Let T be a tree. Then S3 (T ) is connected if and only if T contains P5 or I as a subgraph.
85
Proof. Since S3 (P5 ) and S3 (I) are connected, one direction is immediately proved by using Theorem 4.2. For the other direction, suppose that T does not contain P5 , nor I. Since P5 is a path with 4 edges, the longest path in T can have length at most 3. Thus T has to be one of the following : K1 , P2 , K1,m , m ≥ 2, or Ψn , n ≥ 1. Note that T cannot be Φp,q for all p, q ≥ 2; otherwise, it would contain I as a subgraph. Since K1 and P2 have fewer than 3 vertices, T cannot be one of these two graphs. We already saw that S3 (K1,m ), m ≥ 2, and S3 (Ψn ), n ≥ 1, are disconnected. Therefore, we can conclude that S3 (T ) is not connected.
4.6
Discussion
We have already seen in Lemma 4.4 that if the strong colour graph Sk (G) is connected for some G and k, then so is the normal colour graph Ck (G). In general, the reverse direction is not true. For instance, for all m, n ≥ 2, for the complete bipartite graphs Km,n we have that for k ≥ 3, Ck (Km,n ) is connected, whereas Sk (Km,n ) is not connected. In fact, we have already seen that if G has a complete bipartite graph as a spanning subgraph, then Sk (G) is never connected. For k ≥ 3 it is not hard to construct other graphs apart from complete bipartite graphs that have this property, but all examples we know of have a fairly special structure (for instance, see the trees Ψn in Figure 4.5). This makes us raise the following question. Question 4.15 Is it possible to completely describe a class of graphs H so that if G does not contain a graph from H as a spanning subgraph, then Ck (G) is connected if and only if Sk (G) is connected ? 86
Bibliography [1] V. Auletta, A. Monti, M. Parente, and P. Persiano. A linear time algorithm for the feasibility of pebble motion on trees. Algorithmica, 23:223–245, 1999. [2] J. Billingham, R. A. Leese, and H. Rajaniemi. Frequency reassignment in cellular phone networks. Technical report, Smith Institute Study Group Report, 2005. Available from: www.smithinst.ac.uk/Projects/ESGI53/ESGI53Motorola/Report/. [3] P. Bonsma and L. Cereceda.
Finding paths between graph colourings:
PSPACEcompleteness and superpolynomial distances. Theoret. Comput. Sci., 410:5215–5226, 2009. [4] G. Brightwell, J. van den Heuvel, and S. Trakultraipruk. Connectivity properties of labelled token graphs. In Preparation. [5] L. Cereceda, J. van den Heuvel, and M. Johnson. Connectedness of the graph of vertexcolourings. Discrete Math., 308:913–919, 2008. [6] L. Cereceda, J. van den Heuvel, and M. Johnson. Mixing 3colourings in bipartite graphs. European J. Combin., 30:1593–1606, 2009. [7] L. Cereceda, J. van den Heuvel, and M. Johnson. Finding paths between 3colorings. J. Graph Theory, 67:69–82, 2011. [8] Y. M. Chee and A. Lim. The algorithmic complexity of colour switching. Inform. Process. Lett., 43:63–68, 1992. 87
[9] T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein. Introduction to algorithms. MIT Press, Cambridge, MA, third edition, 2009. [10] R. Diestel. Graph Theory. Springer, Berlin, 2010. [11] R. FabilaMonro, D. FloresPenaloza, C. Huemer, F. Hurtado, J. Urrutia, and D. R. Wood. Token graphs. Graphs Combin., 28:365–380, 2009. [12] G. Fertin, A. Raspaud, and O. S´ ykora. Nohole L(p, 0) labelling of cycles, grids and hypercubes. In Structural information and communication complexity, volume 3104 of Lecture Notes in Comput. Sci., pages 138–148. Springer, Berlin, 2004. [13] S. Fujita, T. Nakamigawa, and T. Sakuma. Colored pebble motion on graphs. European J. Combin., 33:884–892, 2012. [14] M. R. Garey and D. S. Johnson. Computers and intractability. A guide to the theory of NPcompleteness. A Series of Books in the Mathematical Sciences. W. H. Freeman and Co., San Francisco, Calif, 1979. [15] O. Goldreich. Finding the shortest movesequence in the graphgeneralized 15puzzle is nphard. In Studies in complexity and cryptography, volume 6650 of Lecture Notes in Comput. Sci., pages 1–5. Springer, Berlin, 2011. [16] G. Goraly and R. Hassin. Multicolor pebble motion on graphs. Algorithmica, 58:610–636, 2010. [17] J. Han. Frequency reassignment problem in mobile communication networks. Comput. Oper. Res., 34:2939–2948, 2007. [18] D. Kornhauser, G. Miller, and P. Spirakis. Coordinating pebble motion on graphs, the diameter of permutation groups, and applications. In SFCS ’84
88
Proceedings of the 25th Annual Symposium on Foundations of Computer Science, pages 241–250. IEEE Computer Society, Washington, DC, 1984. [19] C. Lu, L. Chen, and M. Zhai. Extremal problems on consecutive L(2, 1)labelling. Discrete Appl. Math., 155:1302–1313, 2007. [20] O. Marcotte and P. Hansen. The height and length of colour switching. In Graph colouring and applications, volume 23 of CRM Proc. Lecture Notes, pages 101–110. Amer. Math. Soc., Providence, RI, 1999. [21] C. H. Papadimitriou, P. Raghavan, M. Sudan, and H. Tamaki. Motion planning on a graph. In SFCS ’94 Proceedings of the 35th Annual Symposium on Foundations of Computer Science, pages 511–520. IEEE Computer Society, Washington, DC, 1994. [22] N. Robertson and P. D. Seymour. Graph minors. XIII. The disjoint paths problem. J. Combin. Theory Ser. B, 63:65–110, 1995. [23] N. Robertson and P. D. Seymour. Graph minors. XX. Wagner’s conjecture. J. Combin. Theory Ser. B, 92:325–357, 2004. [24] A. Schrijver. Combinatorial Optimization, volume A. Springer, Berlin, 2003. [25] S. Trakultraipruk.
Connectedness of strong kcolour graphs.
2010.
arXiv:1009.4440 [math.CO]. [26] J. van den Heuvel and S. Trakultraipruk. On the complexity of finding shortest paths in token graphs. In Preparation. [27] D. B. West. Introduction to Graph Theory. Prentice Hall, New Jersey, second edition, 2001. [28] R. M. Wilson. Graph puzzles, homotopy, and the alternating group. J. Combin. Theory Ser. B, 16:86–96, 1974. 89
[29] Z. Wu and S. Grumbach. Feasibility of motion planning on directed graphs. In Theory and applications of models of computation, volume 5532 of Lecture Notes in Comput. Sci., pages 430–439. Springer, Berlin, 2009.
90
Appendix A
Appendix According to Theorem 2.2 we have that the graph θ0 (which is shown in Figure A.1) is the only 2connected nonbipartite graph for which not all its labelled token graphs are connected. Additionally, it is claimed that its labelled token graph is disconnected when the multiset of tokens is one of the following: (2,2,2), (2,2,1,1), (2,1,1,1,1), or (1,1,1,1,1,1). To justify this claim we give more detail about how the labelled token graphs of θ0 look like. vr6 vr5
J
r r Jr v1 J v v4 Jr 0 r
v2
v3
Figure A.1: The graph θ0
A token configuration of θ0 , using the vertex names in Figure A.1, is said to be standard if the vertex v1 is unoccupied. Performing an operation U (respectively, L) on a standard token configuration is taking 5 moves of the tokens on the upper (respectively, lower) 5cycle anticlockwise to get another standard token configuration (see Figure A.2 for examples). 1r
1r
J
r r Jr 2 J 2
Jr r
3
3
1r
2r
1r
U r
r JJr 2 J 1
r
Jr 3 3
1r
J
r r Jr 2 J 2
Jr r
3
3
Figure A.2: Operations U and L
91
1r
1r
L r
r JJr 3 J 2
r
Jr 2 3
We can see that every token configuration has a path to some standard token configuration in the labelled token graph. Thus to see the structure of the labelled token graphs of θ0 , we need to consider standard token configurations only. Here we classify all the standard token configurations of θ0 into some groups such that standard token configurations are in the same group if and only if they are in the same component of the labelled token graph. Sometimes we put a dashed box around a standard token configuration in two figures from the same group to denote that these two standard token configurations are in fact the same.
92
The Structure of T (θ0; (2, 2, 2)) The following are the two groups of standard token configurations in the labelled token graph T (θ0 ; (2, 2, 2)).
1 1
1 1
2 2
L,L
2 2 3
3
L
2 2
U,L,U,L,L
3 3 2
2
L
3 3
3 3 1
1 1 3
L
3 3
U,L,U,L,L
L,L
1
3
L
L,L
1 1 2
2
L
2 1 2 1 L
1 1
1 1
2 2
2 2
3 3
3 3
3 3 2 2
2 2 3 3
1 1 3 3
3 3 1 1
2 2 1 1
1 1 2 2
U
U
U
U
U
U
1 3
1 2
2 1
2 3
3 2
3 1
1 3 2 2
1 2 3 3
2 1 3 3
2 3 1 1
3 2 1 1
3 1 2 2
L
L
L
L
L
L
1 3
1 2
2 1
2 3
3 2
3 1
3 2 1 2
2 3 1 3
1 3 2 3
3 1 2 1
2 1 3 1
1 2 3 2
U
U
U
U
U
U
3 2
2 3
1 3
3 1
2 1
1 2
1 3 1 2
1 2 1 3
2 1 2 3
2 3 2 1
3 2 3 1
3 1 3 2
U,L
U,L
U,L
U,L
U,L
U,L
2 3
3 2
3 1
1 3
1 2
2 1
1 2 3 1
1 3 2 1
2 3 1 2
2 1 3 2
3 1 2 3
3 2 1 3
L
L
L
L
L
L
2 3
3 2
3 1
1 3
1 2
2 1
2 1 1 3
3 1 1 2
3 2 2 1
1 2 2 3
1 3 3 2
2 3 3 1
U
U
U
U
U
U
3 1
2 1
1 2
3 2
2 3
1 3
2 2 1 3
3 3 1 2
3 3 2 1
1 1 2 3
1 1 3 2
2 2 3 1
U
U
U
U
U
U
1 2
1 3
2 3
2 1
3 1
3 2
3 2 1 3
2 3 1 2
1 3 2 1
3 1 2 3
2 1 3 2
1 2 3 1
L
L
L
L
L
L
1 2
1 3
2 3
2 1
3 1
3 2
2 3 3 1
3 2 2 1
3 1 1 2
1 3 3 2
1 2 2 3
2 1 1 3
Figure A.3: Group 1 in T (θ0 ; (2, 2, 2))
93
1 1
1 1 L
2 3 3 2 U
2 2 U,L,L,U
3 2 2 3 U
2 2
1 3 3 1
3 1 1 3
U
3 3 U,L,U,U
L
U
3 3 L
1 2 2 1 U
2 1 1 2 U
1 3
1 2
2 3
2 1
3 2
3 1
1 2 3 2
1 3 2 3
2 1 3 1
2 3 1 3
3 1 2 1
3 2 1 2
L
L
L
L
L
L
1 3
1 2
2 3
2 1
3 2
3 1
2 2 1 3
3 3 1 2
1 1 2 3
3 3 2 1
1 1 3 2
2 2 3 1
L
L
L
L
L
L
1 3
1 2
2 3
2 1
3 2
3 1
2 3 2 1
3 2 3 1
1 3 1 2
3 1 3 2
1 2 1 3
2 1 2 3
L
L
L
L
L
L
1 3
1 2
2 3
2 1
3 2
3 1
3 1 2 2
2 1 3 3
3 2 1 1
1 2 3 3
2 3 1 1
1 3 2 2
Figure A.4: Group 2 in T (θ0 ; (2, 2, 2))
94
The Structure of T (θ0; (2, 2, 1, 1)) The following are the two groups of standard token configurations in the labelled token graph T (θ0 ; (2, 2, 1, 1)).
1 3
1 1
1 1
U
1 2 4
2
2 2
L,L
2 2 4
3
L
2 2
U,L,U,L,L
4 3 2
2
L
4 3
3 4 1 L
4 3
U,L,U,L,L
L,L
1
1 1 3
4
L
L,L
1 1 2
2
L
2 1 2 1 L
1 1
1 1
2 2
2 2
4 3
4 3
3 4 2 2
2 2 4 3
1 1 3 4
4 3 1 1
2 2 1 1
1 1 2 2
U
U
U
U
U
U
1 4
1 2
2 1
2 3
3 2
3 1
1 3 2 2
1 2 4 3
2 1 3 4
2 4 1 1
4 2 1 1
4 1 2 2
L
L
L
L
L
L
1 4
1 2
2 1
2 3
3 2
3 1
3 2 1 2
2 3 1 4
1 4 2 3
4 1 2 1
2 1 4 1
1 2 4 2
U
U
U
U
U
U
4 2
2 3
1 4
3 1
2 1
1 2
1 3 1 2
1 2 1 4
2 1 2 3
2 4 2 1
3 2 4 1
3 1 4 2
U,L
U,L
U,L
U,L
U,L
U,L
2 3
3 2
4 1
1 4
1 2
2 1
1 2 4 1
1 4 2 1
2 3 1 2
2 1 3 2
3 1 2 4
3 2 1 4
L
L
L
L
L
L
2 3
3 2
4 1
1 4
1 2
2 1
2 1 1 4
4 1 1 2
3 2 2 1
1 2 2 3
1 4 3 2
2 4 3 1
U
U
U
U
U
U
3 1
2 1
1 2
4 2
2 4
1 4
2 2 1 4
3 4 1 2
4 3 2 1
1 1 2 3
1 1 3 2
2 2 3 1
U
U
U
U
U
U
1 2
1 4
2 3
2 1
4 1
4 2
3 2 1 4
2 3 1 2
1 4 2 1
4 1 2 3
2 1 3 2
1 2 3 1
L
L
L
L
L
L
1 2
1 4
2 3
2 1
4 1
4 2
2 4 3 1
3 2 2 1
4 1 1 2
1 3 4 2
1 2 2 3
2 1 1 3
Figure A.5: Part 1 of Group A1 in T (θ0 ; (2, 2, 1, 1))
95
1 1
1 1
2 2
L,L
2 2 3
4
L
2 2
U,L,U,L,L
3 4 2
2
L
3 4
4 3 1
1 1 4
L
3 4
U,L,U,L,L
L,L
1
3
L
L,L
1 1 2
2
2 1 2 1
L
L
1 1
1 1
2 2
2 2
3 4
3 4
4 3 2 2
2 2 3 4
1 1 4 3
3 4 1 1
2 2 1 1
1 1 2 2
U
U
U
U
U
U
1 3
1 2
2 1
2 4
4 2
4 1
1 4 2 2
1 2 3 4
2 1 4 3
2 3 1 1
3 2 1 1
3 1 2 2
L
L
L
L
L
L
1 3
1 2
2 1
2 4
4 2
4 1
4 2 1 2
2 4 1 3
1 3 2 4
3 1 2 1
2 1 3 1
1 2 3 2
U
U
U
U
U
U
3 2
2 4
1 3
4 1
2 1
1 2
1 4 1 2
1 2 1 3
2 1 2 4
2 3 2 1
4 2 3 1
4 1 3 2
U,L
U,L
U,L
U,L
U,L
U,L
2 4
4 2
3 1
1 3
1 2
2 1
1 2 3 1
1 3 2 1
2 4 1 2
2 1 4 2
4 1 2 3
4 2 1 3
L
L
L
L
L
L
2 4
4 2
3 1
1 3
1 2
2 1
2 1 1 3
3 1 1 2
4 2 2 1
1 2 2 4
1 3 4 2
2 3 4 1
U
U
U
U
U
U
4 1
2 1
1 2
3 2
2 3
1 3
2 2 1 3
4 3 1 2
3 4 2 1
1 1 2 4
1 1 4 2
2 2 4 1
U
U
U
U
U
U
1 2
1 3
2 4
2 1
3 1
3 2
4 2 1 3
2 4 1 2
1 3 2 1
3 1 2 4
2 1 4 2
1 2 4 1
L
L
L
L
L
L
1 2
1 3
2 4
2 1
3 1
3 2
2 3 4 1
4 2 2 1
3 1 1 2
1 4 3 2
1 2 2 4
2 1 1 4
Figure A.6: Part 2 of Group A1 in T (θ0 ; (2, 2, 1, 1))
96
1 1 2 4 2
1 1 3
L
3 2 4
U
2 2 2
U,L,L,U
1 3 1
U
2 2 4
L
4 1 3
U
3 4 1
U,L,U,U
1 2 1
U
3 4 2
L
U
2 1 1 2 U
1 3
1 2
2 4
2 1
4 2
4 1
1 2 4 2
1 3 2 4
2 1 3 1
2 4 1 3
3 1 2 1
3 2 1 2
L
L
L
L
L
L
1 3
1 2
2 4
2 1
4 2
4 1
2 2 1 4
3 4 1 2
1 1 2 3
4 3 2 1
1 1 3 2
2 2 3 1
L
L
L
L
L
L
1 3
1 2
2 4
2 1
4 2
4 1
2 4 2 1
4 2 3 1
1 3 1 2
3 1 4 2
1 2 1 3
2 1 2 3
L
L
L
L
L
L
1 3
1 2
2 4
2 1
4 2
4 1
4 1 2 2
2 1 4 3
3 2 1 1
1 2 3 4
2 3 1 1
1 3 2 2
3 2
2 1
2 3
1 2
1 4
U
3 1 1 2 2
4
2 1 1
L
4
1 4 3
L
2
4 1 1
L
2
2 3 4
L
1
3 1 2 2
L
L
3 1
3 2
2 1
2 3
1 2
1 4
2 1 2 4
1 2 1 4
4 1 3 2
1 4 1 2
3 2 4 1
2 3 2 1
L
L
L
L
L
L
3 1
3 2
2 1
2 3
1 2
1 4
2 2 4 1
1 1 4 2
3 4 2 1
1 1 2 4
4 3 1 2
2 2 1 3
L
L
L
L
L
L
3 1
3 2
2 1
2 3
1 2
1 4
4 2 1 2
4 1 2 1
2 3 1 4
2 1 4 1
1 4 2 3
1 2 3 2
U
U
4 3 2
1 2
U
4 3 1
L
1
2 1
U
2 2 2
U,L,U,U
3
U
2 2 1
L
1 4
1
4 1
U
1 1 3
U,L,L,U
4
1 1 2
L
2 3
Figure A.7: Group A2 in T (θ0 ; (2, 2, 1, 1))
97
2 4 3 2
The Structure of T (θ0; (2, 1, 1, 1, 1)) The following are the three groups of standard token configurations in the labelled token graph T (θ0 ; (2, 1, 1, 1, 1)).
1 3
1 1
1 1
U
1 5 4
2
5 2
L,L
2 5 4
3
L
5 2
U,L,U,L,L
4 3 2
5
L
4 3
3 4 1 L
4 3
U,L,U,L,L
L,L
1
1 1 3
4
L
L,L
1 1 2
5
L
2 1 5 1 L
1 1
1 1
5 2
5 2
4 3
4 3
3 4 2 5
5 2 4 3
1 1 3 4
4 3 1 1
5 2 1 1
1 1 2 5
U
U
U
U
U
U
1 4
1 2
2 1
2 3
3 2
3 1
1 3 2 5
1 5 4 3
5 1 3 4
5 4 1 1
4 5 1 1
4 1 2 5
L
L
L
L
L
L
1 4
1 2
2 1
2 3
3 2
3 1
3 5 1 2
5 3 1 4
1 4 5 3
4 1 5 1
5 1 4 1
1 5 4 2
U
U
U
U
U
U
4 2
2 3
1 4
3 1
2 1
1 5
1 3 1 2
1 5 1 4
2 1 5 3
2 4 5 1
3 5 4 1
3 1 4 2
U,L
U,L
U,L
U,L
U,L
U,L
5 3
3 5
4 1
1 4
1 5
5 1
1 2 4 1
1 4 2 1
2 3 1 5
2 1 3 5
3 1 2 4
3 2 1 4
L
L
L
L
L
L
5 3
3 5
4 1
1 4
1 5
5 1
2 1 1 4
4 1 1 2
3 5 2 1
1 5 2 3
1 4 3 2
2 4 3 1
U
U
U
U
U
U
3 1
5 1
1 5
4 5
5 4
1 4
5 2 1 4
3 4 1 2
4 3 2 1
1 1 2 3
1 1 3 2
5 2 3 1
U
U
U
U
U
U
1 2
1 4
5 3
5 1
4 1
4 2
3 5 1 4
5 3 1 2
1 4 2 1
4 1 2 3
5 1 3 2
1 5 3 1
L
L
L
L
L
L
1 2
1 4
5 3
5 1
4 1
4 2
5 4 3 1
3 2 5 1
4 1 1 2
1 3 4 2
1 2 5 3
5 1 1 3
Figure A.8: Part 1 of Group B1 in T (θ0 ; (2, 1, 1, 1, 1))
98
1 1 5 2 3
1 1 4
L
L,L
3 4 5
2 5 2
L
U,L,U,L,L
4 3 1
2 5 1
L,L
L
1 1 4
3 4 3
L
U,L,U,L,L
1 1 5
3 4 2
L,L
5 1 2 1
L
L
1 1
1 1
2 5
2 5
3 4
3 4
4 3 5 2
2 5 3 4
1 1 4 3
3 4 1 1
2 5 1 1
1 1 5 2
U
U
U
U
U
U
1 3
1 5
5 1
5 4
4 5
4 1
1 4 5 2
1 2 3 4
2 1 4 3
2 3 1 1
3 2 1 1
3 1 5 2
L
L
L
L
L
L
1 3
1 5
5 1
5 4
4 5
4 1
4 2 1 5
2 4 1 3
1 3 2 4
3 1 2 1
2 1 3 1
1 2 3 5
U
U
U
U
U
U
3 5
5 4
1 3
4 1
5 1
1 2
1 4 1 5
1 2 1 3
5 1 2 4
5 3 2 1
4 2 3 1
4 1 3 5
U,L
U,L
U,L
U,L
U,L
U,L
2 4
4 2
3 1
1 3
1 2
2 1
1 5 3 1
1 3 5 1
5 4 1 2
5 1 4 2
4 1 5 3
4 5 1 3
L
L
L
L
L
L
2 4
4 2
3 1
1 3
1 2
2 1
5 1 1 3
3 1 1 5
4 2 5 1
1 2 5 4
1 3 4 5
5 3 4 1
4 1
2 1
1 2
3 2
2 3
1 3
2 5 1 3
4 3 1 5
3 4 5 1
1 1 5 4
1 1 4 5
2 5 4 1
U
U
U
U
U
U
U
U
U
U
U
U
1 5
1 3
2 4
2 1
3 1
3 5
4 2 1 3
2 4 1 5
1 3 5 1
3 1 5 4
2 1 4 5
1 2 4 1
L
L
L
L
L
L
1 5
1 3
2 4
2 1
3 1
3 5
2 3 4 1
4 5 2 1
3 1 1 5
1 4 3 5
1 5 2 4
2 1 1 4
Figure A.9: Part 2 of Group B1 in T (θ0 ; (2, 1, 1, 1, 1))
99
1 3
1 1
1 1
U
1 2 4
5
2 5
L,L
5 2 4
3
L
2 5
U,L,U,L,L
4 3 5
2
L
4 3
3 4 1 L
4 3
U,L,U,L,L
L,L
1
1 1 3
4
L
L,L
1 1 5
2
L
5 1 2 1 L
1 1
1 1
2 5
2 5
4 3
4 3
3 4 5 2
2 5 4 3
1 1 3 4
4 3 1 1
2 5 1 1
1 1 5 2
U
U
U
U
U
U
1 4
1 5
5 1
5 3
3 5
3 1
1 3 5 2
1 2 4 3
2 1 3 4
2 4 1 1
4 2 1 1
4 1 5 2
L
L
L
L
L
L
1 4
1 5
5 1
5 3
3 5
3 1
3 2 1 5
2 3 1 4
1 4 2 3
4 1 2 1
2 1 4 1
1 2 4 5
U
U
U
U
U
U
4 5
5 3
1 4
3 1
5 1
1 2
1 3 1 5
1 2 1 4
5 1 2 3
5 4 2 1
3 2 4 1
3 1 4 5
U,L
U,L
U,L
U,L
U,L
U,L
2 3
3 2
4 1
1 4
1 2
2 1
1 5 4 1
1 4 5 1
5 3 1 2
5 1 3 2
3 1 5 4
3 5 1 4
L
L
L
L
L
L
2 3
3 2
4 1
1 4
1 2
2 1
5 1 1 4
4 1 1 5
3 2 5 1
1 2 5 3
1 4 3 5
5 4 3 1
U
U
U
U
U
U
3 1
2 1
1 2
4 2
2 4
1 4
2 5 1 4
3 4 1 5
4 3 5 1
1 1 5 3
1 1 3 5
2 5 3 1
U
U
U
U
U
U
1 5
1 4
2 3
2 1
4 1
4 5
3 2 1 4
2 3 1 5
1 4 5 1
4 1 5 3
2 1 3 5
1 2 3 1
L
L
L
L
L
L
1 5
1 4
2 3
2 1
4 1
4 5
2 4 3 1
3 5 2 1
4 1 1 5
1 3 4 5
1 5 2 3
2 1 1 3
Figure A.10: Part 1 of Group B2 in T (θ0 ; (2, 1, 1, 1, 1))
100
1 1 2 5 3
1 1 4
L
L,L
3 4 2
5 2 5
L
U,L,U,L,L
4 3 1
5 2 1
L,L
L
1 1 4
3 4 3
L
U,L,U,L,L
1 1 2
3 4 5
L
L,L
2 1 5 1 L
1 1
1 1
5 2
5 2
3 4
3 4
4 3 2 5
5 2 3 4
1 1 4 3
3 4 1 1
5 2 1 1
1 1 2 5
U
U
U
U
U
U
1 3
1 2
2 1
2 4
4 2
4 1
1 4 2 5
1 5 3 4
5 1 4 3
5 3 1 1
3 5 1 1
3 1 2 5
L
L
L
L
L
L
1 3
1 2
2 1
2 4
4 2
4 1
4 5 1 2
5 4 1 3
1 3 5 4
3 1 5 1
5 1 3 1
1 5 3 2
U
U
U
U
U
U
3 2
2 4
1 3
4 1
2 1
1 5
1 4 1 2
1 5 1 3
2 1 5 4
2 3 5 1
4 5 3 1
4 1 3 2
U,L
U,L
U,L
U,L
U,L
U,L
5 4
4 5
3 1
1 3
1 5
5 1
1 2 3 1
1 3 2 1
2 4 1 5
2 1 4 5
4 1 2 3
4 2 1 3
L
L
L
L
L
L
5 4
4 5
3 1
1 3
1 5
5 1
2 1 1 3
3 1 1 2
4 5 2 1
1 5 2 4
1 3 4 2
2 3 4 1
4 1
5 1
1 5
3 5
5 3
1 3
5 2 1 3
4 3 1 2
3 4 2 1
1 1 2 4
1 1 4 2
5 2 4 1
U
U
U
U
U
U
U
U
U
U
U
U
1 2
1 3
5 4
5 1
3 1
3 2
4 5 1 3
5 4 1 2
1 3 2 1
3 1 2 4
5 1 4 2
1 5 4 1
L
L
L
L
L
L
1 2
1 3
5 4
5 1
3 1
3 2
5 3 4 1
4 2 5 1
3 1 1 2
1 4 3 2
1 2 5 4
5 1 1 4
Figure A.11: Part 2 of Group B2 in T (θ0 ; (2, 1, 1, 1, 1))
101
1 1
1 1
5 2
L
2 4 5
3
5 2
U,L,L,U
3 2 4
U
5
3 4
1 3 1
U
3 4
U,L,U,U
L
4
4 1 3
U
1
3 4
L
1 5 1
U
2
L
2 1 5
U
1
U
1 3
1 5
2 4
2 1
4 2
4 1
1 2 4 5
1 3 2 4
5 1 3 1
5 4 1 3
3 1 5 1
3 2 1 5
L
L
L
L
L
L
1 3
1 5
2 4
2 1
4 2
4 1
2 5 1 4
3 4 1 2
1 1 5 3
4 3 5 1
1 1 3 5
2 5 3 1
L
L
L
L
L
L
1 3
1 5
2 4
2 1
4 2
4 1
5 4 2 1
4 2 3 1
1 3 1 5
3 1 4 5
1 5 1 3
5 1 2 3
L
L
L
L
L
L
1 3
1 5
2 4
2 1
4 2
4 1
4 1 5 2
2 1 4 3
3 5 1 1
1 5 3 4
5 3 1 1
1 3 5 2
3 2
2 1
2 3
1 5
1 4
U
3 1 1 5 2
4
5 1 1
L
4
1 4 3
L
5
4 1 1
L
5
2 3 4
L
1
3 1 5 2
L
L
3 1
3 2
2 1
2 3
1 5
1 4
5 1 2 4
1 5 1 4
4 1 3 5
1 4 1 5
3 2 4 1
5 3 2 1
L
L
L
L
L
L
3 1
3 2
2 1
2 3
1 5
1 4
2 5 4 1
1 1 4 5
3 4 5 1
1 1 5 4
4 3 1 2
2 5 1 3
L
L
L
L
L
L
3 1
3 2
2 1
2 3
1 5
1 4
4 2 1 5
4 1 5 1
5 3 1 4
5 1 4 1
1 4 2 3
1 2 3 5
U
U
4 3
U
4 3 L
2 1 5
1
U
5 2 U,L,U,U
1 5 1
2
U
5 2 L
3 1 4
1
U
1 1
1 1
U,L,L,U
1 4 1
3
L
4 2 3
5
2 4 3 5
Figure A.12: Part 1 of Group B3 in T (θ0 ; (2, 1, 1, 1, 1))
102
1 5 2 1
1 1 5 4 2
1 1 3
L
3 5 4
U
2 5 2
U,L,L,U
1 3 1
U
2 5 4
L
4 1 3
U
3 4 1
U,L,U,U
1 2 1
U
3 4 5
L
U
5 1 1 2 U
1 3
1 2
5 4
5 1
4 5
4 1
1 5 4 2
1 3 5 4
2 1 3 1
2 4 1 3
3 1 2 1
3 5 1 2
L
L
L
L
L
L
1 3
1 2
5 4
5 1
4 5
4 1
5 2 1 4
3 4 1 5
1 1 2 3
4 3 2 1
1 1 3 2
5 2 3 1
L
L
L
L
L
L
1 3
1 2
5 4
5 1
4 5
4 1
2 4 5 1
4 5 3 1
1 3 1 2
3 1 4 2
1 2 1 3
2 1 5 3
L
L
L
L
L
L
1 3
1 2
5 4
5 1
4 5
4 1
4 1 2 5
5 1 4 3
3 2 1 1
1 2 3 4
2 3 1 1
1 3 2 5
3 5
5 1
5 3
1 2
1 4
U
3 1 1 2 5
4
2 1 1
L
4
1 4 3
L
2
4 1 1
L
2
5 3 4
L
1
3 1 2 5
L
L
3 1
3 5
5 1
5 3
1 2
1 4
2 1 5 4
1 2 1 4
4 1 3 2
1 4 1 2
3 5 4 1
2 3 5 1
L
L
L
L
L
L
3 1
3 5
5 1
5 3
1 2
1 4
5 2 4 1
1 1 4 2
3 4 2 1
1 1 2 4
4 3 1 5
5 2 1 3
L
L
L
L
L
L
3 1
3 5
5 1
5 3
1 2
1 4
4 5 1 2
4 1 2 1
2 3 1 4
2 1 4 1
1 4 5 3
1 5 3 2
U
U
4 3 5
1 2
U
4 3 1
L
1
2 1
U
2 5 5
U,L,U,U
3
U
2 5 1
L
1 4
1
4 1
U
1 1 3
U,L,L,U
4
5 3
1 1 2
L
5 4 3 2
Figure A.13: Part 2 of Group B3 in T (θ0 ; (2, 1, 1, 1, 1))
103
The Structure of T (θ0; (1, 1, 1, 1, 1, 1)) The following are the six groups of standard token configurations in the labelled token graph T (θ0 ; (1, 1, 1, 1, 1, 1)).
1 3
6 1
6 1
U
6 5 4
2
5 2
L,L
2 5 4
3
L
5 2
U,L,U,L,L
4 3 2
5
L
4 3
3 4 1 L
4 3
U,L,U,L,L
L,L
6
1 6 3
4
L
L,L
6 1 2
5
L
2 1 5 6 L
6 1
6 1
5 2
5 2
4 3
4 3
3 4 2 5
5 2 4 3
6 1 3 4
4 3 1 6
5 2 6 1
1 6 2 5
U
U
U
U
U
U
1 4
1 2
2 1
2 3
3 2
3 6
6 3 2 5
6 5 4 3
5 6 3 4
5 4 1 6
4 5 6 1
4 1 2 5
L
L
L
L
L
L
1 4
1 2
2 1
2 3
3 2
3 6
3 5 6 2
5 3 6 4
6 4 5 3
4 6 5 1
5 1 4 6
1 5 4 2
U
U
U
U
U
U
4 2
2 3
1 4
3 6
2 1
6 5
1 3 6 2
1 5 6 4
2 6 5 3
2 4 5 1
3 5 4 6
3 1 4 2
U,L
U,L
U,L
U,L
U,L
U,L
5 3
3 5
4 6
6 4
1 5
5 1
1 2 4 6
1 4 2 6
2 3 1 5
2 1 3 5
3 6 2 4
3 2 6 4
L
L
L
L
L
L
5 3
3 5
4 6
6 4
1 5
5 1
2 6 1 4
4 6 1 2
3 5 2 1
1 5 2 3
6 4 3 2
2 4 3 6
U
U
U
U
U
U
3 6
5 6
6 5
4 5
5 4
1 4
5 2 1 4
3 4 1 2
4 3 2 1
6 1 2 3
1 6 3 2
5 2 3 6
U
U
U
U
U
U
6 2
6 4
5 3
5 1
4 6
4 2
3 5 1 4
5 3 1 2
6 4 2 1
4 6 2 3
5 1 3 2
1 5 3 6
L
L
L
L
L
L
6 2
6 4
5 3
5 1
4 6
4 2
5 4 3 1
3 2 5 1
4 1 6 2
6 3 4 2
1 2 5 3
5 6 1 3
Figure A.14: Part 1 of Group C1 in T (θ0 ; (1, 1, 1, 1, 1, 1))
104
1 6 5 2 3
1 6 4
L
L,L
3 4 5
2 5 2
L
U,L,U,L,L
4 3 6
2 5 1
L,L
L
6 1 4
3 4 3
L
U,L,U,L,L
1 6 5
3 4 2
L
L,L
5 6 2 1 L
1 6
1 6
2 5
2 5
3 4
3 4
4 3 5 2
2 5 3 4
1 6 4 3
3 4 6 1
2 5 1 6
6 1 5 2
U
U
U
U
U
U
6 3
6 5
5 6
5 4
4 5
4 1
1 4 5 2
1 2 3 4
2 1 4 3
2 3 6 1
3 2 1 6
3 6 5 2
L
L
L
L
L
L
6 3
6 5
5 6
5 4
4 5
4 1
4 2 1 5
2 4 1 3
1 3 2 4
3 1 2 6
2 6 3 1
6 2 3 5
U
U
U
U
U
U
3 5
5 4
6 3
4 1
5 6
1 2
6 4 1 5
6 2 1 3
5 1 2 4
5 3 2 6
4 2 3 1
4 6 3 5
U,L
U,L
U,L
U,L
U,L
U,L
2 4
4 2
3 1
1 3
6 2
2 6
6 5 3 1
6 3 5 1
5 4 6 2
5 6 4 2
4 1 5 3
4 5 1 3
L
L
L
L
L
L
2 4
4 2
3 1
1 3
6 2
2 6
5 1 6 3
3 1 6 5
4 2 5 6
6 2 5 4
1 3 4 5
5 3 4 1
4 1
2 1
1 2
3 2
2 3
6 3
2 5 6 3
4 3 6 5
3 4 5 6
1 6 5 4
6 1 4 5
2 5 4 1
U
U
U
U
U
U
U
U
U
U
U
U
1 5
1 3
2 4
2 6
3 1
3 5
4 2 6 3
2 4 6 5
1 3 5 6
3 1 5 4
2 6 4 5
6 2 4 1
L
L
L
L
L
L
1 5
1 3
2 4
2 6
3 1
3 5
2 3 4 6
4 5 2 6
3 6 1 5
1 4 3 5
6 5 2 4
2 1 6 4
Figure A.15: Part 2 of Group C1 in T (θ0 ; (1, 1, 1, 1, 1, 1))
105
6 3
1 6
1 6
U
1 5 4
2
5 2
L,L
2 5 4
3
L
5 2
U,L,U,L,L
4 3 2
5
L
4 3
3 4 6 L
4 3
U,L,U,L,L
L,L
1
6 1 3
4
L
L,L
1 6 2
5
L
2 6 5 1 L
1 6
1 6
5 2
5 2
4 3
4 3
3 4 2 5
5 2 4 3
1 6 3 4
4 3 6 1
5 2 1 6
6 1 2 5
U
U
U
U
U
U
6 4
6 2
2 6
2 3
3 2
3 1
1 3 2 5
1 5 4 3
5 1 3 4
5 4 6 1
4 5 1 6
4 6 2 5
L
L
L
L
L
L
6 4
6 2
2 6
2 3
3 2
3 1
3 5 1 2
5 3 1 4
1 4 5 3
4 1 5 6
5 6 4 1
6 5 4 2
U
U
U
U
U
U
4 2
2 3
6 4
3 1
2 6
1 5
6 3 1 2
6 5 1 4
2 1 5 3
2 4 5 6
3 5 4 1
3 6 4 2
U,L
U,L
U,L
U,L
U,L
U,L
5 3
3 5
4 1
1 4
6 5
5 6
6 2 4 1
6 4 2 1
2 3 6 5
2 6 3 5
3 1 2 4
3 2 1 4
L
L
L
L
L
L
5 3
3 5
4 1
1 4
6 5
5 6
2 1 6 4
4 1 6 2
3 5 2 6
6 5 2 3
1 4 3 2
2 4 3 1
U
U
U
U
U
U
3 1
5 1
1 5
4 5
5 4
6 4
5 2 6 4
3 4 6 2
4 3 2 6
1 6 2 3
6 1 3 2
5 2 3 1
U
U
U
U
U
U
1 2
1 4
5 3
5 6
4 1
4 2
3 5 6 4
5 3 6 2
1 4 2 6
4 1 2 3
5 6 3 2
6 5 3 1
L
L
L
L
L
L
1 2
1 4
5 3
5 6
4 1
4 2
5 4 3 6
3 2 5 6
4 6 1 2
1 3 4 2
6 2 5 3
5 1 6 3
Figure A.16: Part 1 of Group C2 in T (θ0 ; (1, 1, 1, 1, 1, 1))
106
6 1 5 2 3
6 1 4
L
L,L
3 4 5
2 5 2
L
U,L,U,L,L
4 3 1
2 5 6
L,L
L
1 6 4
3 4 3
L
U,L,U,L,L
6 1 5
3 4 2
L
L,L
5 1 2 6 L
6 1
6 1
2 5
2 5
3 4
3 4
4 3 5 2
2 5 3 4
6 1 4 3
3 4 1 6
2 5 6 1
1 6 5 2
U
U
U
U
U
U
1 3
1 5
5 1
5 4
4 5
4 6
6 4 5 2
6 2 3 4
2 6 4 3
2 3 1 6
3 2 6 1
3 1 5 2
L
L
L
L
L
L
1 3
1 5
5 1
5 4
4 5
4 6
4 2 6 5
2 4 6 3
6 3 2 4
3 6 2 1
2 1 3 6
1 2 3 5
U
U
U
U
U
U
3 5
5 4
1 3
4 6
5 1
6 2
1 4 6 5
1 2 6 3
5 6 2 4
5 3 2 1
4 2 3 6
4 1 3 5
U,L
U,L
U,L
U,L
U,L
U,L
2 4
4 2
3 6
6 3
1 2
2 1
1 5 3 6
1 3 5 6
5 4 1 2
5 1 4 2
4 6 5 3
4 5 6 3
L
L
L
L
L
L
2 4
4 2
3 6
6 3
1 2
2 1
5 6 1 3
3 6 1 5
4 2 5 1
1 2 5 4
6 3 4 5
5 3 4 6
4 6
2 6
6 2
3 2
2 3
1 3
2 5 1 3
4 3 1 5
3 4 5 1
6 1 5 4
1 6 4 5
2 5 4 6
U
U
U
U
U
U
U
U
U
U
U
U
6 5
6 3
2 4
2 1
3 6
3 5
4 2 1 3
2 4 1 5
6 3 5 1
3 6 5 4
2 1 4 5
1 2 4 6
L
L
L
L
L
L
6 5
6 3
2 4
2 1
3 6
3 5
2 3 4 1
4 5 2 1
3 1 6 5
6 4 3 5
1 5 2 4
2 6 1 4
Figure A.17: Part 2 of Group C2 in T (θ0 ; (1, 1, 1, 1, 1, 1))
107
6 3
1 6
1 6
U
1 2 4
5
2 5
L,L
5 2 4
3
L
2 5
U,L,U,L,L
4 3 5
2
L
4 3
3 4 6 L
4 3
U,L,U,L,L
L,L
1
6 1 3
4
L
L,L
1 6 5
2
L
5 6 2 1 L
1 6
1 6
2 5
2 5
4 3
4 3
3 4 5 2
2 5 4 3
1 6 3 4
4 3 6 1
2 5 1 6
6 1 5 2
U
U
U
U
U
U
6 4
6 5
5 6
5 3
3 5
3 1
1 3 5 2
1 2 4 3
2 1 3 4
2 4 6 1
4 2 1 6
4 6 5 2
L
L
L
L
L
L
6 4
6 5
5 6
5 3
3 5
3 1
3 2 1 5
2 3 1 4
1 4 2 3
4 1 2 6
2 6 4 1
6 2 4 5
U
U
U
U
U
U
4 5
5 3
6 4
3 1
5 6
1 2
6 3 1 5
6 2 1 4
5 1 2 3
5 4 2 6
3 2 4 1
3 6 4 5
U,L
U,L
U,L
U,L
U,L
U,L
2 3
3 2
4 1
1 4
6 2
2 6
6 5 4 1
6 4 5 1
5 3 6 2
5 6 3 2
3 1 5 4
3 5 1 4
L
L
L
L
L
L
2 3
3 2
4 1
1 4
6 2
2 6
5 1 6 4
4 1 6 5
3 2 5 6
6 2 5 3
1 4 3 5
5 4 3 1
U
U
U
U
U
U
3 1
2 1
1 2
4 2
2 4
6 4
2 5 6 4
3 4 6 5
4 3 5 6
1 6 5 3
6 1 3 5
2 5 3 1
U
U
U
U
U
U
1 5
1 4
2 3
2 6
4 1
4 5
3 2 6 4
2 3 6 5
1 4 5 6
4 1 5 3
2 6 3 5
6 2 3 1
L
L
L
L
L
L
1 5
1 4
2 3
2 6
4 1
4 5
2 4 3 6
3 5 2 6
4 6 1 5
1 3 4 5
6 5 2 3
2 1 6 3
Figure A.18: Part 1 of Group C3 in T (θ0 ; (1, 1, 1, 1, 1, 1))
108
6 1 2 5 3
6 1 4
L
L,L
3 4 2
5 2 5
L
U,L,U,L,L
4 3 1
5 2 6
L,L
L
1 6 4
3 4 3
L
U,L,U,L,L
6 1 2
3 4 5
L
L,L
2 1 5 6 L
6 1
6 1
5 2
5 2
3 4
3 4
4 3 2 5
5 2 3 4
6 1 4 3
3 4 1 6
5 2 6 1
1 6 2 5
U
U
U
U
U
U
1 3
1 2
2 1
2 4
4 2
4 6
6 4 2 5
6 5 3 4
5 6 4 3
5 3 1 6
3 5 6 1
3 1 2 5
L
L
L
L
L
L
1 3
1 2
2 1
2 4
4 2
4 6
4 5 6 2
5 4 6 3
6 3 5 4
3 6 5 1
5 1 3 6
1 5 3 2
U
U
U
U
U
U
3 2
2 4
1 3
4 6
2 1
6 5
1 4 6 2
1 5 6 3
2 6 5 4
2 3 5 1
4 5 3 6
4 1 3 2
U,L
U,L
U,L
U,L
U,L
U,L
5 4
4 5
3 6
6 3
1 5
5 1
1 2 3 6
1 3 2 6
2 4 1 5
2 1 4 5
4 6 2 3
4 2 6 3
L
L
L
L
L
L
5 4
4 5
3 6
6 3
1 5
5 1
2 6 1 3
3 6 1 2
4 5 2 1
1 5 2 4
6 3 4 2
2 3 4 6
4 6
5 6
6 5
3 5
5 3
1 3
5 2 1 3
4 3 1 2
3 4 2 1
6 1 2 4
1 6 4 2
5 2 4 6
U
U
U
U
U
U
U
U
U
U
U
U
6 2
6 3
5 4
5 1
3 6
3 2
4 5 1 3
5 4 1 2
6 3 2 1
3 6 2 4
5 1 4 2
1 5 4 6
L
L
L
L
L
L
6 2
6 3
5 4
5 1
3 6
3 2
5 3 4 1
4 2 5 1
3 1 6 2
6 4 3 2
1 2 5 4
5 6 1 4
Figure A.19: Part 2 of Group C3 in T (θ0 ; (1, 1, 1, 1, 1, 1))
109
1 3
6 1
6 1
U
6 2 4
5
2 5
L,L
5 2 4
3
L
2 5
U,L,U,L,L
4 3 5
2
L
4 3
3 4 1 L
4 3
U,L,U,L,L
L,L
6
1 6 3
4
L
L,L
6 1 5
2
L
5 1 2 6 L
6 1
6 1
2 5
2 5
4 3
4 3
3 4 5 2
2 5 4 3
6 1 3 4
4 3 1 6
2 5 6 1
1 6 5 2
U
U
U
U
U
U
1 4
1 5
5 1
5 3
3 5
3 6
6 3 5 2
6 2 4 3
2 6 3 4
2 4 1 6
4 2 6 1
4 1 5 2
L
L
L
L
L
L
1 4
1 5
5 1
5 3
3 5
3 6
3 2 6 5
2 3 6 4
6 4 2 3
4 6 2 1
2 1 4 6
1 2 4 5
U
U
U
U
U
U
4 5
5 3
1 4
3 6
5 1
6 2
1 3 6 5
1 2 6 4
5 6 2 3
5 4 2 1
3 2 4 6
3 1 4 5
U,L
U,L
U,L
U,L
U,L
U,L
2 3
3 2
4 6
6 4
1 2
2 1
1 5 4 6
1 4 5 6
5 3 1 2
5 1 3 2
3 6 5 4
3 5 6 4
L
L
L
L
L
L
2 3
3 2
4 6
6 4
1 2
2 1
5 6 1 4
4 6 1 5
3 2 5 1
1 2 5 3
6 4 3 5
5 4 3 6
U
U
U
U
U
U
3 6
2 6
6 2
4 2
2 4
1 4
2 5 1 4
3 4 1 5
4 3 5 1
6 1 5 3
1 6 3 5
2 5 3 6
U
U
U
U
U
U
6 5
6 4
2 3
2 1
4 6
4 5
3 2 1 4
2 3 1 5
6 4 5 1
4 6 5 3
2 1 3 5
1 2 3 6
L
L
L
L
L
L
6 5
6 4
2 3
2 1
4 6
4 5
2 4 3 1
3 5 2 1
4 1 6 5
6 3 4 5
1 5 2 3
2 6 1 3
Figure A.20: Part 1 of Group C4 in T (θ0 ; (1, 1, 1, 1, 1, 1))
110
1 6 2 5 3
1 6 4
L
L,L
3 4 2
5 2 5
L
U,L,U,L,L
4 3 6
5 2 1
L,L
L
6 1 4
3 4 3
L
U,L,U,L,L
1 6 2
3 4 5
L
L,L
2 6 5 1 L
1 6
1 6
5 2
5 2
3 4
3 4
4 3 2 5
5 2 3 4
1 6 4 3
3 4 6 1
5 2 1 6
6 1 2 5
U
U
U
U
U
U
6 3
6 2
2 6
2 4
4 2
4 1
1 4 2 5
1 5 3 4
5 1 4 3
5 3 6 1
3 5 1 6
3 6 2 5
L
L
L
L
L
L
6 3
6 2
2 6
2 4
4 2
4 1
4 5 1 2
5 4 1 3
1 3 5 4
3 1 5 6
5 6 3 1
6 5 3 2
U
U
U
U
U
U
3 2
2 4
6 3
4 1
2 6
1 5
6 4 1 2
6 5 1 3
2 1 5 4
2 3 5 6
4 5 3 1
4 6 3 2
U,L
U,L
U,L
U,L
U,L
U,L
5 4
4 5
3 1
1 3
6 5
5 6
6 2 3 1
6 3 2 1
2 4 6 5
2 6 4 5
4 1 2 3
4 2 1 3
L
L
L
L
L
L
5 4
4 5
3 1
1 3
6 5
5 6
2 1 6 3
3 1 6 2
4 5 2 6
6 5 2 4
1 3 4 2
2 3 4 1
4 1
5 1
1 5
3 5
5 3
6 3
5 2 6 3
4 3 6 2
3 4 2 6
1 6 2 4
6 1 4 2
5 2 4 1
U
U
U
U
U
U
U
U
U
U
U
U
1 2
1 3
5 4
5 6
3 1
3 2
4 5 6 3
5 4 6 2
1 3 2 6
3 1 2 4
5 6 4 2
6 5 4 1
L
L
L
L
L
L
1 2
1 3
5 4
5 6
3 1
3 2
5 3 4 6
4 2 5 6
3 6 1 2
1 4 3 2
6 2 5 4
5 1 6 4
Figure A.21: Part 2 of Group C4 in T (θ0 ; (1, 1, 1, 1, 1, 1))
111
6 1
6 1
5 2
L
2 4 5
3
5 2
U,L,L,U
3 2 4
U
5
3 4
1 3 6
U
3 4
U,L,U,U
L
4
4 1 3
U
6
3 4
L
6 5 1
U
2
L
2 6 5
U
1
U
1 3
1 5
2 4
2 6
4 2
4 1
6 2 4 5
6 3 2 4
5 1 3 6
5 4 1 3
3 6 5 1
3 2 6 5
L
L
L
L
L
L
1 3
1 5
2 4
2 6
4 2
4 1
2 5 6 4
3 4 6 2
1 6 5 3
4 3 5 1
6 1 3 5
2 5 3 6
L
L
L
L
L
L
1 3
1 5
2 4
2 6
4 2
4 1
5 4 2 6
4 2 3 6
6 3 1 5
3 1 4 5
1 5 6 3
5 6 2 3
L
L
L
L
L
L
1 3
1 5
2 4
2 6
4 2
4 1
4 6 5 2
2 6 4 3
3 5 6 1
1 5 3 4
5 3 1 6
6 3 5 2
3 2
2 1
2 3
6 5
6 4
U
3 6 1 5 2
4
5 6 1
L
4
6 4 3
L
5
4 1 6
L
5
2 3 4
L
1
3 1 5 2
L
L
3 6
3 2
2 1
2 3
6 5
6 4
5 1 2 4
6 5 1 4
4 6 3 5
1 4 6 5
3 2 4 1
5 3 2 1
L
L
L
L
L
L
3 6
3 2
2 1
2 3
6 5
6 4
2 5 4 1
1 6 4 5
3 4 5 6
6 1 5 4
4 3 1 2
2 5 1 3
L
L
L
L
L
L
3 6
3 2
2 1
2 3
6 5
6 4
4 2 1 5
4 1 5 6
5 3 6 4
5 6 4 1
1 4 2 3
1 2 3 5
U
U
4 3
U
4 3 L
2 1 5
6
U
5 2 U,L,U,U
1 5 6
2
U
5 2 L
3 6 4
1
U
1 6
1 6
U,L,L,U
6 4 1
3
L
4 2 3
5
2 4 3 5
Figure A.22: Part 1 of Group C5 in T (θ0 ; (1, 1, 1, 1, 1, 1))
112
1 5 2 6
1 6
1 6
2 5
L
5 4 2
3
2 5
U,L,L,U
3 5 4
U
2
3 4
6 3 1
U
3 4
U,L,U,U
L
4
4 6 3
U
1
L
1 2 6
U
5
5 6 1 2
U
U
6 3
6 2
5 4
5 1
4 5
4 6
1 5 4 2
1 3 5 4
2 6 3 1
2 4 6 3
3 1 2 6
3 5 1 2
L
L
L
L
L
L
6 3
6 2
5 4
5 1
4 5
4 6
5 2 1 4
3 4 1 5
6 1 2 3
4 3 2 6
1 6 3 2
5 2 3 1
L
L
L
L
L
L
6 3
6 2
5 4
5 1
4 5
4 6
2 4 5 1
4 5 3 1
1 3 6 2
3 6 4 2
6 2 1 3
2 1 5 3
L
L
L
L
L
L
6 3
6 2
5 4
5 1
4 5
4 6
4 1 2 5
5 1 4 3
3 2 1 6
6 2 3 4
2 3 6 1
1 3 2 5
3 5
5 6
5 3
1 2
1 4
U
3 1 6 2 5
4
2 1 6
L
4
1 4 3
L
2
4 6 1
L
2
5 3 4
L
6
3 6 2 5
L
L
3 1
3 5
5 6
5 3
1 2
1 4
2 6 5 4
1 2 6 4
4 1 3 2
6 4 1 2
3 5 4 6
2 3 5 6
L
L
L
L
L
L
3 1
3 5
5 6
5 3
1 2
1 4
5 2 4 6
6 1 4 2
3 4 2 1
1 6 2 4
4 3 6 5
5 2 6 3
L
L
L
L
L
L
3 1
3 5
5 6
5 3
1 2
1 4
4 5 6 2
4 6 2 1
2 3 1 4
2 1 4 6
6 4 5 3
6 5 3 2
U
U
4 3
U
4 3 L
5 6 2
1
U
2 5 U,L,U,U
6 2 1
5
U
2 5 L
3
6
6 1
U,L,L,U
1
1 4
U
6 1
4 6
3
L
4 5 3
2
5 4 3 2
Figure A.23: Part 2 of Group C5 in T (θ0 ; (1, 1, 1, 1, 1, 1))
113
1 6
1 6
5 2
L
2 4 5
3
5 2
U,L,L,U
3 2 4
U
5
3 4
6 3 1
U
3 4
U,L,U,U
L
4
4 6 3
U
1
3 4
L
1 5 6
U
2
L
2 1 5
U
6
U
6 3
6 5
2 4
2 1
4 2
4 6
1 2 4 5
1 3 2 4
5 6 3 1
5 4 6 3
3 1 5 6
3 2 1 5
L
L
L
L
L
L
6 3
6 5
2 4
2 1
4 2
4 6
2 5 1 4
3 4 1 2
6 1 5 3
4 3 5 6
1 6 3 5
2 5 3 1
L
L
L
L
L
L
6 3
6 5
2 4
2 1
4 2
4 6
5 4 2 1
4 2 3 1
1 3 6 5
3 6 4 5
6 5 1 3
5 1 2 3
L
L
L
L
L
L
6 3
6 5
2 4
2 1
4 2
4 6
4 1 5 2
2 1 4 3
3 5 1 6
6 5 3 4
5 3 6 1
1 3 5 2
3 2
2 6
2 3
1 5
1 4
U
3 1 6 5 2
4
5 1 6
L
4
1 4 3
L
5
4 6 1
L
5
2 3 4
L
6
3 6 5 2
L
L
3 1
3 2
2 6
2 3
1 5
1 4
5 6 2 4
1 5 6 4
4 1 3 5
6 4 1 5
3 2 4 6
5 3 2 6
L
L
L
L
L
L
3 1
3 2
2 6
2 3
1 5
1 4
2 5 4 6
6 1 4 5
3 4 5 1
1 6 5 4
4 3 6 2
2 5 6 3
L
L
L
L
L
L
3 1
3 2
2 6
2 3
1 5
1 4
4 2 6 5
4 6 5 1
5 3 1 4
5 1 4 6
6 4 2 3
6 2 3 5
U
U
4 3
U
4 3 L
2 6 5
1
U
5 2 U,L,U,U
6 5 1
2
U
5 2 L
3 1 4
6
U
6 1
6 1
U,L,L,U
1 4 6
3
L
4 2 3
5
2 4 3 5
Figure A.24: Part 1 of Group C6 in T (θ0 ; (1, 1, 1, 1, 1, 1))
114
6 5 2 1
6 1
6 1
2 5
L
5 4 2
3
2 5
U,L,L,U
3 5 4
U
2
3 4
1 3 6
U
3 4
U,L,U,U
L
4
4 1 3
U
6
L
6 2 1
U
5
5 1 6 2
U
U
1 3
1 2
5 4
5 6
4 5
4 1
6 5 4 2
6 3 5 4
2 1 3 6
2 4 1 3
3 6 2 1
3 5 6 2
L
L
L
L
L
L
1 3
1 2
5 4
5 6
4 5
4 1
5 2 6 4
3 4 6 5
1 6 2 3
4 3 2 1
6 1 3 2
5 2 3 6
L
L
L
L
L
L
1 3
1 2
5 4
5 6
4 5
4 1
2 4 5 6
4 5 3 6
6 3 1 2
3 1 4 2
1 2 6 3
2 6 5 3
L
L
L
L
L
L
1 3
1 2
5 4
5 6
4 5
4 1
4 6 2 5
5 6 4 3
3 2 6 1
1 2 3 4
2 3 1 6
6 3 2 5
3 5
5 1
5 3
6 2
6 4
U
3 6 1 2 5
4
2 6 1
L
4
6 4 3
L
2
4 1 6
L
2
5 3 4
L
1
3 1 2 5
L
L
3 6
3 5
5 1
5 3
6 2
6 4
2 1 5 4
6 2 1 4
4 6 3 2
1 4 6 2
3 5 4 1
2 3 5 1
L
L
L
L
L
L
3 6
3 5
5 1
5 3
6 2
6 4
5 2 4 1
1 6 4 2
3 4 2 6
6 1 2 4
4 3 1 5
5 2 1 3
L
L
L
L
L
L
3 6
3 5
5 1
5 3
6 2
6 4
4 5 1 2
4 1 2 6
2 3 6 4
2 6 4 1
1 4 5 3
1 5 3 2
U
U
4 3
U
4 3 L
5 1 2
6
U
2 5 U,L,U,U
1 2 6
5
U
2 5 L
3
1
1 6
U,L,L,U
6
6 4
U
1 6
4 1
3
L
4 5 3
2
5 4 3 2
Figure A.25: Part 2 of Group C6 in T (θ0 ; (1, 1, 1, 1, 1, 1))
115