Citation
On interval representations and symmetries of graphs

Material Information

Title:
On interval representations and symmetries of graphs
Creator:
Flesch, Breeann Marie
Publication Date:
Language:
English
Physical Description:
xiv, 102 leaves : ; 28 cm.

Subjects

Subjects / Keywords:
Graph theory ( lcsh )
Interval analysis (Mathematics) ( lcsh )
Symmetry (Mathematics) ( lcsh )
Graph theory ( fast )
Interval analysis (Mathematics) ( fast )
Symmetry (Mathematics) ( fast )
Genre:
bibliography ( marcgt )
theses ( marcgt )
non-fiction ( marcgt )

Notes

Review:
This thesis focuses on two main topics: interval representations and symmetries of graphs. A graph is interval if to every vertex v E V (G), we can assign an interval of the real line, Iv, such that xy E E(G) if and only if Ixnly-=/:- 0. We call the set of intervals of the real line the interval representation of the graph. Interval graphs were characterized by the absence of induced cycles larger than 3 and asteroidal triples by Lekkerkerker and Boland [36) in 1962. Subsequently variations on the interval theme have been introduced, including probe interval graphs and the interval p-graph, which is a generalization of the interval bigraph. A natural extension of interval graphs, called interval bigraphs, were introduced by Harary, Kabell, and McMorris [28) in 1982. A bipartite graph G = (X, Y) is an interval bigraph if to every vertex, v E V(G), we can assign an interval of the real line, Iv, such that xy E E( G) if and only if Ix n fy -=/:- 0 and x E X and y E Y. Initially it was thought that the natural extension of asteroidal triples of vertices to asteroidal triples of edges along with induced cycles larger than 4 would be a forbidden subgraph characterization [28). However that was not to be, and there is no forbidden subgraph characterization of interval bigraphs to date. The only forbidden subgraph characterization in the literature is for cycle-free interval bigraphs in [13). In 2002 Brown, Flink, and Lundgren introduced a further extension of interval bigraphs called interval k-graphs [11). We change the name to interval p-graphs here to avoid confusion. Let G = {X1 ,X2 , ... ,XP} be a multipartite graph. A graph G is an interval p-graph if there exists an assignment to each vertex , v E V (G) , an interval of the real line , Iv, such that xy E E (G) if and only if Ix n ly =I= 0 and X E Xi, y E xj and i =I= j . The forbidden subgraph characterization for interval 2-graphs (interval bigraphs) has proven difficult , hence a forbidden subgraph characterization for interval p-graphs , for p > 2, will also be difficult, whence we restrict attention to a natural generalization of the cycle-free case: the case of k-trees. The class of k-trees is the set of all graphs that can be obtained by the following construction: (i) the k-complete graph , Kk , is a k-tree; (ii) to a k-tree Q' with n- 1 vertices (n > k) add a new vertex adjacent to a k-complete subgraph of Q'. In chapter 2, two characterizations of k-tree interval p-graphs are given , one of which is a forbidden subgraph characterization. Moving to a different variation on the interval property, we next investigate probe interval 2-trees. A graph G is a probe interval graph (PIG) if there is a partition of V (G) into sets P and N and a collection {I v I v E V (G)} of intervals of the real line such that , for u , v E V( G) , uv E E( G) if and only if Iu n I v =/= 0 and at least one of u, v belongs to P. Probe interval graphs were invented to help with modeling in the human genome project. Przulj and Corneil found in [41] that 2-tree probe interval graphs have a large set of forbidden subgraphs , at least 62. We give a characterization of 2-tree PIGs and add to the list of forbidden subgraphs. The second concentration of this thesis, symmetries of graphs, began in 1996 with a paper by Albertson and Collins [2]. A coloring of the vertices of a graph G, f : V (G) ~ { 1, ... , r} is said to be r-distinguishing if no nontrivial automorphism of the graph preserves all of the vertex colors. The distinguishing number - of a graph G is defined by D( G) = min { r I G has a coloring that is r-distinguishing }. Albertson and Collins determined the distinguishing number for graphs that realize the dihedral group. We let Dn denote the dihedral group of order 2n , which is the group of symmetries of a regular n-gon. Albertson and Collins [2] proved that if G realizes Dn then D( G) = 2 unless n = {3 , 4, 5, 6, 10} in which case D( G) is either 2 or 3. Since Albertson and Collins introduced this topic , there has been much investigation into distinguishing colorings. Areas of these investigations include the distinguishing number of Cartesian products ( [1], [6], [33], [35]), determining a bound on the distinguishing number ([17], [34]) , and the distinguishing number of trees and forests ( [15]). In our investigations we generalize distinguishing colorings to list - distinguishing colorings. Given a family L of lists assigning available colors to the vertices of G, we say that G is Ł-distinguishable is thereis a distinguishing coloring for G such that f(v) E L(v) for all v. The list-disnguishing number of G, written DE(G), is the smallest positive integer k such that G is Ł-distinguishable for any assignment L of lists with jL(v)j + k for all v. Since all of the lists can be identical , we see that D( G) < De( G). Here we determine the list-distinguishing number for several families of graphs and highlight a number of distinctions between the problems of distinguishing and list-distinguishing a graph. We first give a Brooks-type result for list-distinguishing colorings. By determining precisely when the distinguishing number is 3 in small cases , we show that the list-distinguishing number is equal to the distinguishing number for all graphs that realize the dihedral group. Lastly, we give the list-distinguishing number for some Cartesian product graphs.
Thesis:
Thesis (Ph. D.)--University of Colorado Denver, 2011.
Bibliography:
Includes bibliographical references (leaves 98-102).
Statement of Responsibility:
by Breeann Marie Flesch.

Record Information

Source Institution:
University of Colorado Denver
Holding Location:
Auraria Library
Rights Management:
All applicable rights reserved by the source institution and holding location.
Resource Identifier:
761014160 ( OCLC )
ocn761014160

Downloads

This item is only available as the following downloads:


Full Text

PAGE 1

ON INTERVAL REPRESENTATIONS AND SYMMETRIES OF GRAPHS by Breeann Marie Flesch M.S., University of Colorado Denv e r 2010 A thesis submitted to the University of Colorado D e nver in partial fulfillment of the requirements for the degree of Doctor of Philosophy Applied Mathematics 2011

PAGE 2

This thesis for the Doctor of Philosophy degree by Breeann Marie Flesch has been approved by iRiChard :Lundgren David Brown 1 1Date

PAGE 3

Flesch, Breeann Marie (Ph.D., Applied Mathematics) On Interval Representations and Symmetries of Graphs Thesis directed by Professor J. Richard Lundgren ABSTRACT This thesis focuses on two main topics: interval representations and symme tries of graphs. A graph is interval if to every vertex v E V (G) we can assign an interval of the real line, Iv, such that xy E E(G) if and only if Ixnly-=/:-0. We call the set of intervals of the real line the interval representation of the graph. Interval graphs were characterized by the absence of induced cycles larger than 3 and asteroidal triples by Lekkerkerker and Boland [36) in 1962. Subsequently variations on the interval theme have been introduced, including probe interval graphs and the interval p-graph, which is a generalization of the interval bigraph. A natural extension of interval graphs, called interval bigraphs, were in troduced by Harary, Kabell, and McMorris [28) in 1982. A bipartite graph G = (X, Y) is an interval bigraph if to every vertex, v E V(G), we can assign an interval of the real line, Iv, such that xy E E( G) if and only if Ix n fy -=/:-0 and x E X and y E Y. Initially it was thought that the natural extension of asteroidal t,riples of vertices to asteroidal triples of edges along with induced cycles larger than 4 would be a forbidden subgraph characterization [28). However that was not to be, and there is no forbidden subgraph characterization of

PAGE 4

interval bigraphs to date. The only forbidden subgraph charact e rization in the literatur e is for cycle-fre e interval bigraphs in [13). In 2002 Brown, Flink, and Lundgren introduced a further e xtension of in terval bigraphs called interval k-graphs [11). We change the name to interval p-graphs here to avoid confusion. Let G = {X1,X2 ... ,XP} b e a multipartite graph. A graph G is an interval p-graph if there exists an assignment to each vertex v E V (G) an interval of the real line Iv, such that xy E E (G) if and only if Ix n ly =I= 0 and X E Xi, y E xj and i =I= j The forbidden subgraph characterization for interval 2-graphs (interval bi graphs) has proven difficult hence a forbidden subgraph char a cterization for interval p-graphs for p > 2, will also be difficult, whence we restrict attention to a natural generalization of the cycl e -free case: the cas e of k-trees. The class of k-trees is the set of all graphs that c an be obtained b y the following construc tion: (i) the k-complete graph, Kk, is a k-tree; (ii) to a k-tree Q' with n-1 vertices (n > k) add a new vertex adjacent to a k-complete subgraph of Q'. In chapter 2 two characterizations of k-tree interval p-graphs ar e given one of which is a forbidden subgraph characterization. Moving to a different variation on the interval property, we next investigate probe interval 2-trees. A graph G is a probe interval graph (PIG) if there is a partition of V (G) into sets P and N and a collection {I v I v E V (G)} of intervals of the real line such that, for u v E V( G) uv E E( G) if and onl y if I u n I v =/= 0 and at least one of u, v belongs to P. Probe interval graphs were invented to help with modeling in the human genome project. Przulj and Corneil found in [41] that 2-tree probe interval graphs have a large set of forbidden subgraphs

PAGE 5

at least 62. We give a characterization of 2-tree PIGs and add to the list of forbidden subgraphs. The second concentration of this thesis, symmetries of graphs, began in 1996 with a paper by Albertson and Collins [2]. A coloring of the vertices of a graph G, f : V (G) { 1, ... r} is said to be r-distinguishing if no n o ntrivial automorphism of the graph preserves all of the vertex colors. The distinguishing number of a graph G is defined by D( G) = min { r I G has a coloring that is r-distinguishing }. Albertson and Collins determined the distinguishing number for graphs that realize the dihedral group. We let Dn denote the dihedral group of order 2n which is the group of symmetries of a regular n-gon. Albertson and Collins [2] proved that if G realizes Dn then D( G) = 2 unless n = {3 4 5 6 10} in which case D( G) is either 2 or 3. Since Albertson and Collins introduced this topic there has been mu c h investigation into distinguishing colorings. Areas of these investigations include the distinguishing number of Cartesian products ( [1], [6], [33], [35]), determining a bound on the distinguishing number ([17], [34]), and the distinguishing number of trees and forests ( [15]). In our investigations we generalize distinguishing colorings to list -distinguishing colorings. Given a family L of lists assigning available colors to the vertices of G we say that G is -distinguishable if there is a distinguishing coloring f of G such that f(v) E L(v) for all v. The list-distinguishing number of G written De( G) is the smallest positive integer k such that G is -distinguishable for any assignment L of lists with jL(v)j = k for all v. Since all of the lists can be identical we see that D( G) < De( G).

PAGE 6

Here we determine the list-distinguishing number for several families of graphs and highlight a number of distinctions between the problems of dis tinguishing and list-distinguishing a graph. We first give a Brooks-type result for list-distinguishing colorings. By determining precisel y when the distinguishing number is 3 in small cases we show that the list-distinguishing number is equal to the distinguishing number for all graphs that realize the dihedral group. Lastly we give the list-distinguishing number for some Cartesian product graphs. This abstract accurately represents the content of the candidate s thesis. I recommend its publication. Signed J. Richard Lundgren

PAGE 7

DEDICATION I dedicate this thesis to my parents, Doug Flesch and Janna Hertzler. Without their love and support, none of this would have been possible.

PAGE 8

ACKNOWLEDGMENT I would first like to thank my committee, as this thesis has been a collaborative effort of them all. Thank you to Rich Lundgren, my advisor. His mentoring has not only led to this thesis, but also to more fulfillment in my life. I am also thankful for everything that Dave Brown has done for me. His friendship has made all the difference in this process; I can't thank you enough. Meetings with Mike Ferrara and Ellen Gethner were not only a highlight of my week, they made me a better mathematician. For that, and your friendship, I thank you from the bottom of my heart. Participating in the GK-12 project for two years with Mike Jacobson has been an amazing experience. His advice has given me a better understanding of what it takes to be an educator. I would also like to thank the many friends that supported me during the last four years. Thanks to Annie Zimmerman for listening to me vent, almost nightly, around the dinner table. I am also grateful for Kristie Letter and her uncanny ability to understand and support me. Thank you to 1ny backbone, Matthew Nabity; I can't stand without you. Lastly, I would like to thank my daughters, Olivine and Mica, for making my life better and giving me motivation to continue on this journey.

PAGE 9

CONTENTS Figures . xi 1. Introduction 1 1.1 Prologue and Definitions 1 1.2 Interval Representations 4 1. 3 Symmetries . 9 2. k-tree Interval p-Graphs 14 2.1 Definitions and Background 14 2.2 A Characterization of k-Tree Interval p-Graphs 20 2.3 Forbidden Subgraph Characterization for 2-Tree Interval p-Graphs 26 3. 2-tree Probe Interval Graphs . 32 3.1 Structure of Probe Interval 2-trees 32 3.2 Probe Interval 2-tree Characterization 3.3 Forbidden Subgraphs for Probe Interval 2-trees 4. List-distinguishing Dihedral Graphs 4.1 Brooks-type Theorem. 4.2 Dihedral Groups 5. ListDistinguishing Cartesian Products 5.1 Motion Lemma 5.2 Products of Cycles 5.3 Products of Complete Graphs IX 43 52 58 58 61 81 81 84 90

PAGE 10

6. Concluding Remarks and Future Directions 6.1 Interval Representations 6.2 Symmetries References . X 95 95 96 98

PAGE 11

FIGURES Figure 1.1 The graphs NL10, H10, and NC7. . . . . 6 1.2 On the left is the 3-sun which contains an AT, and on the right is a 2-tree with an ATE. . . 7 1.3 A distinguishing coloring of K3DK4 10 1.4 A distinguishing coloring of C6 12 1.5 The coloring from the proof that De( Cn) = 2 when n > 6. The black vertices are colored anything from their list that is not c. 13 2.1 The three non-isomorphic 2-paths oflength five and six non-isomorphic 2-paths of length six. . . 15 2.2 A 2-tree with the 3-cliques of G2 -labeled. 16 2.3 HL is a 2-caterpillar, but not an interior 2-caterpillar, and HR is an interior 2-caterpillar. . . . . . . 16 2.4 On the left is a 2-lobster that is not a spiny interior 2-lobster, and on the right is a spiny interior 2-lobster. . 17 2.5 Labeled examples for the two cases in Theorem 2.4. 19 2.6 An example of a graph that does not have an interval p-representation (p > 3) and does not contain an ATE. . 20 2.7 Labeled examples for the two cases in Lemma 2.6 22 2.8 An example of a spiny interior 2-lobster that is labeled as in Theorem 2.7. 25 XI

PAGE 12

2.9 The interval p-representation of the 2-tree in Figure 2.8. 25 2.10 Forbidden subgraphs for 2-trees interval p-graphs. 27 2.11 The four graphs for Case 1 in Theorem 2.10. 28 2.12 Possible forbidden subgraphs for 2-tree interval p-graphs from Case 2 in Theorem 2.10. . . . . . . 30 2.13 Two examples of G12 without a vertex and the corresponding interval prepresentation. . . . . . . . 30 2.14 Examples of forbidden subgraphs without a vertex that still contain an ATE. . . . . . . . . 31 3.1 Three spiny interior 2-lobsters that are not probe interval graphs in [43]. . . . . . . . . 32 3.2 A spiny interior 2-lobster with the vertices and 3-cliques of G2 -labeled. . . . . . . . . 34 3.3 Three sparse spiny interior 2-lobsters with the vertices and 3-cliques of G2 -labeled. . . . 35 3.4 Two labeled examples for Lemma 3.6. 37 3.5 An example for the proof of Lemma 3.7 where any placement of the interval for a produces a contradiction. . . . 38 3.6 An example for the proof of Lemma 3.7 where any placement of the interval for a produces a contradiction. . . . 38 3.7 An example for the proof of Lemma 3.7, where the placement of the interval for d forces an adjacency between a and d, which is a contradiction. .......................... 40 xu

PAGE 13

3.8 Graphs Q and the 3-sun with their possible (P, N)-partitions up to isomorphism. The white vertices are non-probes, black are probes, and the grey can be either a probe or non-probe. . 40 3.9 Examples for Cases 1, 2, and 3 in the proof of Lemma 3.8 42 3.10 Hi, i E z+ . . . . . 43 3.11 A ssi2-lobster with vertices labeled as in Lemma 3.11 46 3.12 The probe interval representation for Figure 3.11 47 3.13 Labeled examples for Case 2 in the proof of Theorem 3.12. 49 3.14 Labeled examples for Case 3 in the proof of Theorem 3.12. 50 3.15 The graphs H1 S, and G1 . . . . 52 3.16 Three probe interval representations for H1 minus a vertex. 53 3.17 The graphs N1 through N6 are not probe interval 2-trees. 55 3.18 The graphs Sf6 and N6 are not isomorphic. . . 56 3.19 The graph N1 and two induced subgraphs of N1 one a PIG and one not a PIG. . . . . . 56 4.1 A labeled picture to illustrate Proposition 4.4. 60 4.2 Two graphs that realize D6 62 4.3 An illustration of Lemma 4.8. 63 4.4 An illustration of Case 1 and Case 2 of Lemma 4.11, where c =1c'. 67 4.5 An illustration of Cases 3 and 4 of Lemma 4.11, where c =1c' and x y =1z. . . . . . . . . 70 4.6 Two graphs that realize D5 with example lists and list-distinguishing colorings using white, black, and grey. . . . . 7 4 Xlll

PAGE 14

4. 7 Two graphs that realize D4 with example lists and list-distinguishing colorings using white, black, and grey. . . . . 75 4.8 Two graphs that realize D6 with example lists and list-distinguishing colorings using white, black, and grey. . . . . 77 4.9 Two graphs that realize D10 with example lists and list-distinguishing colorings using white, black, and grey. . . . . 80 5.1 Let' : (ui,vj) (ui,agvj) E Aut(C4 DC 5 ) to illustrate Lemma 5.5. If (u1,v1) (u4,v5) in', then (u1,v2) (u4,v1), (u1,v3) 85 5.2 Examples of colorings described in Lemma 5.6. Vertices represented by open circles cannot be colored black. . 88 5.3 Examples of colorings described in Lemma 5.8. 90 5.4 A list-distinguishing coloring of the matrix that represents K 3DK4; c1 c2 and c3 need not be distinct. . . . . 91 5.5 Examples of list-distinguishing colorings of the matrix that represents K 3DK4 from the proof of Theorem 5.11. . . 93 XIV

PAGE 15

1. Introduction 1.1 Prologue and Definitions Questions in Graph Theory can often be stated as: "Determine which graphs have property
PAGE 16

vertices as abc. The degree sequence of a graph is the list of vertex degrees, where the degree of a vertex is the number of edges incident to that vertex. In this thesis, the degree sequence is listed in non-decreasing order. A k-coloring of a graph G is a labeling f: V(G) S, where lSI = k. A kcoloring is proper if adjacent vertices have different labels. A graph is k-colorable if it has a proper k-coloring. The chromatic number x( G) is the least k such that G is k-colorable. A k-edge-coloring of G is a labeling f : E( G) S, where lSI = k. A k-edge-coloring is proper if incident edges have different labels. A graph is k-edge-colorable if it has a proper k-edge-coloring. The edge-chromatic number x' (G) of a loopless graph G is the least k such that G is k-edge-colorable. For each vertex v in a graph G let L( v) denote a list of colors available at v. A list coloring is a proper coloring f such that f( v) E L( v) for all v. A graph G is list k-colorable if every assignment of k-element lists to the vertices permits a proper list coloring. The list chromatic number xe( G) is the minimum k such that G is list k-colorable. Let L( e) denote the list of colors available for an edge e. A list edge-coloring is a proper edge-coloring f with f(e) chosen from L( e) for each e. The edge-choosability G) is the rninimum k such that every assignment of lists of size k yields a proper list edge-coloring. We say that an order of subgraphs G1 ... Gn of a graph G is consecutive if u E V(Gi)nV(Gj), i < .i, then u E V(Gk) for all i < k < j. When a consecutive order exists for a family F of subgraphs, we say that F is consecutively orderable. A collection of sets is said to have the Helly property if whenever a subcollection sl' ... 'sk of them intersect pairwise, then si is nonempty. 2

PAGE 17

A breadth-first search (BFS) starts at a given vertex v, which we call the root and is at level 0. In the first stage, we visit all vertices that are at the distance of one edge away, and all of these vertices are placed into level 1. In the second stage, we visit all the new vertices we can reach at the distance of two edges away from v. These new vertices, which are adjacent to the level 1 vertices and are not previously assigned a level, are placed into level 2, and so on. The BFS traversal terminates when every vertex has been visited and creates a BFS spanning tree of a connected graph G. The parent of a vertex x is the vertex immediately following x on the unique path from x to the root v on the BFS tree. Two vertices are siblings if they have the same parent. A descendant w of x is any vertex that contains x on the path from w to the root v on the BFS tree. An ancestor of x is any vertex on the path from x to the root v on the BFS tree. An isomorphism from a graph G to a graph H is a bijection f : V (G) ---t V(H) such that uv E E(G) if and only if f(u)f(v) E E(H). We say G is isomorphic to H, written G rv H if there is an isomorphism fron1 G to H. An automorphism of a graph G is a permutation a of the vertex set V (G), such that for any edge e = (u, v), a( e) = (a(u) a(v)) is also an edge. The set of automorphisms of a given graph, under the operation of composition forms a group. A group is an ordered pair ( G, *) where G is a set and is an operation on G satisfying the following axioms: (1) For all a, b E G, a* b E G so G is closed under *, (2) (a* b) c = a* (b *c) for all a, b, c E G so is associative, (3) there exists an element e in G called the identity, such that for all a E G we have e *a = a* e = a, and ( 4) for each a E G there is an element a-1 of G 3

PAGE 18

called an inverse of a, such that a* a-1 = a-1 a = e. A subset S of elements of a group G with t he pro perty that every element of G can be written as a product of elements of S and their inverses is called a set of generators of G. We denote this as G = ( S) and say that G is generated by S. If His a nonempty subset of a group G such that His closed under the binary operation on G and is closed under inv e rs es, we call H a subgroup of G. Let G be a graph and let r be a gr o up. If Aut( G ) ""' r then we will say that G realizes r. For a v erte x v in G we let St(v) = {h E fiv h = v } and O(v ) =-{blv = hb for some h E r} be the stabilizer and orb i t of v unde r t h e action of r on G. The size of the o rbi t o f v unde r the action of r o n G i s IAut(G)I/ISt(v)l, which is r e ferred to as the Orbit/Stabilizer Th eorem A group act i on of a group G on a set A is a map from G x A to A(written as g a for all g E G and a E A) satisfying the following properties: ( 1 ) g1 (g2 *a) = (gl g2) *a, for all g1, g2 E G a E A and (2) e a = a, for a ll a EA. 1. 2 Interval Representations A graph is interval if to eve r y vertex v E V ( G ), we can assign an interval of the real line Iv, such that xy E E ( G ) if and only if I x n I y =I= 0 We cal l the set of intervals of the r eal lin e the interval repre entation of the graph. We let I v denote the inte rval corres ponding the the vertex v and lv, r v denote the left and right endpoints of l v Interval graphs were introduced in a question posed by H a j 6s [29] in 1957. In 1959 B enzer used interval graph to model the fine structure of a g ne [ 5 ] This in teresting application helped keep in en,-al graph in the literatur and l ed to variations on t h e interval property. 4

PAGE 19

Interval graphs were characterized by the absence of induced cycles larger than 3 and asteroidal triples by Lekkerkerker and Boland [38] in 1962. An asteroidal triple (AT) in G is a set A of three vertices such that between any two vertices in A there is a path within G between them that avoids all neighbors of the third. The vertices a, b, and c form an AT in the graph called the 3-sun in Figure 1.2. Other characterizations of interval graphs soon followed in [23] and [25], including a characterization of interval graphs as those that have a consecutive ordering of cliques. A natural extension of interval graphs, called interval bigraphs were Introduced by Harary, Kabell, and McMorris [30] in 1982. A bipartite graph G = (X, Y) is an interval bigraph if to every vertex, v E V (G), we can assign an interval of the real line, Iv, such that x y E E( G) if and only if Ix n Iy # 0 and x E X and y E Y. Interval digraphs, which are related to interval hi graphs, were introduced by Sen, Das Roy and West in [46], where they also gave a characterization of interval digraphs (and hence interval bigraphs) based on the adjacency matrix. Interval bigraphs have been studied extensiv e ly ([12], [15], [30], [31], [39], and [41 ]), which includes a consecutive ordering of complete bipartite graphs characterization. Initially it was thought that the natural ex tension of asteroidal triples of vertices to asteroidal triples of edges along with induced cycles larger than 4 would be another characterization of interval higraphs [30]. However, Muller [41] found insects and Hell and Huang [31] found edge asteroids and bugs as forbidden subgraphs, and to date the only forbidden subgraph characterization in the literature is for cycle-free interval bigraphs (see Theorem 1.1). Three edges a c and e of a graph G form an asteroidal tripl e of 5

PAGE 20

edges (ATE) if for any two there is a path from the vertex set of one to the vertex set of the other that avoids the neighborhood of both vertices of the third edge. The edges bx, cz, and ay form an ATE in Figure 1.2. Since it is not pertinent to our studies, we will forgo defining insects, bugs, and edge asteroids in this thesis. Theorem 1.1 {15} A cycle-free graph G is an interval bigraph and only has it has no NL1 0 of Figure 1.1 as an induced subgraph. NLJO HJO NC7 Figure 1.1: The graphs NLlO, HlO, and NC7. In 2002 Brown, Flink, and Lundgren introduced a further extension of in terval bigraphs called interval k-graphs [13]. We change the name to interval p-graphs here to avoid confusion. Let G = {X11 X2 ... Xp} be a multipartite graph. The graph G is an interval p-graph if there exists an assignment to each vertex, v E V( G), an interval of the real line, Iv, such that xy E E( G) if and only if Ix n Iy =f. 0 and X E xi, y E xj and i =f. j. We call a set of intervals of the real line plus a partition of the vertices an interval p-representation of the graph. We consider the vertices of each partite set to have the same color, so adjacency results when two vertices have overlapping intervals and are different colors. The only characterization of interval p-graphs is with a consecutive ordering of completer-partite subgraphs (see Theorem 1.2). 6

PAGE 21

Theorem 1.2 {13} A graph is an. interval p-graph if and only if there exists a cover of completer-partite subgraphs that can be consecutively ordered, when 1 < r < p for each subgraph. 3-sun Figure 1.2: On the left is the 3-sun which contains an AT, and on the right is a 2-tree with an ATE. A forbidden subgraph characterization for interval p-graphs appears to be very difficult as in the case for interval bigraphs, so it seems natural to consider generalizing Theorem 1.1 to the class of graphs called k-trees. The class of k trees is the set of all graphs that can be obtained by the following construction: (i) the k-complete graph, Kk, is a k-tree; (ii) to a k-tree Q' with n-1 vertices ( n > k) add a new vertex adjacent to a k-complete subgraph of Q'. Both graphs in Figure 1.2 are 2-trees. Chapter 2 contains a characterization of k-tree interval p-graphs and a forbidden subgraph characterization of 2-tree interval p-graphs. Through advances in genetics, the need for a new model that was similar to Benzer's original model arose. In 1994 probe interval graphs were introduced by Zhang to model the physical mapping of clones, small subsequences of DNA, for the human genome project ([48], [52], [51], and [50]). A graph G is a probe interval graph (PIG) if there is a partition of V(G) into sets P and N and a collection {I v I v E V (G)} of intervals of the real line such that, for u, v E V (G), uv E E( G) if and only if Iu n Iv =1-0 and at least one of u, v belongs to P. 7

PAGE 22

Intervals of the real line together with a (P, N)-partition will be referred to as a probe interval representation of the graph. Considering clones to be vertices and adjacency to be overlap in the sequence of the clones, the model is a probe interval graph with each vertex a probe. However, we do not always have all of the information for the clones or do not want to work with all of the clones at once. Thus a probe interval graph where only the vertices of clones of interest are defined to be probes gives more flexibility in the model. For our purposes, we consider only the structural properties of probe interval graphs. PIGs and related topics have been studied extensively, including [16], [14), and (27], with many results. McMorris, Wang, and Zhang (40) characterized PIGs as those graphs that have a consecutive ordering of quasi cliques (see [40]). A quasi clique Q in a PIG G with a (P, N)-partition is a set of vertices with all vertices of Q n P adjacent, and any vertex of Q n N adjacent to all vertices of QnP. In 1999 Sheng found in [47) a forbidden subgraph characterization of cycle free probe interval graphs (see Theorem 1.3), which remains the only forbidden subgraph characterization of PIGs to date. Sheng also found in (47) that the vertex of degree three in an induced NL7 (see Figure 1.1) must be a non-probe in any probe interval representation, which will be used often in this thesis. Moving up from trees, Przulj and Corneil found in (43) that 2-tree PIGs have a large set of forbidden subgraphs, at least 62. They gave no unifying characteristic of the. 62 forbidden subgraphs and made no claim that their list was complete. In chapter 3 we give a characterization of 2-tree PIGs and add to the list of forbidden subgraphs. 8

PAGE 23

Theorem 1.3 [4 7} A cycle-free graph is a probe interval graph if and only has no induced subgraph isomorphic to H10 or N L10 in Figure 1.1. 1.3 Symmetries Frank Rubin posed the following question in [44] in 1979. Professor X, who is blind, keeps keys on a circular key nng. Suppose there are a variety of handle shapes available that can be distinguished by touch. Assume that all keys are symmetrical so that a rotation of the key ring about an axis in its plane is undetectable from an examination of a single key. How many shapes does Professor X need to use in order to keep n keys on the ring and still be able to select the proper key by feel? In 1996 Albertson and Collins [2] framed this question in terms of Graph Theory, which gave rise to the following definitions. A coloring of the vertices of a graph G, f : V(G) {1, ... r} is said to be r-distinguishing if no nontrivial automorphism of the graph preserves all of the vertex colors. The distinguishing number of a graph G is defined by D(G) = min {r I G has a coloring that is r-distinguishing }. The professor's key ring can be represented as a cycle and the different handle shapes are vertex colors. As it turns out, three handle shapes are required for five or fewer keys and two handle shapes for six or more keys. Given the origins of the problem, Albertson and Collins determined the distinguishing number for graphs that realize the dihedral group (see Theorem 4.6). We let Dn denote the dihedral group of order 2n, which is the group of symmetries of a regular n-gon. We use the standard presentation Dn = (O"n, = = e, O"nTn = Tn0";1 ) where .O"n and Tn denote the appropriate 9 r

PAGE 24

rotation and reflection of the n-gon, re spective ly. We will write Tn an = a if the context is clear. T and Since Albertson and Collins introduced this topic there has been much investigation into distinguishing colorings. Areas of these investigations include the distinguishing number of Cartesian products ([1], [ 6], [35), [ 37 ]), determining a bound on the distinguishing number ([19), [ 36 ]), and the distinguishing number of trees and forests ([17]). The Cartesian product of G and H written GDH, is the graph with vertex set V(G) x V(H) specified by putting (u, v) adjacent to ( u', v') if and only if (1) u = u' and vv' E E(H), or ( 2) v = v' and uu' E E ( G ) (see Figure 1. 3). Figure 1.3: A distinguishing coloring of J{30K4 In our studies we generalize distinguishing colorings to list-distinguishing colorings. Given a famil y L of lists assigning availabl e co lors to t h e vertices of G we say that G i s L-distinguishabl e if there is a distinguishing coloring f of G such that f(v ) E L(v ) for all v The list -d istinguis h ing number o f G vvTitten De( G), i s the smallest positive intege r k such that G is L-di stinguisha bl e f o r any assignment L of lists wi t h I L ( v) I = k for all v Sin ce all o f t h e lists can be 10

PAGE 25

identical, we see that D(G) < De(G). Moving from a coloring property to the list-coloring variant has yielded di verse results. Erdos, Rubin, and Taylor found that there are bipartite graphs with arbitrarily large list chromatic number (see Theorem 1.4). Since the chromatic number of a bipartite graph is 2, the chromatic number and the listchromatic number can be arbitrarily far apart. Theorem 1.4 ([21]) If m = (2k;1), then Km,m is not list k-colorable. On the other hand, the long-standing List Coloring Conjecture states that G) = x' (G) for all G. This conjecture was suggested independently by many researchers, including Vizing, Gupta, Albertson, Collins and Tucker, but it is most often credited to Bollobas and Harris in [7]. These differences in the list variant of a coloring property versus the original coloring property bring us to the central question of our investigations into list distinguishing colorings. Question 1.5 Does there exist a graph G such that D( G) < De( G)? In some cases, the list-distinguishing number can readily be shown to be equal to the distinguishing number. For example D(Kn) = n = De(Kn), since Aut(Kn) = Sn In other cases when D(G) = De(G), the proof techniques can be significantly different; we consider the proof that D( Cn) = 2 = De( Cn) when n > 6 as an illustrative example. The proof that D( Cn) = 2 when n > 6 relies on a clever coloring to distinguish (see Figure 1.4); whereas, the proof that De( Cn) = 2 when n > 6 requires a more in-depth strategy. 11

PAGE 26

Figure 1.4: A distinguishing coloring of C6 Proposition 1.6 For n > 6, DR-( Cn) = D( Cn) = 2. Proof: Assign list L(v) such that IL(v)l = 2 to each v E V(Cn) If I U L(v)l = 2, then the lists are identical, so we can color the vertices as the distinguishing coloring, and we are done. Assume then that I U L( v) I -::/= 2 and let c be the color that appears the fewest lists. Choose a vertex with c in its list and label it v1 then continue labeling the vertices consecutively clockwise in numerical order. Since c appears the fewest lists, there are at least vertices that do not have a c in their list. Choose a vertex, vi, such that c :. L(vi) and is not antipodal to v1 Consider the vertex Vn+2-i, which is across from vi. There exists x E L( Vn+2-i) such that x -::/= c; color Vn+2-i with x. Now there is a y E L( vi) such that y-::/= x and we know that y -::/= c, so color vi with y. Now color the remaining vertices with any element from their list that is not c (see Figure 1.5). Any color-preserving automorphism must map vi to VI, since it is the only vertex colored c. Therefore, either vi 1--t Vn+2i or vi 1--t Vi In the former case, the automorphism does not preserve the colors. This leaves us with only the latter, which is the trivial automorphism. Therefore the coloring is list-distinguishing, and DR-( Cn) = D( Cn) = 2. 12

PAGE 27

e. 0 l1 Figure 1.5: The coloring from the proof that De(Cn) = 2 when n > 6. The black vertices are colored anything from their list that is not c. In Chapter 4 we give a list-distinguishing Brooks-type theorem and show that D( G) =De( G) for all graphs that realize the dihedral group. In Chapter 5 we show that D( G) = De( G) for certain Cartesian product graphs. 13

PAGE 28

2. k-tree Interval p-Graphs In this chapter we give two characterizations. First we characterize k-trees interval p-graphs as spiny interior k-lobsters We next use this result to give a forbidden subgraph characterization of 2-tree interval p-graphs. 2.1 Definitions and Background To describe the structure of k-trees, we use the generalized idea of a path introduced by Beineke and Pippert in [4]. Definition 2.1 A k-path of G is an alternating sequence of distinct k-and (k + I)-cliques of G, (e0 t1, ell t2 e 2 ... tP, ep), starting and ending with a kclique and such that ti contains exactly two of the distinct k-cliques: ei-l and ei (I < i < p). The length of the k-path is the number p of (k +I)-cliques. The letters e and t in the definition of a k-path are used to stand for edges and triangles, in the case of 2-trees. This gives one good intuition for the structure of a 2-path, a sequence of distinct edges and triangles. Although there is a unique path of length p up to isomorphism, this is not true for k-paths. For example, Przulj and Corneil [43] proved that there are three non-isomorphic 2-paths of length five and six non-isomorphic 2-paths of length six (See Figure 2.I) Drawing further parallels to trees, Proskurowski introduced the notion of a k-caterpillar in [42], and we introduce a spiny interior k-lobster. Before we do this, we classify some of the structure of a k-tree I4.

PAGE 29

Figure 2.1: The three non-ismnorphic 2-paths of length five and six nonisomorphic 2-paths of length six. A vertex v E V(G) is a k-leaf of G if Na(v) is a clique. Let G beak-tree and define G1 -to be G-Pa, where Pais the set {v E V(G): vis a k-leaf of G}; iteratively, G2 -= G1-Pa1-. Suppose G is a k-tree such that G2 -is the k-path (eo, t1, e1, h, ... tp, ep), such that e0 and ep are defined in the following way. L e t a0 be a k-leaf of G1 -such that Na1-(a0 ) C t1 and ap be a k-leaf of G1 -such that Na1-(ap) C tp. Define e0 = Na1-(a0 ) and ep = Na1-(ap) We will define e0 and ep in this way for the rest of the thesis, as it is important for subsequent definitions. We now describe two sets of k-leaves in G and G1 respectively. 81 G = { v E V (G) : v is a k-leaf of G N a ( v) =1e i ( 0 < i < p)}; 82G = {v E V(G1-): vis a k-leaf of G1-, Na1-(v) =/:ei (0 < i < p)}. In Figure 2.2, G2 -is the graph induced by the vertices { v1 ... v6}. Also e0 = v2v1 and e4 = v5v6 because of the 2-leaves of G1 -x and z, respectively. For this 2-tree, 81 G = {a, b, c, d, f, g, h, j} and 82G = 0 since the 2-leaves of G1 -are {x,y,z,u}, all of which are adjacent to some ei in G2-. Definition 2.2 A 2-caterpillar is a 2-tree G such that G1 -is a 2-path. An interior 2-caterpillar is a 2-caterpillar G such that there does not exist a vertex a 15

PAGE 30

Figure 2.2: A 2-tree with the 3-cliques of G2 -labeled. such that a E 81G and Na(a) c G2 -and there does not exist vertices x, y E 8 1 G such that Na(x) f= Na(Y) and Na2-(x),Na2 (y) c ei,i E {O,p}. Figure 2.3: HL is a 2-caterpillar but not an interior 2-caterpillar, and HR is an interior 2-caterpillar Although HL and HR in Figure 2.3 are 2-caterpi.llars, HL is not an interior 2-caterpillar for two reasons. First the vertex a is in the set al H L since it is a 2-leaf of HL and its neighborhood is not an ei of Hz-. Furthennore, NHL(a) is completely contained in Hz-, thus it violates the first condition of being an interior 2-caterpillar. Moreover the vertices x andy violate the second condition of being an interior 2-caterpillar. They are both in the set al H L' their neighborhoods are not the same in Ht, and both neighborhoods in Hzare subsets of eo. The definition of an interior k-caterpillar is technical, but one can draw on intuition from the word 'interior' for understanding. The graph HR in Figure 2.3 16

PAGE 31

is an interior 2-caterpillar since all of the 2-leaves are adjacent to the 'interior' edges of the 2-path Hk-. The first condition of being an interior k-caterpillar says that all k-leaves are adjacent to interior cliques of the k-path G2-. The second condition of being an interior k-caterpillar makes sure that nothing goes wrong at the ends of the k-path G2-, since it deletes two vertices on either end of the longest k-path in the original graph G. This brings us to our next definition. Definition 2.3 A graph G is a k-lobster if G2 -is a k-path. A spiny interior k-lobster is a k-lobster G with 82G = 0. Figure 2.4: On the left is a 2-lobster that is not a spiny interior 2-lobster, and on the right is a spiny interior 2-lobster. Since caterpillar and lobster are names used to define trees, it seems natural to use the name k-lobster for k-trees. The modifier of interior is put on the klobster to signify that all k-paths of length 2 originate from the interior cliques of the k-path G2 -in a spiny interior k-lobster (see vertex y in Figure 2.4). The word spiny is added to signify that there could be k-leaves whose adjacency is not an interior clique (see vertex z in Figure 2.4). In the 2-tree on the left in Figure 2.4, x E 82H, which is why it is not a spiny interior 2-lobster. Another way to define a spiny interior is that G is a interior k-lobster if G1 -is an interior k-caterpillar. It is well known that a tree is an interval graph if and only if it is a caterpillar [15]. However, a 2-caterpillar may not be an interval graph since it could contain 17

PAGE 32

an asteroidal triple of vertices (x y and z in Figure 2.3 are an AT). Eckhoff studied k-trees in the context of extremal interval graphs in [20]. He found that G is a ( k + 1 )-extremal interval graph if and only if it is an interior k-caterpillar. Therefore, interior k-caterpillars are the class of k-trees that are interval graphs. We include a simplified proof for completeness. Theorem 2.4 If G is an interval k-tree the n G is an interior k-caterpillar. Proof: Let G be a k-tree that is not. an interior k-caterpillar and let P = (eo, t1, e1 ... tP, ep) be a longest k-path in G 1 such that e0 and e p ar e the neighborhoods of k-leaves of G. Either G is not a k-caterpillar or it is a k-caterpillar that is not an interior k-caterpillar. If it is not a k-caterpillar then there is some vertex v that is not on P. If it is a k-caterpillar that is not an interior k-caterpillar, then there is some vertex v tJ. P adjacent to some k ver tices of a ti such that ei_ 1 ei =/:. N p ( v). If i = 1 or p then the second condition of being a k-caterpillar that is interior is violated; otherwise, the first condition of being a k-caterpillar that is interior is violated. First we consider the case where there is a vertex, v tJ. P adjacent to some k vertices of a t i such that ei-b e i =/=Np(v). If no such v exists, then G is not a k-cat e rpillar and there are two vertices a, bE V(G) such that Np(a) = e i for 1 < i < p-1 and Np(b) C ei and a E Nc(b). Case 1: Assume there exists a vertex, v tJ. P, adjacent to some k vertices of a ti such that ei-b ei =/=Np(v). Label z as the vertex not inti with ei-1 C Nc(z), w the vertex not in ti with ei C JV c ( w), and y as the vertex such that t i = N p ( v) +y. We know z and w exist since G is not an interior k caterpillar and P was the 18

PAGE 33

longest k-path in G1-. Label N p ( v) = 1, 2, .. k such that z is adjacent to 1, 2, .. k-1 and w is adjacent to 2, 3, .. k. Notice that y is one of the vertices labeled as {3, ... k-1}, and z, w E Na(y), since ei_1 ei -=f. Np(v). The path z1v avoids Na(w), and zyw avoids Na(v) and vkw avoids Nc(z) (see G1 in Figure 2.5). Therefore, { w, v, z} is an asteroidal triple, and G is not interval. Case 2: Assume there are two vertices a, bE V(G) such that Np(a) = ei for 1 < i < p-1 and Np(b) C ei and a E Na(b). Let ti = z + ei, ti+1 = w + ei, y be a vertex not inti such that ei_1 c Np(y), and v be a vertex not inti such that ei+1 C Np(v). We know that the vertices {z,y,w,v} exist since Pis the longest k-path in G1 -and G is not an interior k-caterpillar. Let N p(b) = e i -c, and notice that a, z, and ware adjacent to c, since they are each adjacent to all the vertices in ei. The vertices y and v are both not adjacent to a vertex in ei, label these vertices as d and e respectively. The path yzcwv avoids Na(b); the path yzeab avoids Na(v); and the path vwdab avoids Nc(Y) (see G2 in Figure 2.5); Thus {y, v, b} is an asteroidal triple, and G is not interval. f. l Figure 2.5: Labeled examples for the two cases in Theorem 2.4. 2.2 A Characterization of k'free Interval p-Graphs 19

PAGE 34

Now we turn our attention to interval p-graphs. Brown, Flink and Lundgren found in [13] that although interval p-graphs can contain an asteroidal triple, they cannot contain an asteroidal triple of edges. Furthermore, Brown found in [11] that there are graphs that have no interval p-representation and do not contain an ATE (see Figure 2.6). Theorem 2.5 {13} If a graph G has an asteroidal triple of edges then G is not an interval p-graph. Figure 2.6: An example of a graph that does not have an interval prepresentation (p > 3) and does not contain an ATE. Using the characterization of cycle-free interval bigraphs and Theorem 2.4 as motivation, one might hope that either k-lobsters or interior k lobsters characterize k-trees that have an interval p-representation. However, in Figure 2.4 the 2-lobster on the left has an ATE Interior k-lobsters are interval p-graphs, but do not completely characterize the family. We now show that spiny interior k-lobsters characterize k-trees that have an interval p-representation. Lemma 2.6 If G is a k-tree that is not a spiny interior k-lobster then G con tains an asteroidal triple of edges. Proof: Let G be a k-tree that it is not a spiny interior k-lobster. Let P = (e0 t1, ell ... tp, ep) be the longest k-path in G2-, such that e0 and ep are the neighborhoods of k-leaves of G1-. It follows from the definition of a spiny 20

PAGE 35

interior k-lobster that either there exists a vertex a E V(G2-) P or there exists a vertex a E 82G. We will first consider the case that there is a vertex a E V(G1-) such that Np(a) c ti, but ei_1 ei # Np(a). This a could be in 82G or it could be in V(G2-)P. Thus the only remaining way that G could not be a spiny interior k-lobster is if there exists a E V(G2-)P such that Np(a) = ei for some 1 < i < p -1. Case 1: There exists a vertex a E V(G1-) such that Np(a) c t i but ei-1, ei # Np(a). Label some vertices in ti as follows: ti = ei_1 + m, ti = ei + n, and ti = Np(a) +y. Notice from the definition of a k-path and our choice of vertex a that m, n, andy are distinct vertices. Label the vertices z, w E V(G1-) such that z tj. ti and ei-1 C Np(z) and such that w tj. ti and ei c Np(w); label r, v E V(G) such that z, g E Np(r) where g is any vertex of ei_1 and w, f E Np(v) where f is any vertex of ei. We know that the v e rtices {r z, w v} exist, since G2 -is missing two vertices on either end of the longest k-path in G. Moreov e r since the vertex a is in V(G1-), there must be a vertex b tj. P such that Np(b) c t i and a E Nc(b). We claim that the edges {rz, ab, wv} form an ATE (see G1 in Figure 2. 7). The path r zywv avoids N c ( ab); the path r znab avoids N c ( wv); and the path vwmab avoids N c ( r z). Case 2: There exists a vertex a E V ( G2-) P such that N p (a) = ei for some 1 < i < p -1. Since Pis the longest path in G2-, the cliques ti and ti+1 must exist on P, so label ti = z + ei and ti+1 = w + ei. Let r E V(G1-) such that z, g E Np(r) where g is any vertex in ei, and let v E V(G1-) such that w f E Np(v) where 21

PAGE 36

f is any vertex in ei. Notice that there must be a vertex in ei that is not in the neighborhood of r, so label this vertex d, similarly, there must be a vertex in ei that is not in the neighborhood of v, so label this vertex e. Now let s E V(G) such that r, g E N a ( s) where g is any vertex in ti, and let y E V (G) such that v, f E Na(Y) where f is any vertex in ti+l Again we know that the vertices {r, s, y, v} exist, since G2 -is missing two vertices on either end of the longest k-path in G. The vertex a is in V ( G2-) P, so there must be a vertex b E V ( G1-) such that Np(b) C ei and a E Na(b). Not all of ei can be in the neighborhood of b, so let c E ei such that c tt. Na(b). The vertices c, d and e need not be distinct. Furthermore, there is also a vertex h E V (G) such that N p (h) C ei and bE Na(h). We claim that the set {rs, vy, bh} is an ATE (see G2 in Figure 2.7). The path srzcwvy avoids Na(bh); the path srzeabh avoids Na(vy); and the path hbadwvy avoids N a ( r s). f. l Figure 2.7: Labeled examples for the two cases in Lemma 2.6. We now give the main result of this section. 22

PAGE 37

Theorem 2. 7 A k-tree G zs an interval p-graph if and only if it is a spzny interior k-lobster. Proof: Let G beak-tree that has an interval p-representation, and assume for contradiction that G is not a spiny interior k-lobster. By Lemma 2 .6, G contains an asteroidal triple of edges. By Theorem 2.5, interval p-graphs can not contain an ATE, which is a contradiction to our assumption. Suppose G is a spiny interior k-lobster. Let G2 -= ( e 0 t 1,e1 ... ,tp,ep), where eo and ep are the neighborhoods of some k-leaves of G1-, g and h. La bel to = eo + g and tp+l = ep + h. Since g and h are k-l e av e s of G1-, the re must be k-leaves of G, a and b, such that a E Nc(g) and b E Nc(h). Label t_l = e l +a = Nc(a) +a and tp+l = e p+l + b = Nc(b) +b. Lastly, l e t e-2 be any subset of t_1 of size k that contains a and let ep+ 2 be any subset of tp+l of size k that contains b. The sequence of k-and k + 1-cliqu e s (e-2, t_l, e_I, to, eo, t1, e1, ... tp, ep, tp+b e p+l, tp+2, e p+2) is a longest k-path in G and we call it P. For each vertex v E P assign an ordered pair ( x y) such that tx is the first clique that contains v and ty is the last. To each vert e x assign the interval Iv = (x, y + Assign the colors 1, 2 ... k + 1 to the vertices of t_1 and assign colors to the rest of the body as follows. If t i = ei-l + ai and til = ei-1 + bi-1 assign ai the same color as bi-l For the (k + 1)-clique ti the vertices' intervals intersect at ( i, i + and are all different colors, and intervals for the v e rtices of each ei intersect at ( i + i + 1) and are all different colors. For each t i there are k-1 possible unique neighborhoods for a k-leaf, wi,1 ... wi,k-1, such that N(wi,j) c ti, but N(wi, j) =f. ei or ei-l For each unique neighborhood there 23

PAGE 38

may be many k-leaves, which all are assigned the same label. Assign the interval wi, j = ( i + 2fk-_\), i + 2(/_1)) to each of these k-leaves. Each k-leaf is adjacent to k of the k + 1 vertices in the clique ti, so let hi,j = ti N ( wi,j). Color wi, j the same as hi,j None of the intervals for the k-leaves wi,1 ... wi,k-l intersect, so no adjacencies result between them. Each k-leaf is the color of the vertex that is not in its neighborhood. So although each k-leaf's interval intersects all the intervals of the clique, adjacencies only result amongst each k-leaf and its k neighborhood in the clique. Furthermore, leaves with a common label are the same color, so there is no resulting adjacency from their overlapping intervals. There may be many k-paths of length one or two originating from each e i. Let there be n vertices not on P adjacent to the k vertices of some ei, and label th 'T' h th t l ---'( 1 i=l 1 _i_) L t em zi,1 ... zi,n .tO eac assign e In erva Zi,j z + 2 + 2n z + 2 + 2n e ti = ei + bi and color zi,j, 1 < j < n the same as b i For each zi j there are k possible k-leaves, mi,j,1 ... mi,j,kl such that zi,j E N(mi, j ,e) and N(mi,j,e) C e i + zi,j Again, there may be many different k-leaves of this type that have the same label. Assign the interval mi, j e = ( i + + + i + + + If 9i,j,e = ei + zi,j -N(mi,j, e), color mi, j e the same as 9i,j,e None of the intervals for the k-leaves intersect, so no adjacencies result between the leaves. Each leaf is adjacent to k of the k + 1 vertices of ei + zi,j and is the color of the vertex that is not in its neighborhood, so the desired adjacencies result. Again, the k-leaves with the same label are the same color, so there is no resulting adjacency from their overlapping intervals. Therefore, we have a p-interval representation for the spiny interior k-lobster. 24

PAGE 39

a 112.1 m 3,1,1 h m '4,1,1 Figure 2.8: An example of a spiny interior 2-lobster that is lab eled as in Theorem 2.7. Figure 2.8 gives a spiny interior 2-lobster with the appropriate labels as in the proof of Theorem 2. 7. In the proof we extend G2 -arbitrarily by two cliques on both ends; notice that either vertex z4 1 or h, could hav e received the 'h' label. Figure 2.9 gives the inter val p-representation for the graph in Figure 2.8 based on the proof above. mJ.I.I1-1).1= m' r;;m;JmJ 1 2 1 1 '3,1,11-1)/= zJ.J= -z4, I.. h g li> b = I I I I I I I I I I I -1 0 1 2 3 4 5 6 Figure 2.9: The interval p-representation of the 2-tree in Figure 2.8. Combining the results from Lemma 2.6 and Theorem 2.7, we get the following corollary. 25

PAGE 40

Corollary 2.8 A k-tree G is a spiny interior k-lobster if and only if G does not contain an asteroidal triple of edges. The relationship between k and p m the prevwus theorem is a topic of interest. In the proof, we use k + 1 colors for the interval p-assignment. This is the minimal number of colors that can be used, since Kk+l is a subgraph of any non-trivial k-tree. In fact, interval p-graphs have been shown to be perfect in [11], and since collections of intervals have the H e lly property, there is never a need for more colors than the size of the largest clique in the graph. However, it is possible to use more colors if there is an advantage. For example, we could have used the color red instead of white on the vertex z3 1 in Figure 2.8. In fact when G is a spiny interior k-lobster, we can use a different color for each vertex of G1 -since it is a interior k-caterpillar' which has an interval representation. This is why we left the statement of this theorem in terms of k and p. Thus we conclude this section with the following corollary. Corollary 2.9 A k-tree G is an interval (k + 1)-graph if and only if G zs a spiny interior k-lobster. 2.3 Forbidden Subgraph Characterization for 2-Tree Interval p-Graphs Next we use Theorem 2.7 to find a forbidden subgraph list for 2-tree interval p-graphs. Recall that Przulj and Corneil found in [43] that 2-trees PIGs have a large set of forbidden subgraphs, at least 62. For k-trees interval p-graphs the forbidden subgraph list also appears to be prohibitively long, so we restrict our 26

PAGE 41

Figure 2.10: Forbidden subgraphs for 2-trees interval p-graphs. consideration to 2-trees interval p-graphs. Theorem 2.10 A 2-tree G has an interval p-representation if and only if G contains no subgraph isomorphic to Gi, 1 < i < 12 in Figure 2.1 0. Proof: Let G be a 2-tree that has an interval p-representation. By Theorem 2. 7, G is a spiny interior 2-lo bster. Consider the 2-trees G i, 1 < i < 12 in Figure 2.10. The graphs c;-, 1 < i < 10 are not 2-paths, so Gi, 1 < i < 10 are not 2-lobsters. In both G11 and G12, we have x, y, and z as the 2-leaves of and each of which has a different neighborhood in G2-. We use two of these to define e0 and ep and the third vertex is in 82G11 or 82G12, thus Gn and G12 are not spiny interior 2-lobsters. Therefore, G contains no subgraph isomorphic to Assume that G does not have an interval p-representation. By Theorem 2.7, G is not a spiny interior 2-lobster. Let P = (eo, t1 e1 ... tp, ep) be the a longest 2-path in G2-, such that e0 and ep are the neighborhoods of 2-leaves of G1-. It follows from the definition of a spiny interior 2-lobster that either there exists a vertex a E V(G 2-)P or there exists a vertex a E 82G. We will first 27

PAGE 42

consider the case that there is a vertex a E V ( G1-) such that N p (a) c ti, but ei-ll ei =f. Np(a). This a could be in 82G or it could be in V(G2-)P. Thus the only remaining way that G could not be a spiny interior 2-lobster is if there exists a E V(G2-)P such that Np(a) = ei for 1 < i < p-1. Case 1: There is a vertex a E V(G1-) such that Np(a) C ti, but ei_1 ei =f. Np(a). Label the vertices of ti such that t i = ei_1 +x, ti = ei +y, and J V p( a) = ti-z Thus ei-1 = z + y, ei = x + z, and Np(a) = x + y. For ei-l and ei to be defined as such there must be vertices b, c distinct from x, y or z such that ei-l c Np(b) and ei C Np(c). Now the graph induced by the vertices {a,b,c,x,y,z} is a 3-sun, and is a subgraph of G1-. Thus there must be vertices m n, q E V(G) such that either b, z E Nc(m) orb, y E Nc(m) and c, x E Nc(n) o r c, z E Nc(n) andy, a E Nc(q) or x, a E Nc(q). Without loss of generality, we start by adding q such that y, a E Nc(q). Now there are 4 possibilities for adding m and n as illustrated by Hi, 1 < i < 4 in Figure 2.11. One of these graphs Hi, 1 < i < 4 must be a subgraph of Gin this case. The graphs H1 H2 and H 4 are isomorphic to G11 and the graph H3 is isomorphic to G12 Figure 2.11: The four graphs for Case 1 in Theorem 2.10. 28

PAGE 43

Case 2: There exists a vertex a E V ( G2-) P such that N p (a) = ei for 1
PAGE 44

Figure 2.12: Possible forbidden subgraphs for 2-tree interval p-graphs from Case 2 in Theorem 2.10. The graphs G11 and G12 are minimal; that is, the removal of any vertex creates an interval p-graph. Figure 2.13 gives two examples of G12 with a vertex removed and the corresponding interval p-representation. Notice that G12 -cis not a 2-tree, but G12 -e is a 2-tree. a-d f ,_ h ----k c k Figure 2.13: Two examples of G12 without a vertex and the corresponding interval prepresentation. However, graphs Gi, 1 < i < 10 are not minimal in this traditional sense. Each graph contains a vertex v such that the removal of the vertex leaves a graph that still does not have an interval p-representation. Figure 2.14 gives the first five forbidden subgraphs missing one vertex. Each of these still does not have 30

PAGE 45

Figure 2.14: Examples of forbidden subgraphs without a vertex that still contain an ATE. a interval p-representation since the three edges in bold form an ATE in each graph. However, the removal of each of these vertices leaves a subgraph that is not a 2-tree. If we were to remove a 2-leaf from any graph of Gi, 1 < i < 10 the resulting graph would be a spiny interior 2-lobster and hence hav e an inte rval p-representation. Thus they are minimal in the sense that the removal of any vertex creates a subgraph that is either an interval p-graph or is not a 2-tree. Minimality will be of more importance in Chapter 3. 31

PAGE 46

3. 2-tree Probe Interval Graphs In this chapter we build on the structure of the spiny interior k-lobster introduced in the last chapter to characterize 2-tree probe interval graphs. The characterization is then used to show the list of 62 forbidden subgraphs obtained by Przulj and Corneil in [43] is not complete. 3.1 Structure of Probe Interval 2-trees We let k = 2 in all of the definitions introduced in the second chapter. Although spiny interior 2-lobsters characterize the 2-trees that are interval pgraphs, the same is not true for 2-trees that are probe interval graphs. Figure 3.1 gives three forbidden subgraphs for probe interval 2-trees in [43], S25, S13 and S19. Each of Si5, Sfi, and Sf9 are 2-paths. In addition the 2-leaves of Sii and st;; are { x, y, z} and the 2-leaves of s25 are {y, z}' none of which are in 82S13l 8 2 S19, nor 8 2 S25, so all three graphs are spiny interior 2-lobsters. However every PIG is an interval p-graph, so we look for a subset of spiny interior 2-lobsters that characterize 2-tree PIGs. This leads us to more definitions. Fif?ure 3.1: Three spiny interior 2-lobsters that are not probe interval graphs in l43]. Suppose G is a 2-tree such that G2 -is the 2-path (eo, t1,e1,t2, ... tP, ep) We classify the 2-leaves in 81 G as follows: 32

PAGE 47

ate= {v E a1G: Nc(v) c V(G2-)}; 8fG = {v E a1G: Nc(v) V(G2-)}. Since t he non adjacencies of these 2-leaves are of particular importance to us, we label some of the vertices of G2 -as follows: W1(G) = {v E V(G2-): Nc(x) = ti-v for some X E ate, (1 < i < p)} ; W2(G) = {v E V(G2-): Nc(y) = Nc2-(z) + z -v = e i + z v for some y E arG and z E V(G), (1 < i
PAGE 48

Figure 3.2: A spiny interior 2-lobster with the vertices and 3-cliques of G2 -labeled. Definition 3.1 Let G be a spiny interior 2-lobster with G2 -the 2-path ( e0 t1, e1, t2, ... i]J,ep). If the following four conditions all hold then G is a sparse spiny interior 2-lobster (ssi2-lobster). 1. No ti, 1 < i < p, has two vertices in W-W3 2. No ti, 1 < i < p, has two vertices X andy such that X E w-W3 andy E W3'. 3. No ti, 1 < i < p, has two vertices x andy such that x, y E W3'. 4No ti, i E {1,p}, has three vertices x, y, and z such that x, y E W3 and if eo = X + y or ep = X + y then Z E W1 U W2 U W3'. The 2-tree in Figure 3.2 is not an ssi2-lobster since t1 has two vertices in W-W3 w1 and w2 The graphs A1 B and C in Figure 3.3 are sparse spiny interior 2-lobsters. In graph A, at A = {j} and a? A = {a, m, h }; thus W1 = W3 = { d} and W2 = W3 = 0. Because there is only one vertex in W, A is an ssi2-lobster. In graph B, ate = { v} and a? B = {a b, r, t, n }; thus W1 = {h}, W2 = {h}, W3 = {d,f,h}, and W3 = 0. Although t1 has two vertices in W, neither of them are in H '1 U W2 U W3'. No other clique has more than one vertex in W, so B is an ssi2-lobster. In graph C ate= 0 and a?C = 34

PAGE 49

{a,J,g,j,n,q}. Both W1 and W2 are empty and W3 = {d,c,k}. Although there are two vertices f and g such that Nc(f) = Nc2-(b)+ b-c = e0 + b-c and Nc(g) = Nc2-(b) + b-c = e0 + b-c, because both are adjacent to b, the vertex c r/: W3'; hence W3 = { d}. Because W3 contains only one vertex, the third condition on being an ssi2-lobster must hold. Since t1 contains three vertices in W3 we check the fourth condition and notice that e0 = d + c and ep = d + k and in neither case is the third vertex in W1 U W2 U W3'. Thus C is also an ssi2-lobster. In order to prove that ssi2-lobsters are exactly the class of 2-trees that have probe interval representations, first w e need some definitions and lemmas in [ 4 7] and [ 43]. Figure 3.3: Three sparse spiny interior 2-lobsters with the vertices and 3-cliques of G2 -labeled. A collection of sets {X, Y, Z} is an asteroidal collection (AC) if for all x E X, for ally E Y, and for all z E Z, {x,y,z} is an asteroidal triple. Each of these sets X, Y, and Z is called as asteroidal set (AS). The following results in [43] and [47] provide information about the (P, N)-partition of vertices in a PIG. Lemma 3.2 [47] In a PIG at least one vertex of every asteroidal triple must be a non-probe. Corollary 3.3 [43] At least one asteroidal set of an asteroidal collection of a 35

PAGE 50

PIG G must consist entirely of non-probes. Thus at least one asteroidal set of a PIG must be an independent set. Lemma 3.4 [43] In every asteroidal triple of a PIG G there must exist a non probe asteroidal triple vertex u such that there exists a path between the other two asteroidal triple vertices that avoids N ( u) and has a non-probe internal vertex. Corollary 3.5 [43] There exists only one (P, N)-partition of vertices of a 3-sun up to isomorphism. Figure 3.8 gives the (P, N)-partition of the 3-sun from Corollary 3.5. We now prove a lemma that says that the vertices of W1 must be non-probes. Lemma 3.6 Let G be a spiny interior 2-lobster with a probe interval representation such that G2 -= (eo, tl, el, t2, ... 'tp, ep) Any Wx E W1 must be a non-probe. Proof: Let G be a spiny interior 2-lobster with a probe interval representation such that G2 -= (eo, t1, e1, t2, ... tp, ep), and let X E 8}G such that Nc(x) = ti-Wx. If i > 2 then let a E ti-2-ei-2, and let bE ti-lei-I If i = 2 let a be a 2-leaf of G1 -such that Nc1-(a) = e0 and let b E t 1 e 1 If i = 1 then let b beak-leaf of G1 -such that Nc1-(b) = e0 and let a E B?G such that N c (a) c ( e0 + b). If i < p -1 let c E ti+ 1 -ei and let d E ti+2 -ei+ I If i = p -1 then let d be a 2-leaf of G1 -such that Nc1-(d) = ep, and let c E tpep-1 If i = p then let c be a 2-leaf of G1 -such that Nc1-(c) = ep, and let d E 8tG such that N c (d) C ( ep + c). Let r E ti ei Let s E ti ei-1 Let X = { x}, y = {a, b}, and Z = { c, d}. We claim that {X, Y, Z} is an AC. The path abwxcd 36

PAGE 51

avoids Nc(x). The path abrx avoids Nc(c) and Nc(d). The path dcsx avoids Nc(a) and Nc(b). By Corollary 3.3, since abE E(G) and cd E E(G), the AS X = { x} must contain all non-probes. Now consider the subgraph H induced by the vertices {b, c, r, s, x, wx}, which is isomorphic to the 3-sun. By Corollary 3.5, since x must be a non-probe, Wx must also be a non-probe. Figure 3.4: Two labeled examples for Lemrpa 3.6. Figure 3.4 gives two ssi2-lobsters that are labeled as in the proof of Lemma 3.6. In order to prove a similar statement about vertices of W2 we must first provide a lemma about the probes and non-probes of an induced subgraph that is common in 2-trees. Lemma 3. 7 There are exactly three (P, N)-partitions of vertices of the PIG Q in Figure 3. 8 up to isomorphism. Proof: Label the vertices of the PIG Q as in the Figure 3.8; The vertices {a,g,h} form an AT, since the path acg avoids NQ(h), the path abdh avoids NQ(g), and the path hdfg avoids NQ(a). By Lemma 3.4, we know there must exist a non-probe AT vertex u such that there exists a path between the other two AT vertices that avoids N(u) and has a non-probe internal vertex. First let us assume that h is the AT vertex with this property. The only vertex in the 37

PAGE 52

neighborhood of his d, so the internal vertex that must also be a non-probe can be either b, .f, or c. Assume that b is the non-probe vertex, and thus a and c must be probes. In a probe interval representation of G, Ih and Ic must not overlap, since they are not adjacent and c E P. Furthermore, dis adjacent to both hand c. Thus without loss of generality, let rh < lc and hence ld < rh and r d > lc. Now both b and .fare adjacent to d but not adjacent to one another or to h. Let us assume that f is a probe, so It and h must not overlap. If It C Id, then I9 n Id -=/:0, which is a contradiction since d is a probe and d and g are not adjacent. Thus since f is not adjacent to h, we must have that rb < lt. However, this forces Ia n Id -=/:0, since a is adjacent to both c and b, which is a contradiction (see Figure 3.5). h========= c----------d b ? fa--. Figure 3.5: An example for the proof of Lemma 3.7 where any placement of the interval for a produces a contradiction. Let us assume then that f is a non-probe and that rb < r f Since a and g are adjacent to c and not to d, it must be that r d < la and r d < l9 Thus we have that Ian It -=f. 0, which is a contradiction (see Figure 3.6). We get a similar contradiction iff is a non-probe and r t < rb, so if hE N then b tJ. N. c---------h======:= d b===::==== !====?= a-Figure 3.6: An example for the of Lemma 3.7 where any placement of the interval for a produces a contradiction. 38

PAGE 53

We get similar arguments and contradictions if we assume that h and f must be the non-probes that satisfy Lemma 3.4, so it is also true that if hE N, then f tJ_ N. Hence it must be the case that N = {h,c} and P = {a,b,d,j,g} (see Q' in Figure 3.8). With this (P, N)-partition and the interval assignment Ic = (0, 6), Ia = (0, 2), h = (1, 2.5), Id = (2, 4), If = (3.5, 5), I9 = ( 4, 6), Ih = (2.5, 3.5), we can see that this is a probe interval representation. Now let us start with the AT non-probe vertex being a, which forces b, c E P. By Lemma 3.4, we know that either d or f must be a non-probe. Assume that f is a non-probe, which means that d and g are probes. We also know from above that h must be a probe iff is a non-probe, and thus the only vertices that are non-probes are a and f. Since NQ(a) NQ(f) and NQ(f) NQ(a), neither interval can be contained in the other. We know that Ia and If must overlap, or else the probe interval representation would be an interval representation, which is a contradiction since G contains an AT. Without lo$S of generality, let la < lf. Since b E NQ(a), but b tJ_ NQ(f), we know that rb < lf. However, d is adjacent to both b and j, so ld < rb and rd > lf. This forces Ian Id -=/=-0, which is a contradiction (see Figure 3.7). Therefore, d must be the non-probe. Hence either N = {a,d}, P = {b,c,j,h,g} or N = {a,d,g}, P = {b,c,j,h}(see Q in Figure 3.8). With either (P, N)-partition and the interval assignment Ic = (2, 6), Ia = (2, 3), h = (2, 3), Id = (1, 4), If = (3, 5), I9 = (4, 6), Ih = (0, 2), we can see that both are probe interval representations. If we start by assuming that the AT non-probe vertex is g, we find a similar argument to the one above. However, these (P, N)-partitions are isomorphic to the ones above. Thus there are exactly three (P, N)-partitions of vertices of PIG 39

PAGE 54

b d Figure 3.7: An example for the proof of Lemma 3.7, where the placement of the interval ford forces an adjacency between a and d, which is a contradiction. Q in Figure 3.8 up to isomorphism. g 3-sun Figure 3.8: Graphs Q and the 3-sun with their possible (P, N)-partitions up to isomorphism. The white vertices are non-probes, black are probes, and the grey can be either a probe or non:..probe. Now we use Lemma 3.7 to prove a lemma that says that the vertices of W2 must be nonprobes. Lemma 3.8 Let G be a spiny interior 2-lobster with a probe interval representation such that G2 -= (eo, ti, el, t2, ... 'tp, ep) Any Wy E W2 must be a non-probe. Proof: Let G be a spiny interior 2-lobster with a probe interval rep resentation such that G2 -= (eo, t1, e1, t2, ... tp, ep) Let y E a; such that . : Nc2-(y) = ei-Wy for Wy E W2(G); from the definition of W2 i #-O,p. If i > 2 let a E ti_2 -ei-2 and let b E til ei-l If i = 2 let a be a 2-leaf of G1 -such that N01-(a) = e0 and let b E t 1 e 1 If i = 1 let b be a 2-leaf of G1 -such 40

PAGE 55

that Nc1-(b) =eo, and let a E BrG such that Nc(a) c (eo+ b). If i < p-2 let c E ti+2-ei+1, and let dE ti+3 -ei+2 If i = p-2 let d be a 2-leaf of G1 -such that Nc1-(d)= ep, and let c E tp-ep_1 If i = p-llet c be a 2-leaf of G1 -such that Nc1-(c) = ep, and let dE BrG such that Nc(d) C (ep +c). Lets E ti-ei. Let r E ti+1 -ei. Lastly, let Nc(y) = ei + u-Wy. This leads us to three cases. Either both b, c tf:. Nc(wy), exactly one of b or c tf:. Nc(wy), orb, c E Nc(wy) Case 1: The vertices b, c tf:. Nc(wy) If both b, c tf:. Nc(wy), then the graph induced by vertices {b, s, wy, r, c, u, y} is a NL 7. By [ 4 7] we know that the vertex of degree 3 in a NL 7 must be a non-probe Therefore, wy is a non-probe. Case 2: Exactly one of b or c E Nc(wy) Without loss of generality, assume that bE Nc(wy) and c tf:. Nc(wy) Label vertex v such that v E ti, but v tf:. ei_1 which implies that v E ei. Let Y = {y } X= {a, b}, and Z = {c, d}, and we claim that {X, Y, Z} is an AC. The path abwyrcd avoids Nc(y); abwyuy avoids Nc(c) and Nc(d); and dcvy avoids Nc(b) and Nc(a). Since abE E(G) and cd E E(G), the AS Y = {y} must contain all non-probes by Corollary 3.3. We know that y tf:. Nc(r) since r tf:. ei. We know that u, y, r, c, v tf:. Nc(b) because b tf:. ei_1 Thus the graph H induced by the vertices {b, wy, r, c, v, u y} is isomorphic to Q in Figure 3.8, with Wy ""' d and y ""'a. By Lemma 3.7 and the fact that yEN, wy is a non-probe. Case 3: The vertices b, c E Nc(wy) Let ei = wy + J, and let Y = {y}, X= {a,b}, and Z = {c,d}; we claim {X, Y, Z} is an AC. The path abwycd avoids Nc(y); absfy avoids Nc(c) and Nc(d); and dcr fy avoids Nc(a) and Nc(b) Since ab E E(G) and cd E E(G), 41

PAGE 56

the AS Y = {y} must contain all non-probes by Corollary 3.3. Now consider the subgraph H induced by the vertices {b, s f y wy, r c}, which is isomorphic to Q' in Figure 3.8 with Wy rv c and y rv h. By Lemma 3. 7 and the fact that yEN, the vertex Wy is a non-probe. Figure 3.9: Examples for Cases 1 2 and 3 in the proof of Lemma 3.8 We now find a new forbidden subgraph family not given in [43]. Although we will speak more of forbidden subgraphs in the next section we prove that this fa1nily does not have a probe interval representation now so w e can us e it in the proof of the main theorem. Lemma 3.9 The family of graphs H i, i E z + ar e not prob e inte r val graphs. Proof: Label H i, i E z+ as in Figure 3.10. The subgraph induced b y the vertices { wy, Wx, r g y f h} is an NL 7 which forces Wy to be a non-probe. Now consider subgraph induced by the vertices {r, b x, d1 Wx, wy} which is a 3-sun with wy as a non-probe. By Corollary 3.5 b must also be a non-probe Lastly, let X= { x } Y = {r}, and Z = {g y}. We claim that {X, Y ,Z} is an AC. The path rwx wygy avoids Nc(x), the path rbx avoids N c (g) and Nc(y), and the path x d1wygy avoids Nc(r). By Lemma 3.3 and the fact that g and y are adjacent, either r or x must be a non-probe. However we already said 42

PAGE 57

that b must be a non-probe, and both r and x are adjacent to b, which is a contradiction. Therefore, no Hi, i E z+ is a probe interval graph. Figure 3.10: Hi, i E z+ Corollary 3.10 The graphS in Figure 3.15 is not a PIG. Proof: The only vertices used in the proof that Hi, i E z+ are not PIGs are inS. Therefore, Sis not a PIG. 3.2 Probe Interval 2-tree Characterization Now that we have established much of the structure of a probe interval 2-tree, we proceed with the main result of this chapter. Lemma 3.11 Let G be a 2-tree. If G is an ssi2-lobster then G is a PIG. Proof: Suppose G is a sparse spiny interior 2-lobster such that G2 (e0, t1 e 1 ... tp, ep) By the definition of e0 and ep, we know that both contain at least one vertex in W3 If eo contains exactly one vertex in W3 label it w. Similarly if ep contains exactly one vertex in W3 then label it a. If both vertices of e0 (or ep) are in W3 -(W1 u W2 .u W3'), then label the vertex in e0 and e1 as w (or ep and ep-l as a). If not then by conditions 1, 2 and 3 of the definition of an ssi2-lobster' both vertices of eo (and ep) are not in the set W1 u W2 u W3'. 43

PAGE 58

Thus choose a vertex w E e0 such that w E W3 -(W1 U W2 U W3'), and choose a vertex a E ep such that a E W3 -(W1 U W2 U W3'). Let y E 8i such that Nc(Y) = Nc1(z) + zw = e0 + zw. Label e0 = w + x, and notice that Ncl-(z) = { w, X} and y E Nc(x). Similarly let d E 8i such that Nc(d) = Nc1-(c) + c-a = ep + c-a, and label ep = a+ b. Now we let e-2 = Y + z, t-1 = x + y + z, e-1 = z + x, to = z + w + x, tp+ 1 = a+ b + c, ep+1 = b + c, tp+ 2 = b + c + d, and ep+ 2 = c +d. Make each vertex v E W1 U W2 U W3 U (W3 -{ w, a}) and each vertex z E 81 -{y, d} a non-probe. If w or a is in W1 U W2 U W3 then it will be a non-probe; however, if it is just in W3 -W3 then it will be a probe. By conditions 1, 2, 3 of the definition of an ssi2-lobster, no clique contains two vertices from W1 u W2 u W3'' and from condition 4 if a clique contains a vertex from (W3 { w, a}) then it does not contain a vertex from W1 u W2 U W3'. Hence no clique in G2 -contains two non-probe vertices; therefore from the definition of a 2-tree, no two non-probe vertices of G2 -are adjacent. Furthermore no two vertices of 81 are adjacent, and if a vertex of 81 is adjacent to a vertex of W1 U W2 U W3 U (W3 -{ w, a}) then there is a clique with two vertices in W1 u W2 u W3 and G is not an ssi2-lobster. Thus this (P, N)-partition has no adjacencies between non-probe vertices. Now we must assign intervals using this (P, N)-partition. Let G2-* = (e-2, t-1, e_ll to, eo, t1, e1, ... tP, ep, tp+1, ep+1, tp+2, ep+2), and for each v E G2-* assign an ordered pair ( m, n) such that tm is the first clique that contains v and tn is the last. Assign the interval Ivm,n = ( m n + to each v E G2-*. Notice that the interval ( i + i + 1) contains only the vertices from ei, 44

PAGE 59

and the interval ( i, i + contains only the vertices from ti. For each ei E G2 -*, let Mi = {v E V(G): v : V(G2-*) and N02-.. (v) = ei} and enurnerate the vertices of Mi as X(i,1) to X(i,IMil). Assign the interval lx(i,j) = ( i + + i + + 21iti1 ) to each X(i,j) E A{ for all Mi. For each X(i,j) E Mi let Mi,j = { v E or : X(i,j) E N( v)} and enumerate the vertices of M(i,J) as Y(i,j,1 ) to Y(i,J,iM(i,j) I). Assign the interval I -(' .! --i=.!_ 1 _j_) h M Y(i,j,k) z + 2 + 2 1Mil, z + 2 + 21Mil to eac Y(i,j,k) E (i,j). Recall that all these vertices are non-probes, so their intersecting intervals do not represent adjacencies. Since the spiny interior 2-lobster is sparse, each Y(i,J,k) E M(i,j) in not adjacent to a distinct vertex of ei, which is a non-probe. Therefore, no adjacency results between each Y(i,j,k) and its non-adjace,ncy in ei. For each ti, 1 < i < p let Q i = { v E of : N c ( v) C ti}, and let Qo = { v E or : Na(v) = z + w} and Qp+1 = {v E or: Nc(v) =a+ c}. Enumerate the vertices of Qi, 0 < i < p + 1 as C(i,1 ) to C(i,IQil). Assign the interval Ic(i,j) = ( i, i + Recall that all these vertices are non-probes, so their intersecting intervals do not result in an adjacency. Since G is an ssi2-lobster, the vertex wi E ti such that wi : N02.. (c(i,j)) is the same for all j, and wi is a non-probe since it is in W1 Therefore no adjacency results between each C(i,j) and wi for all j. Thus G has a probe interval representation. Figure 3.11 gives an example of an ssi2-lobster with the vertices labeled as in Lemma 3.11. Both X and w are in W3 and neither is in W1 u W2 u W3'' thus the vertex in both e0 and e1 was chosen as w. This is because the other vertex X is then forced to be a non-probe, even though it is not in W1 U W2 U W3'. Since it is only adjacent tow on G2 -and w is a probe, we avoid two non-probe vertices in the same clique. Given w's labeling, X(-1 1 ) could have been labeled 45

PAGE 60

Figure 3.11: A ssi2-lobster with v e rtices labeled as in Lemma 3.11 as y. Notice on the other end of the 2-tree that a is the only vertex in e6 that is in W3 thus it was labeled as such. Again the choice of the vertex that was labeled d was arbitrary. Figure 3.12 gives the probe interval assignment for Figure 3.11. The representation has each clique ti from G2-* cover the interval ( i, i + In this section we can add intervals for 2-leaves of Gin 8{ whose neighborhood is a subset of t i Since there is at most one vertex which is not adjacent to these vertices it be comes a non-probe. Likewise the representation has each clique e i covering the interval ( i + i + 1). We can partition this interval for each vertex that is adj a cent to ei but is not on G2-*. Next we add intervals for vertic es that are 2-leav e s of G and whose neighborhood is a subset of the vertices in this area. How e v e r we must make the 2-leaf and its non-adjacency on G2 -a non-probe. This is the intuition for the ssi2-lobster: you can' t have two of these non-adjacenc ie s for 2-leaves in one clique because they must be non-probes (although we have 46

PAGE 61

more flexibility at the ends of the 2-path G2-). =Jf!.l.li =Cro. l ) '16.2)= -Xf/.1) --"t(l.l) Ci6.1)= -x(6.1J Y-w \.j c z '1 a d-X '2 v b I I I I I I I I I I I -1 0 1 2 3 4 5 6 7 8 Figure 3.12: The probe interval representation for Figure 3.11 Theorem 3.12 Let G be a 2-tree. G is a probe interval graph if and only if it is a ssi2-lobster. Proof: Let G be a 2-tree that has a probe interval representation. Assmne that it is not a ssi2-lobster. Thus it is either not a spiny interior 2-lobster or it is a spiny interior 2-lobster that is not sparse. If it is not a spiny interior 2-lobster then by Theorem 2.7 it is not an interval p-graph. Since probe inte rval graphs are contained in interval p-graphs, it is not a probe interval graph. Therefore, we assume that G is a spiny interior 2-lobster that is not sparse. Let G2 -= (eo, tb el, ... tp, ep). Either there is a ti with two vertices Wx and Wy in W-W3 there is a ti with two vertices Wx and Wy such that Wx E W-W3 and Wy E W3', there is a ti with two vertices Wx and Wy such that Wx, Wy E W3 or there is a ti, i E {1,p}, with three vertices Wx, Wy, and Wz such that Wx, Wz E W3 1 2 3' and 1f e0 = Wx + Wz or ep = Wx + Wz then Wy E W U W U W Case 1: There is a ti with two vertices Wx and Wy in w -W3 47

PAGE 62

In this case, Wx and Wy are non-probes by Lem1nas 3.6 and 3.8, which is a contradiction since Wx wy E E (G). Case 2: There is a ti with two vertices Wx and wy such that Wx E W-W3 d 3' an wy E W Without loss of generality, let Nc(Y) = Nc2(z) + z-wy = ep + z -wy and Nc(s) = Nc2-(r)+r-wy = ep+r-wy for y,s E ofG and distinct z,r E V(G). Since Wx and Wy are both inti, Wy E e 1 i < j < p. If Wy ei_ 1 there is a v ertex g such that ei-1 C Nc(g) and Wy Nc(g). Let ei_ 1 = W x +h. The subgraph H induced by the vertices { Wy, h, g, y, s, z, r} is an NL 7 with wythe vertex of degree 3 and hence is forced to be a non-probe (see A1 in Figure 3.13). By Lemmas 3.6 and 3.8, Wx is a non-probe, which is a contradiction since WxWy E E(G). Therefore, let us assume that wy E ei_1 Since wy is in both ei_1 and ei, this precludes Wx from being in W1 since vertices in this set must be in two consecutive e1 sets. This means that Wx + Wy = ei for i -=1-0 and i -=/:p. Let ep = Wx + f and bE ei_1 and consider the subgraph H induced be the vertices { Wy, J, z, y, r, s, b}' which is isomorphic to Q in Figure 3.8 with Wy rv d (see A2 in Figure 3.13). Since wxb E E(G), b must be a probe. Thus by Lemma 3.7, Wy must be a non-probe and we again get a contradiction. Case 3: There is a ti with two vertices Wx and Wy such that Wx, Wy E W3'. Let Nc(Y) = Nc2-(z)+z-wY = ei+z-wy and Nc(s) = Nc2-(r)+r-wY = ei + r-Wy for y, s E oiG and distinct z, r E V(G), (i = 0 or i = p), and Nc(x) = Nc2-(v)+v-wx = ei+v-wx and Nc(c) = Nc2-(d)+d-wx = ei+d-wx for x, c E ofG and distinct v, d E V(G), (i = 0 or i = p). First consider the case that Wx + wy -=1-e0 nor ew Then the subgraph H induced by the 48

PAGE 63

Figure 3.13: Labeled examples for Case 2 in the proof of Theorem 3.12. vertices { Wy, y, z, s, r, Wx, v} is isomorphic to an NL 7 with wythe vertex of degre e 3. Similarly, the subgraph H induced by the vertices { Wx, v, d, x, c, wy, z} is isomorphic to an NL7 with Wx the vertex of degree 3 (see A3 in Figure 3.14). These two induced subgraphs force both Wx and Wy to be non-probes, which is a contradiction since they are adjacent. Therefore, let us assume without loss of generality that Wx + Wy = ep and that Wx :. ep-l Let a E tp such that a=/= Wx, wy, and notice that there exists a vertex b such that a, Wy E Na(b), but b :. Na(wx) Thus the subgraph H induced by the vertices { Wx, v, x, c, d, a, b} is an NL 7 with Wx the vertex of degree 3 and hence must be a non-probe. If Nc1-(z) = Nc1-(r) = e0 then e0 = wy + f and the subgraph H induced by the vertices { wy, z, y, r, s, d, f} is isomorphic to Q in Figure 3.8 (see A4 in Figure 3.14). Since dE Na(wx) and Wx is a non-probe, d must be a probe. By Lemma 3. 7 this forces Wy to be a non-probe, which is again a contradiction. If Nc1-(z) = Nat (r) eP, then let g be a vertex such that g :. tp and g E Na(b). We know such a vertex exists since G2 -has at least one ti The subgraph H induced by the vertices { wy, y z, s, r, Wx, b} is isomorphic to Q in 49

PAGE 64

Figure 3.8. By Lernma 3.7 and the fact that Wx E JV, Wx and b must be non-probes. If g E Nc(wy), consider the subgraph H induced by the vertices { Wy, y, z, s, r, Wx, g }, which is again isomorphic to Q in Figure 3.8. Hence .by Lemma 3.7, Wx and g 1nust be non-probes, but this is a contradiction since bg E E(G). If g tt Nc(wy) consider the subgraph H induced by the vertices { wy, y, z, s, r, Wx, b, g }. We claim the set {g y, s} is an AT (see A5 in Figure 3.14). The path gbwyrs avoids Nc(y); the path gbwyzy avoids Nc(s); and the path SWxY avoids Nc(g). By Lemma 3.4, we know that one of the vertices in the AT must be a non-probe such that there exists a path between the other two AT-vertices that avoids the neighborhood of the non-probe and has a non-probe internal vertex. Since g is adjacent to b which is a non-probe, the non-probe AT vertex must be either y or s. However, both of thes e vertices are adjacent to wx, which has already been shown to be a non-probe, and thus we get a contradiction. c Figure 3.14: Labeled examples for Case 3 in the proof of Theorem 3.12. Case 4: There is a ti,i E {l,p}, with three vertices Wx,wy, and Wz such 1 2 w3' that Wx,Wz E W3 and if eo= W x+Wz or e p = Wx+Wz then Wy E W UW U 50

PAGE 65

Without loss of generality, let ep = Wx + Wz, ep_1 = W : c + Wy and Nc(x) = Nc2-(v)+v-wx = ep+v-wx and Nc(z) = Nc2-(d)+d-wz = ep+d-wz for x, z E BiG and v, dE V(G). We first consider the case that v =d. If y E W3', then let Nc(Y) = Nc2-(c)+c-wy = e0+c-wy and Nc(s) = Nc'l -(r)+r-wy = eo+ rWy for y, s E BiG and distinct c, r E V(G). The subgraph induced by all the vertices of G2 -and { r, s, c, y, v, x, z} is isomorphic to Hi in Figure 3.10 for some i E z+, and hence by Lemma 3.17 G is not a PIG. Now let us assume that wy E W1 U W2 and recall that by Lemmas 3.6 and 3.8, Wy must be a non-probe. The graph H induced by the vertices { Wy, Wz, Wx, v, z, x} is isomorphic to the 3-sun. With wy already a non-probe, we know that v must also be a non-probe by Corollary 3.5. Since wy is in W1 u W2 the clique tp_1 must exist on G2-, so without loss of generality we let tp-1 = a+ Wy + Wx We claim that {a, z, x} is an asteroidal triple. The path awxz avoids Nc(x); the path awywzx avoids Nc(z); and the path zvx avoids Nc(a). We know that one of the vertices in the AT must be a non-probe, but since a is adjacent to wy, the non-probe must be either z or x. However, both z and x are adjacent to v, which has already been shown to be a non-probe, and we have a contradiction. Now we consider the case that v =/= d. If wy E W3', then subgraph H induced by the vertices {wy,c,y,r,s,wz,X} is isomorphic to NL7 with Wythe vertex of degree 3, hence Wy must be a non-probe. By Lemmas 3.6 and 3.8, if Wy E W1 u W2 then Wy is a non-probe. In either case, there is a vertex r that is either a 2-leaf of G1 -or in tp_1 such that Wx, wy E Nc(r). Now consider the subgraph H induced by the vertices { Wx, wy, Wz, v, d, x, z, r }, which is isomorphic 51

PAGE 66

to G1 in Figure 3.15. The graph G 1 -v is isomorphic to Q in Figure 3.8. By Lemma 3.7, Wy cannot be a non-probe, which is a contradiction. Since in every case we get a contradiction if G is not a sparse spiny interior 2-lobster, then it is not a PIG. Figure 3.15: The graphs H1 S and G1 Now let G be a ssi2-lobster. By Lemma 3.11 G has a probe interval r epre sentation. 3.3 Forbidden Subgraphs for Probe Interval 2-trees Since this research was motivated in part by the 62 forbidden subgraphs found by Przulj and Corneil in [43], we now turn our atte ntion to forbidden subgraphs for probe interval 2-trees. We have already given one new family of forbidden subgraphs for 2-tree PIGS in Figure 3.10. If any v ertex is d e leted from the infinite family, the graph ceases to be a 2-tree or has a prob e int e rval representation. However, only one of the the graphs is minimal. Proposition 3.13 The graph H1 is a minimal forbidden induced subgraph for 2-tree PIGs. 52

PAGE 67

Proof: Label H1 as in Figure 3.15 The removal of any 2-leaf, {r, x, h, y,} results in a ssi2-lobster; hence by Theorem 3.12 it has a probe interval representation. The removal of Wx or Wy results in a graph with no cycles larger than 3 and no AT, so it is an interval graph, which is also a probe interval graph. The removal of g is isomorphic to the removaL of f. The removal of {g, b, d1 } has a probe interval representation as illustrated in Figure 3.16. Figure 3.16: Three probe interval representations for H1 minus a vertex. The graphs Hi, i E z+ -{ 1} are not minimal, since removing all di except d1 results in the graphS in Figure 3.15, and by Corollary 3.10, Sis not a PIG. However, there is no sub graph isomorphic to any Hi, i E z+ -{ 1} in the 62 forbidden 2-trees in (43]. To see this, we have listed the degree sequences for the 62 forbidden subgraphs in the table below. It is easy to check that none of the Hi, i E z+ -{1} have the same degree sequence as the graphs listed in the table below. For example; the degree sequences for the first four Hi are: {2,2,2,2,3,3,4,4,5,5,6}, {2,2,2,2,3, 3 ,3,4, 4 5 6 ,6}, and {2, 2, 2, 2, 3, 3, 3, 3 4, 4, 5, 6 7}. Using the characterization of probe interval 2-trees being ssi2-lobsters, we can find more forbidden subgraphs that are not given in the original 62 in (43]. 53

PAGE 68

s1 {2,2,2,2,3,3,3,4,5,6} st7 {2,2,2,2,3,3,3,3,3,4,4,4,5,10} s2 {2,2,2,2,3,3,3,5, 5,5} Sf7 {2,2,2,2,3,3,3,4, 5,6} s3 {2,2,2,3,3,4,4,4,5,6} {2,2,2,2,3,3,3,3,3,3,3,4,4,4,5,12} s4 {2,2,2,3,3,3,3,4,4,5, 7} Sf a {2,2,2,2,3,3,3,3,5,6,7} S5 {2,2,2,3,3,3,3,3,3,6,8} Sfs {2,2,2,2,3,3,3,3,4,5,6,7} s6 {2,2,2,3,3,3,3,3,4,6,7} {2,2,2,2,3,3,3,3,3,4,5,6,8} s7 {2,2,2,3,3,3,3,3,4,5,8} Sf a {2,2,2,2,3,3,3,3,3,3,4,5,6,9} Sa {2,2,2, 3 ,3,3,3,3,3,3,4,4,9} s19 {2,2,2,2,3,3,4,4,4,6,6} slO {2,2,2,3,3,3,3,4,4,4,8} S2o {2,2,2,2,3,3,3,3,4,5,9} Su {2,2,2,3,3,3,4,4,4,4,7} s21 {2,2 ,2,2,3,3,3,4,4,5,8} sl2 {2,2,2,3,3,3,3,4,4,6,6} s22 {2,2, 2 ,2,3,3,3,3,4,7,7} s13 {2,2,2,2,3,3,3,4,5,6,6} s23 {2,2,2, 2 ,3,3,3,4,4,6,7} S}4 {2,2,2,2,3,3,3,4,5,8} s24 {2,2,2,2,3,3,4,4,4,5,7} Sf4 {2,2,2,2,3,3,3,4,4,4,9} s25 {2,2,2,2,3,3,5,5,5,5} sr4 {2,2,2,2,3,3,3,3,4,4,4,10} {2,2,2,2,3,3,4,4, 6,6} st4 {2,2,2,2,3,3,3,3,3,4,4,4,11} Si6 {2, 2 2 2 ,3,3,4,4,4, 5,7} Sf4 {2,2,2,2,3,3,3,3,3,3,4,4,4,12} {2,2,2,2,3,3,3,4,4,4,5,8} {2,2,2,2,3,3,3,3,3,3,3,4,4,4,13} {2, 2 ,2,2,3,3,3,3,4,4,4,5,9} S}5 {2,2,2,2,3,3,3,5, 5,7} {2,2,2,2,3, 3 3 ,3,3,4,4,4,5,10} Sf5 {2,2,2,2,3,3,3,4,4, 5,8} {2,2,2,2,3,3,4,5,5,6} {2,2,2,2,3,3,3,3,4,4,5,9} Si1 {2,2 ,2,2,3,3,4,4,4,5,7} st5 {2 ,2,2,2,3,3,3,3,3,4,4,5,10} {2,2 ,2,2,3,3,3,4,4,4,5,8} s}6 {2,2,2,2,3,3,3,3,4,7,7} {2,2,2,2,3,3,3,3,4,4,4,5,9} Sf6 {2,2,2,2,3,3,3,3,4,4, 6,8} {2, 2 ,2,2,3,3,3,3,3,4,4,4,5,10} {2,2,2,2,3,3,3,3,3,4,4,6,9} SJs {2,2 2 ,2,3,4,4,4,5,6} st6 {2,2,2,2,3,3,3,3,3,3,4,4,6,10} Sis {2,2,2,2,3,4,4,4,4,5,6} Sf6 {2,2,2,2,3,3,3,3,3,3,3,4,4,6,11} {2,2,2,2,3,3,4,4,4,4,5,6} {2,2,2, 2 ,3,3,3,3,3,3,3,3,4,4,6,12} {2,2,2,2,3,3,3,4,4,4,4,5 ,8} S}7 {2,2,2,2,3,3,3,4,4,6,7} s29 {2,2,2,2,3,4,4,4, 5,6} Sf7 {2,2,2,2,3,3,3,4,4,4,5,8} NL10 {1,1,1,2,2,2,2,2,2,3} sr7 {2,2, 2 2 ,3,3,3,3,4,4,4,5,9} H10 {1, 1 ,1,1,2,2,2,2,3,3} Proposition 3.14 The graphs N1 though N6 are forbidden subgraphs for probe interval 2-tress that are not isomorphic to the any of the 62 graphs in {43]. 54

PAGE 69

Figure 3.17: The graphs N1 through N6 are not probe interval 2-trees. Proof: In each 2-tree Ni 1 < i < 6, t1 has two vertices in W2 Thus they are not ssi2-lobsters and do not have a probe interval representations. The degree sequences of Ni, 1 < i < 6 are: {2, 2, 2, 2, 3,3, 3, 3, 4, 4, 7, 7}, {2, 2, 2, 2, 3, 3 '3, 3, 3, 3, 6, 10}, {2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 6, 9}, {2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 8, 8}, {2, 2, 2, 2, 3, 3, 3, 3, 3, 4, 7, 8}, {2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 6, 8}, respectively. It is easy to check using the table of the degree sequences of the 62 forbidden subgraphs in [43) above that the only degree sequences that are the same are those of N6 and Si6 Let us assume for contradiction that these two 2ttees are isomorphic. Both of these graphs have exactly one vertex of degree 6, vertices a and z in Figure 3.18. Hence these vertices must map to one another in an isomorphism. However, the vertex a E V(Si6 ) has three neighbors of degree 3, vertices d, e, and fin Figure 3.18, and vertex z E V(N6 ) only has two neighbors of degree 3, vertices x and u in Figure 3.18. This is a contradiction, so N6 and Si6 are not isomorphic, and Ni, 1 < i < 6, are not isomorphic to any of the 62 graphs in [43). Although the graphs N1 through N6 have no induced subgraph isomorphic to an already known forbidden 2-tree PIG, they are not minimal in the traditional sense. For example, in Figure 3.19 N1 -x is not a PIG, so N1 is not minimal. 55

PAGE 70

Figure 3.18: The graphs 8i6 and N6 are not isomorphic. However, N1-xis not a 2-tree or a tree, which brings us back to the discussion about minimality at the end of the last chapter. If you remove a vertex from the graphs N1 through N6 either they cease to be 2-trees or they have probe interval presentations. For example, in Figure 3.19 N1 -y is an ssi2-lobster, and thus has a probe interval representation. Figure 3.19: The graph N1 and two induced subgraphs of N1 one a PIG and one not a PIG. In [43] 83 through 812 are isomorphic to G1 to G10 in the last chapter, and thus are not minimal. However, Przulj and Corneil only eliminated 89 from the count of 62 because it contains an NL10 (see Figure 1.1). They say their intent is to find forbidden 2-tree PIGs that do not contain forbidden tree PIGs as induced subgraphs, which is why they include H10 and NL10 in the count to 62. However, later in [43] infinite families of forbidden subgraphs are reduced to finite families by throwing out the graphs that are not mini1nal. Thus the 56

PAGE 71

list of 62 is a combination of minimal and non-minimal forbidden subgraphs for probe interval 2-trees. To stay consistent we add to their list H1 since it is a minimal member of an infinite family and N1 to N6 since it is a finite family. This brings us to our final proposition of this chapter. Proposition 3.15 There exist at least 69 graphs in the forbidden induced sub graph characterization for 2-tree PIGs. 57

PAGE 72

4. List-distinguishing Dihedral Graphs In this chapter, we begin investigations into the list-distinguishing number of a graph. We start by giving a list-distinguishing Brooks-type theorem. Then we prove that Dt.( G) = D( G) for all graphs that realize the dihedral group. One interesting and useful consequence of this is that we d etermine precisely those graphs that realize Dn and have (traditional) distinguishing number 3. 4.1 Brooks-type Theorem Theorem 4.1, known as Brooks' Theorem, gives a bound on the chromatic number of a graph based on the maximum degree of the graph. In this section we give a similar bound for the list-distinguishing number of a graph also based on the maximum degree of the graph. Theorem 4.1 ([10]) If G is a connected graph other than a complete graph or an odd cycle, then x( G) < Brooks-type theorems for the (traditional) distinguishing number were given independently by Klavzar, Wong, and Zhu [36] and Collins and Trenk [19]. We give the result as stated by Klavzar, Wong, and Zhu. Theorem 4.2 ([36]) Let G be a connected graph. Then D(G) < unless G is either Kn, n > 1, Kn,n, n > 1, orCs. In these cases D(G) 1. The proof of Theorem 4.2 uses the following lemma, which we will use as well. 58

PAGE 73

Lemma 4.3 ( [36)) Suppose ( G, R ) is a connected vertex colored graph such that R( v) is the color for v E V (G). Let every vertex of the set X C V (G) be fixed by every automorphism of (G, e). Let x EX and setS= Nc(x) \X. If R(u) =/= R(v) for any pair of distinct vertices u and v in S then every vertex of S is fixed by every automorphism of ( G, e). We are able to modify the approach from [36) to give a Brooks-type theorem for list-distinguishing colorings. Interestingly, we are able to show that the traditional distinguishing problem is precisely what prevents the exceptional graphs Kn, Kn,n and C5 from being Proposition 4.4 Let G be a connected graph and let = { L( v)} be an assignment of lists of size to V(G). Then G can be -distinguished unless G is one of Kn, Kn,n, or C5 and I U L( v) I = In these e xceptional cases, G can be colored from any assignment of lists of length + 1. Proof: Assign list L(v) to each vertex v E V(G) such that IL(v)l and assume I U L ( v) I =/= (G). Since G is connected, there exist two vertices, x andy, such that L(x) =/= L(y) and xy E E(G). Let ex E L(x)-L(y), and color x with Cx. Going forward, no other vertex but x will receive color ex, assuring that x will be fixed by every color-preserving automorphism of G. Construct a breadth first search spanning tree of G rooted at x. Since INc(x)l < we can color each vertex wE Nc(x)-y with a unique color, Cw E L(w), such that Cw =/= Cx. Since IL(y)l and Cx (j. L(y), there exists a color, Cy E L(y) such that Cy =/= Cw for all w E Nc(x) -y; color y with Cy. From here each vertex has at most (G) -1 children in the spanning tree. Therefore we can color each 59

PAGE 74

sibling of a vertex in the spanning tree uniquely from its list, never using the color Cx Since x is the only vertex colored ex, all color-preserving automorphisms must map x to itself. By Lem1na 4.3 and that every pair of vertices in the neighborhood of x has a distinct color, each vertex in the neighborhood of x must also map to itself in a color-preserving automorphism. Similarly, we apply Lemma 4.3 to each level of the breadth first search tree, forcing each vertex to be mapped to itself in a color-preserving automorphism. Thus the coloring so constructed is a list-distinguishing coloring of G. It remains to consider when I U L(v)l which is the same as distin guishing coloring. By [19] and [36], if G is Kn, Kn ,n, or C5 then D( G) = 1 and if not then D( G) = Since in this case the lists are all the same, w e can color the vertices as in the distinguishing colorings. Thus if G is Kn, Kn n or c5 and I UL(v)l then De(G) 1; and if G is not Kn, Kn,n or c5 and I u L(v)l then De( G)= (2,3,4,6) (1,2,3,4) Figure 4.1: A labeled picture to illustrate Proposition 4.4. 60

PAGE 75

Figure 4.1 gives a breadth first search spanning tree to illustrate the proof of Proposition 4.4. Each vertex is assigned a list of length 4 which is the maximum degree. The graph on the left gives an example of one such assignment of lists. Vertex x is chosen as the root of the tree, because it has an adjacency y that does not have the same list as x. Since 1 is not in the list for y, we can color all of the children of x differently, without using 1. The descendants of x will all have at most three children in the tree, ensuring each child can be colored uniquely without using 1 with a list of length 4. Notice that the vertex g is colored the same as two of its ancestors; however, as long as it is colored differently than d and j, Lemma 4.3 ensures that the coloring fixes those vertices under all automorphisms. Theorem 4.4 immediately yields the following Brooks-type result. Theorem 4.5 Let G is a graph with maximum degree Then De(G) < unless G is one of C5 Kn or Kn, n in which case D e ( 1. 4.2 Dihedral Groups In this section, we study the list-distinguishing number of graphs realizing Dn for some n > 3. It is clear that Cn realizes Dn, but there are many other graphs that realize the dihedral group (see Figure 4.2). The group Dn is generated by aand T where a-n = e, T 2 = e and Ta= a-n-1 7 It is important to note that there are three types of non-trivial subgroups of Dn The first is (a-J), which is a cyclic subgroup. The second is Dm = (a-J, Ta-i), where m divides n and the third is generated by an element of order two (Ta-i). 61

PAGE 76

Figure 4.2: Two graphs that realize D6 As previously mentioned, Albertson and Collins introduced this topi c by examining the distinguishing number of graphs that realize the dihedral group. Theorem 4.6 [2} If G realiz es Dn then D(G) = 2 unless n = {3 4 5 6 10} i n which case D( G) is either 2 or 3. The main result of this section is as follows. Theorem 4.7 Let G be a graph realizing Dn. Th e n D(G) = D t(G). We point out at this time that the lemmata developed here to prove The or e m 4. 7 appear nearly identical to those utilized to prove the corresponding theorem in [2). However, the techniques used here frequently vary greatly from those in [2), illustrating further the distinctions between the distinguishing and list distinguishing numbers. Lemma 4.8 Let r be a group and G be a graph realizing r and suppos e ul' ... Ut are vertices from different vertex orbits of G. If n!=l St( U i ) = { e } then Dt( G) = 2. 62

PAGE 77

Proof: For each ui, select a color ci E L(ui) and then color each other vertex in 0( ui) with any color other than ci. Let g be any nonidentity element in r. Since 1 St ( U i ) = { e}' at least one Ui is not fixed by G. Since uig is not colored Ci, this is a 2-list-distinguishing coloring. G G 8 8 8 8 8 O(u) O(uJ G 8 8 Figure 4.3: An illustration of Lemma 4.8. Figure 4.3 g1ves an illustration of the proof of Lemma 4.8, where ""' ex means any color except Cx. The general idea of this lemma is that the only automorphism that simultaneously fixes each of u 1 ... Ut to themselves is the trivial automorphism, and vertices are only mapped to other vertices in their orbit. Thus coloring u 1 ... Ut uniquely in their respective orbits, which can easily be done with lists of length 2, will force any color-preserving automorphism to fix these vertices, and the only automorphism that fixes all of these vertices is the trivial automorphism. The following lemmas, the first of which appears in [2), will be useful as we proceed. Lemma 4.9 Let G realize Dn, and suppose that G has t vertex orbits. If 63

PAGE 78

u1, ... Ut are vertices from the t different vertex orbits of G then (a) n St(u1) n n St(ut) = {e}. Proof: The proof of this lemma is identical to the proof of the correspond ing lemma in [2]. Since alata-L = at and TaiatTai = O"n-t, the conjugacy class of O"t in Dn is {at, O"n-t}. Thus if at is an. element of any subgroup H then a t is an element of any subgroup conjugate to H. Hence if at E St(u1 ) n .. n St(ut), then at is in every conjugate of each of these stabilizers which in1plies at is in every stabilizer of every vertex of G. If a t fixes every vertex of G then O"t = e and t = n, since G realizes Dn Lemma 4.10 Let G realize Dn. If there is a vertex u in G such that St(u) = (O"J) then De( G) = 2. Proof: The proof of this lemma is identical to the proof of the correspond ing lemma in (2]. Let u1 ... Ut be vertices from each of the differ ent orbits of G. Then n ist(ui ) c St(u) = (aJ) which implies that n ist(ui ) = { e } by Lemma 4.9 thus completing the proof by Lemma 4.8. At this point we begin to more seriously modify the techniques frmn (2] in order to better fit our list-coloring framework. The intuition for the following proof comes from Proposition 1.6. Although an orbit of the forn1 0( u) = { u ua, ua2 uO"J-l} need not be a cycle of length j, the movement of this orbit can be envisioned as such which gives us a working 1nental picture for the proof (see Figures 4.4 and 4.5) as we verify all the details. 64

PAGE 79

Lemma 4.11 Let G realize Dn and let u be a vertex in G such that St(u) zs either (a 1,Tai) or (Tai). If IO(u)l > 6, then O(u) is 2-list-distinguishable. Proof: If vertex u has stabilizer (a.i,Tai), then O(u) = {u, ua, ua2 ... ua1 -1}. If u has stabilizer (Tai), then O(u) = {u,ua,ua2 ... ,uan-1}. Either way, we have that O(u) = {u,ua,ua2 ... ,ua1-1 } for some j, and hence we assume that j > 6. Consider the set A = { u, ua2 ua3 } and select a color cu E L( u). If possible, color ua2 and ua3 with Cu as well. We will demonstrate that it is possible to extend this coloring to a 2-list-distinguishing coloring without using Cu on any vertex in V (G) -A. Case 1: All three vertices in A are color e d with Cu We proceed by coloring the vertices in V (G) -A using any color in their respective lists except Cu. Any automorphism g in Dn that fixes this coloring of 0( u) must permute the vertices in A, and specifically must map u to som e element of A. If ug = u, then g E St(u); if ug = ua2 then g E St(u)a2 ; and if ug = ua3 then g E St( u )a3 As was demonstrated in [2], the only automorphisms from these sets that permute A actually fix all of O(u). We will include this argument for completeness. Suppose g E Dn fixes A so ug = u, ua2 or ua3 The automorphisms that send u to u are St( u), the automorphisms that send u to ua2 are St( u )a2 and the automorphisms that send u to ua3 are St(u)a3 Now we show that each automorphism in St(u),St(u)a2,St(u)a3 either acts trivially on O(u) or does not fix A. The subgroup of automorphisms that act trivially on 0( u) is the intersection of the stabilizer subgroups of each vertex, so if St(u) = (a1, Tai) this is (a1) and if St(u) = (Tai) this is e If St(u) = (a1, Tai), then j divides n 65

PAGE 80

by the Orbit/Stabilizer Theorem, and the elements of St(u) are e ai a2i a(!j--l)i T/Ti T/Ti+j T/Ti+(}-l)j ... v v ... v If 0 < d < } -1, then below are the outcomes when the automorphisms above are applied to A. Aadj =A ATai+dj = {u,uan-2,uan-3 } Aadi a2 = { ua2 ua4 ua5 } ATai+dj a2 = { ua2 u uan -l} Aadia3 = {ua3,ua5,ua6 } ATai+dia3 = {ua3,ua,u} Since n > 6, the only automorphism that maps A to A is adi, which acts trivially on O(u). If St(u) = (Tai) then St(u) = {e,Tai} and below are the outcomes when these automorphisms are applied to A. None of these automorphisms map A to A. Thus this coloring is a 2-listdistinguishing coloring of 0 ( u). Case 2: The vertex u is the only one in A colored with Cu Suppose that St( u) = (ai, Tai). Then j divides n by the Orbit/Stabilizer Theorem, so the assumption that j > 6 implies that ua2 f= uan -2 which also holds when St(u) = (Ta i). In either case, we extend the coloring of A by first assigning the vertex uan-2 any color c f= Cu in L(uan-2). Since we utilize the color Cu on the vertices in A wherever possible and u is the onl y vertex of G that receives color Cu, we conclude that Cu rt L('ua2). Therefore there is a color 66

PAGE 81

c' in L( UCJ2), different from both c and Cu. Color u0"2 using color c' and color the remaining vertices of G with any color aside from Cu in their respective lists. We now show that this coloring distinguishes 0( u). Since u is the unique vertex of color cu, any color-preserving automorphism g E Dn must lie in St(u). Then either g = O"dJ or g = TO"i+dJ, with d being necessarily zero when St( u) = (TCJi). Note that O"dJ fixes O(u) and that, for any d TO"i+dJ takes u0"2 to UO"n-2 Since we have constructed our coloring so that U0"2 and UO"n-2 have different colors, this yields a 2-list-distinguishing coloring of 0 ( u). Case 1 Case2 Figure 4.4: An illustration of Case 1 and Case 2 of Lemma 4.11, where c =/= c'. Case 3: The vertices u and u0"2 are the only ones in A colored with Cu As above, if St(u) = (O"J,TO"i ) then j divides n by the Orbit/Stabilizer Theorem. Consequently, the assumption that j > 6 implies that u0"3 =/= uCJn-I which again also holds when St(u) = (TO"i). In this case we extend the coloring of u and uCJ2 in a similar manner to Case 1 with two exceptions. We make no special color assignment to UO"n-2 save the standard assumption that it doe s not receive color Cu Instead, we assign different colors to the vertices u0"3 and 67

PAGE 82

UO"n-l such that neither vertex is colored with Cu. As above, this is possible since Cu L( U0" 3), or else we would have used it to color u0"3 Now every automorphism g E Dn that preserves the colors on O(u) either interchanges u and U0"2 or fixes both of these vertices. As discussed in the previous case, any element of St(u) will either fix all of O(u) or will map u0"2 to UO"n-2 Thus as UO"n-2 is not colored with cu, any color preserving automorphism g must interchange u and U0"2 which implies that g has the form g' 0"2 where g' is an element of St( u). Specifically, either g' = O"dJ or g' = TO"i+dJ for some integer d, with d = 0 if St(u) = (TO"i). In either case, g'0"2 takes u0"3 to UO"n-I, implying that this coloring 2-list-distinguishes O(u). Case 4: The vertices u and U0"3 are the only ones in A colored with Cu. Suppose first that St(u) = (TO"i). We wish, as above, to extend our coloring of A to a list-distinguishing coloring of 0( u) in which no vertices aside from u and U0"3 receive color Cu. Any element g E Dn that fixes such a coloring must either stabilize u or exchange u and u0"3 Consequently, either g = TO"i or g = TO"i+3 so consider the outcomes when these elements are applied to A: ATO"i = { u, UO"n-2' UO"n-3} ATO"i+3 = { U0"3 UO", u}. Therefore, we would like to choose colors x E L( UO") and y E L( UO"n-2 ) such that x, y =Icu and choose a color z =Ix, y from L(u0"2). We would then extend our col oring of A by assigning these colors to their respective vertices and then coloring the remaining vertices in G using any color except Cu. The coloring so described is possible unless all of the following hold: L(uO") = {eu,x}, L(uO"n-2 ) = {eu,y} and L( u0"2 ) = { x, y }. In this case, suppose L( u) = { Cu, We will then recolor 68

PAGE 83

u with and again color ua2 and ua3 with these colors if possible. Then the analysis conducted thus far assures that we can construct a 2-list-distinguishing coloring of O(u), as we cannot have L(ua) = L(uan-2 ) = and L( ua2 ) = { x, y} for x = y, and this was the only obstacle preventing us from constructing the desired coloring when St(u) = (Tai). Hence we assume that St( u) = ( a1, Tai). In this case, j divides n by the Orbit/Stabilizer Theorem, and we may assume that n > j > 6. Again, we wish to extend our coloring of A to a distinguishing coloring of Gin which no vertices aside from u and ua3 receive color Cu. If g E Dn fixes such a coloring then either g E St(u) or g = g'a3 for some g' E St(u). Thus for some d > 0, g = ad1, either ad1+3 Tai+dj or Tai+d1+3 Applying each of these elements to A, we obtain: Aad1 =A Aad1+3 = { ua3 ua5 ua6 } ATadj+i = { u, uan-2 uan-3 } ATad1+i+3 = { ua3 ua, u}. Since j divides n and n is at least seven, uan-3 =/= ua3 Therefore g = Tadj+i cannot preserve our proposed coloring. Additionally, ad1 fixes all of 0( u), so we need only consider the cases where g = ad1+3 or g = Tad1+i+3 If j > 6, then since ad1+3 takes ua3 to ua6 this choice of g cannot distinguish u. Thus when j > 6 is suffices to assume that g = Tai+dj and thus we need only to distinguish ua from ua2 without assigning Cu to ua, which is clearly possible as we have assumed that Cu rJ. L( ua2). Thus we assume that j = 6 and that either g = ad1 or g = Tai+dj+3 We would like to choose colors x E L(ua) andy E L(ua5 ) such that x, y =/= Cu and 69

PAGE 84

choose a color z =1x, y from L(ua2). Then we would extend our coloring of A by assigning these colors to their respective vertices and then coloring the remaining vertices in G using any color except Cu. As above, this coloring is possible unless L(ua) = {eu,x}, L(ua5 ) = {eu,y} and L(ua2 ) = {x,y}. However, in this case we proceed by changing our initial coloring of A by using the color =1cu in L(u). As when St(u) = (Tai), this allows us to construct a coloring that will distinguish 0( u), and therefore completes the proof. Case3 Figure 4.5: An illustration of Cases 3 and 4 of Lemma 4.11, where c =1c' and x, y =1z. Now that we have shown that sufficiently large orbits can be 2-list-distinguished, we show that if a graph has one of these large orbits that the 2-list-distinguishing coloring on the orbit can be extended to 2-list-distinguish the entire graph. The following is a slight modification of the corresponding lemma in [2]. Lemma 4.12 Let G realize Dn. Let u be a vertex such that u E V(G) and St(u) = (ai, Tai) or (Tai). If IO(u)l > 6, then De( G)= 2. Proof: Assign lists of length two to each vertex in G. If St(u) = (Tai), then the intersection of the subgroups conjugate to St( u) is the identity. Applying 70

PAGE 85

Lemma 4.11, O(u) is 2-list-distinguishable and thus by Lemma 4.8, De(G) = 2. Therefore, assume St( u) = (rJJ, TrJi). Since 0( u) is 2-list-distinguishable, we need only consider the automorphisms that act trivially on 0( u). These are the intersection of the stabilizers of vertices of O(u), which is A= (rJ1). The group action of A on G creates vertex orbits U1 U2 .. Ut. The orbit O(u) is broken into 1-orbits under the group action A, because rJJ fixes O(u). From each orbit Ui such that lUi I > 1 select a vertex u i and color it with any color ci E L(ui); notice we are not recoloring the vertices of 0( u). Then color the remaining vertices of Ui with any color other than ci, construct a list-distinguishing coloring of 0 ( u) from its assigned lists, and color all other uncolored vertices in G with any color from their respective lists. If a nontrivial automorphism in A fixes ui, then it must fix all of Ui. Thus each g =/= e in A map move some ui to another vertex in its orbit, implying that the only color preserving automorphism is the identity. Consequently, this is a 2-list-distinguishing coloring of G, so De( G) = 2. Lemmas 4.8 4.11 provide the necessary machinery to complete the proof of Theorem 4.7, and we do so now. Proof: (of Theorem 4. 7) Albertson and Collins proved in [2], that if n has a divisor which is a prime power po: greater than 6 there must be an orbit of order at least 6. By Lemma 4.2 these graphs are 2-list-distinguishable, and so the only remaining cases are n = 3, 4, 5, 6, 10, 12, 15, 20, 30, 60. Assume that n > 12 and that every orbit has size less than or equal to 5. By Lemma 4.10, we may assume that the stabilizer of every vertex is either (rJJ, TrJi) of order or TrJi of order 2. By the Orbit/Stabilizer Theorem, an stabilizer of order 2 J corresponds to an orbit of size n, which is greater than 5. Hence each vertex 71

PAGE 86

must have the stabilizer (a-J, Ta-i). For G to realize Dn, G must have orbits with sizes whose least common multiple is n. Since we are assuming that all orbits are smaller than 6 if n = 12 there are orbits of size 3, 4; if n = 15, there are orbits of size 3, 5; if n = 20, there are orbits of size 4, 5; if n = 30, there are orbits of size 2, 3, 5; and if n = 60, there are orbits of size 3, 4, 5. Since 15 is odd, there is no 2-orbits if n = 15; since 4 doesn't divide 30, there is no 4-orbit if n = 30. If n = 12, 20, or 60, then there is no 2-orbit, or we could choose a stabilizer from the 2-orbit and 4-orbit whose intersection is (a-4 ). Then by Lemma 4.9, the intersection of the stabilizers from all orbits is the identity, and by Lemma 4.8 we can 2-list distinguish G. Thus we can assume that, except for the 1-orbits, the orbits for each n must be exactly as listed in the second sentence of this paragraph. Therefore if n > 12, the orbits of G have sizes which are all pairwise relatively prime. From [2], Dn is the product of the automorphism group of each orbit, considered as a subgraph of G. Since each orbit must be a vertex tran-sitive graph, the orbits of size 3 are K3 or its complement; the orbits of size 4 must be either K4 or its complement or C4 or its complement; and the orbits of size 5 must be either K5 or its complement or C5 or its complement. In each case, the product of the sizes of the appropriate groups is larger than the size of Dn for each value of n. Thus if n > 12 it must have an orbit of size 6 or larger, and G can be 2-list-distinguished by Lemma 4.2. It remains to show that the theorem holds when n = 3, 4, 5, 6 or 10. Suppose first that G realizes Dn, where n = 3 or 5 and select a vertex u with nontrivial orbit in G. By Lemma 4.10, we may assume that every vertex u in G has 72 I

PAGE 87

St(u) = (T(Ji) or ((}j1T(}i). However, as n is prime, if(JJ fixes u, thenj = 0 or j = 1. Consequently, we may assu1ne that j = 0, as ((}, T(}i) = Dn, and by assumption u has a nontrivial orbit. Note as well that if T(}i is in St(u), then Tis in St(u(}x) where 2x = n-i (mod n). Such an x exists for all i when n = 3 or 5, so we may assume that St(u) = (T). Then, since the orbit of u is by assumption nontrivial, O(u) { u, U(}, ... U(}n-l} and the only element of Dn that fixes all of 0( u) is e If G has exactly one nontrivial orbit, then this orbit is precisely 0( u) { u, U(}, ... l U(}n-l }. Since this orbit behaves as c3 or Cs, we need 3 distinct colors to distinguish O(u) and thus G; therefore, D(G) = De(G) = 3 (se e G1 in Figure 4.6). Suppose then that G has vertices u and v with distinct nontrivial orbits and that we have also assigned lists of length 2 to the vertices of G. We may furthermore assume, via the above discussion, that St(u) = St(v) = (T). If it is possible to 2-list-distinguish O(u), the n we do so and color the rest of the graph as in the proof of Lemma 4.2. If it is not possible to color each vertex in 0( u) with a unique color, then each vertex in 0( v) must have list L( U(}i) = { c1 c2}. We then color u with color c1 and color both U(} and U(}2 with color c2 If g a nonid entity element of Dn, fixes this coloring of O(u), then g E St(u). However, since O(v) is nontrivial, g must exchange two elements in 0( v), say V(}i and V(}j. Assigning these vertices distinct colors from their respective lists serves to 2-list-distinguish G (see G2 in Figure 4.6) and thus implies that D( G) = De( G) = 2. Next let G be a graph that realizes D 4 and furthermore assume that there is no vertex u in G such that St(u) = ((JJ) or IO(u)l > 6. Lemmas 4.8 and 73

PAGE 88

Figure 4.6: Two graphs that realize D5 with example lists and list distinguishing colorings using white, black, and grey. 4.9 imply that if there are vertices u and v in distinct orbits of G such that T(J'i E St( u) but T(J'i St( v), then D( G) = De( G) = 2 since the intersection of the stabilizers of u and v and ((]') will be trivial. Suppose that T stabilizes some element in every orbit of G (the case where some other T(J'i stabilizes an element in every orbit is handled similarly). Under our assumptions, every nontrivial orbit in G must have order either two or four. If every nontrivial orbit has two elements, then T stabilizes every vertex in G, a contradiction. Therefore, there is some vertex u such that St(u) = (T) and 0( u) = { u, U(J', U(J'2 U(J' 3}. If possible, color the orbit of u in a manner consistent with the traditional distinguishing coloring of C4 Specifically, for some i, color U(J'i and U(J'i+l with the same color c and then color the other two vertices in O(u) with distinct colors other than c. Since no element of D4 fixes all of O(u), this would suffice to 2-list-distinguish G and also shows that De( G) < 3. Thus we may assume that L(u(J'i) = {c1 c2 } for all i implying that if O(u) is the only nontrivial orbit of G, D( G) =De( G) = 3. Next assume that there is some vertex v, not in 0 ( u), such that 0 ( v) is also nontrivial and assign lists of length two to each vertex in G. We claim that it is possible to construct a list-distinguishing coloring of G from these 74

PAGE 89

lists. If IO(v)l = 4, then O(v) = {v,va,va2,va3 } and we may assume that L( vai) = { c;} for all i. Without loss of generality, suppose that T stabilizes v (and therefore vo-2). Color u and ua with color c1 ua2 and ua3 with color c2 v and va2 with color and, finally, va and va3 with color c;. Then the only automorphism that fixes the colors in both 0( u) and 0( v) is e, so this coloring 2-list-distinguishes G (see G1 in Figure 4.7). We may therefore suppose that 0( v), and every nontrivial orbit of G aside from O(u), has exactly two elements, and hence that St(v) = (o-2 T) and O(v) = {v,va}. The case where St(v) = (a 2 ,TaJ) is again similar. We will color u and ua with color c1 ua2 and ua3 with color c2 and color v and va with distinct colors. The only nonidentity automorphism of G that preserves this coloring of O(u) is Ta3 However, this interchanges the elements of O(v), which received different colors, so this coloring 2-list-distinguishes G (see G2 in Figure 4.7). :v (w b) (g .b) G2 (g.b) Figure 4. 7: Two graphs that realize D4 with example lists and list distinguishing colorings using white, black, and grey. Next we consider the penultimate case, that G realizes D6 By Lemmas 4.10 and 4.2, we may assume that there is no vertex u in G has St(u) = (aJ) or IO(u)l > 6. If there exists a u E V(G) such that St(u) = (Tai), then IO(u)l = 6, therefore we assume that every vertex u in G has St(u) = (aJ, Tai). Given this stabilizer and the Orbit/Stabilizer Theorem, for every vertex u in 75

PAGE 90

G, IO(u)i = 1, 2 or 3. This implies that G can easily be 3-list-distinguished, as it is possible to color all of the vertices in a given orbit with distinct colors. Furthermore, if there is no orbit of order 3, then it is not difficult to 2-list distinguish G. Therefore, let us first assume there is exactly one orbit of order 3. Specif ically let u be a vertex such that IO(u)i = 3 and observe that necessarily O(u) = {u,uo-,uo-2}. Suppose first that for each x E O(u) there 1s some x E Aut (G) n St ( x) such that the following hold: 1. cPx interchanges the two vertices in O(u)x, and 2. cPx fixes all of V( G) 0( u). In this case, we cannot 2-distinguish G with any 2-coloring, as without loss of generality both uoand uo-2 will receive the same color. However, then the automorphism cPu described above is nontrivial and color-preserving, regardless of how the remainder of G is colored. If there is some x E 0( u) for which no such x exists, then we claim that G is 2-list-distinguishable (and hence 2-distinguishable). In this case, we assign distinct colors to all pairs of vertices lying in orbits of order two and also color all vertices of 0( u) with distinct colors, if this is possible. If it is not possible to color 0( u) in this way, then each vertex in 0( u) must be assigned identical lists, say {c 1 c2}. We then color x with c 1 and the vertices in O(u)x with c2 Due to the assumptions that 0( u) is the unique orbit of order three and that there is no x as described above, any nontrivial automorphism g E Aut( G) that preserves this coloring of 0( u) must interchange the elements of an orbit 76

PAGE 91

of order two. However, all such orbits have been colored with distinct colors, so g is not color-preserving. It follows that Dt_( G) = 2 Suppose then that G has more than one orbit of order 3, and assign lists of order 2 to the vertices of G. Choose vertices u and v in distinct orbits such that IO(u)l = IO(v)l = 3. If it is not possible to color each vertex in O(u) with a distinct color (as in G1 in Figure 4.8), then each vertex in O(u) must have the same list, { c1 c2}. We then color u with c1 and the other two vertices with color c2 If g, a nonidentity element of D6 fixes this coloring of O(u) then g E St(u). However, since IO(v)l = 3, g must exchange two elements in O(v), call them v' and v". Assigning v' and v" distinct colors from their respective lists serves to 2-list-distinguish G (see G2 in Figure 4.8). Therefore D(G) = Dt_(G) = 2. Figure 4.8: Two graphs that realize D6 with example lists and list distinguishing colorings using white, black and grey. Suppose lastly that G realizes D10 and that there is no vertex u in G such that St(u) = (e5i) or IO(u)l > 6. If there exists au E V(G) such that St(u) = (TCJi), then IO(u)l = 10, therefore we may assume that every vertex u in G has St(u) = (CJi,TCJi). Given this stabilizer, it is not hard to show that for every vertex u in G IO(u)l = 1, 2 or 5 with the Orbit/Stabilizer Theorem. Furthermore, as every orbit of order 5 in V(G) has the form O(u) = { u, uCJ, ... uCJ4 } and stabilizer (CJ5 TCJi) for some j it is not difficult to see 77

PAGE 92

that the action of D10 on any such orbit of order five can be viewed precisely as the action of Ds on the vertices of C5 We observe that this implies that G is 3-list-distinguishable, as then we may color each orbit of order five such that three vertices receive distinct colors and also color the orbits of order two so that both vertices receive distinct colors. Keeping in mind the action of Aut( G) on O(u), we can see that this is a list-distinguishing coloring. Again we can easily 2-list-distinguish G if there are no orbits of order 5, so we first assume there is exactly one orbit of order 5. Specifically let u be a vertex such that I 0( u) I = 5 and recall that necessarily 0( u) = { u, UO", ... u0"4}. Suppose as well for every x E O(u) there is some x E St(x) such that the following hold: 1. x interchanges the pairs (xO", X0"4 ) and ( x0"2 x0"3 ) and 2. x fixes all of V( G) -0( u). As in the previous case, we claim that the existence of these x implies that G is not 2-distinguishable. In any 2-coloring of 0( u), there is some vertex x such that the pairs (xO", X0" 4 ) and (x0"2 x0"3 ) are monochromatic. How eve r then the automorphisn1 x describ e d above is nontrivial and color-preserving regardless of how the remainder of G is colored. It follows that G is not 2-list-distinguishable and, by our above observation, that G must therefore be 3-list-distinguishable. Suppose therefore, without loss of generality, that there is no such u E Aut(G) and assign lists of l ength two to V(G). We color eac h orbit of length two with distinct colors, and if possible assign distinct colors to three vertices 78

PAGE 93

in 0( u). If it is not possible to color three vertices with distinct colors, then each vertex in 0( u) must have the same list, { c 1 c2}. We will then color u with color c 1 and color ua, ua2 ua3 and ua4 with color c2 Given the action of Dw on 0( u), the only nontrivial automorphisms that would fix this coloring of O(u) necessarily fix u and exchange the pairs (ua, ua4 ) and (ua2 ua3). By the assumption that there is no cPu satisfying conditions (1) and (2), such an auto morphism must exchange the vertices in an orbit of order two and is therefore not color-preserving. It follows that G is 2-list-distinguishable. Now assume there is more than one orbit of order 5 and ass1gn lists of length 2 to the vertices of G. Choose vertices u and v in distinct orbits such that IO(u)l = IO(v)l = 5. If it is possible to color three vertices in O(u) with distinct colors, then such a coloring can be extended to a 2-list-coloring of G (see G 1 in Figure 4.9). If it is not possible to color three yertices with distinct colors, then each vertex in O(u) must have the same list, {c 1 c2}. We then color two vertices, v and w, with c1 and the rest with color c2 If g, a nonidentity element of D10 fixes this coloring of O(u), then either g E St(v) n St(w) or g interchanges v and w. However, since IO(v)l = 5, g must exchange two elements in 0 ( v), call them v' and v". Assigning v' and v" distinct colors from their respective lists serves to 2-list-distinguish G (see G2 in Figure 4.9). Therefore D(G) = De(G) = 2. As a consequence of the proof of Theorem 4.7, we obtain the following, which tells us when the (traditional) distinguishing number is 2 and when it is 3 for the small cases. This information was vital for determining that D( G) = De( G) for all graphs G that realize the dihedral group 79

PAGE 94

Figure 4.9: Two graphs that realize D10 with example lists and list distinguishing colorings using white, black and grey. Theorem 4.13 Let G be a graph realizing Dn such that V(G) has no orbit of order greater than .five, and also such that G does not satisfy the hypotheses of Lemma 4.8 or Lemma 4.10. Then D(G) = 3 if and only if G has exac tly one nontrivial orbit 0 satisfying one of the following: 1. n E {3, 4, 5} and 101 = n or 2. n = 6, 101 = 3, and for each x E 0 there is some x E St(x ) suc h that th e following hold: (a) x interchanges the two vertices in 0( u) -x, and (b) x fixes all ofV(G)-O(u), or 3. n = 10, 101 = 5, and for each x E 0 there is some cPx E St(x) such that th e following hold: (a) x interchanges the pairs ( xa, xoA) and ( xa2 xa3), and (b) cPx fixes all of V (G) 0 ( u) 80

PAGE 95

5. List-Distinguishing Cartesian Products In this chapter we look at the list-distinguishing number of Cartesian product graphs. We first show that most Cartesian product graphs have list distinguishing number 2. Then we show that De( G) = D( G) for the Cartesian product of two cycles, and lastly we give the list-distinguishing number of the Cartesian product of two complete graphs. 5.1 Motion Lemma A graph is called prime (with respect to the Cartesian product) if it cannot be represented as the Cartesian product of two nontrivial graphs. Two graphs G and H are relatively prime (with respect to the Cartesian product) if there is no nontrivial graph that is a factor of both G and H. For example if two graphs are not isomorphic and prime, then they are relatively prime. Fi nally, a fiber .. ,gk) of G1D DGk is the subgraph induced by the vertex set {(91,92, ... ,gi-I,x,gi+I, ... ,gk)lx E Gi} The automorphism group of Cartesian products is well understood. If G = (G1DG2 ) and E Aut(G1), then' : V(G) V(G) defined by' : (ui, vJ) (ui, vJ) is an automorphism of G. If G1 = G2 then a: (ui vJ) (vJ, ui) is also an automorphism of G. In fact, the automorphisms of a factor and permutations of isomorphic factors generate Aut( G) [32). The distinguishing number of Cartesian products has been extensively studied. In [6) Bogstad and Cowen detern1ined that D( Qd) = 2 if d > 4, where Qd 81

PAGE 96

denotes the d-dimensional hypercube. In 2005 Albertson generalized this result to connected prime graphs [1], using a probabilistic result from Russell and Sundaram [45]. Let E Aut(G) and define m() = l{v E G: (v) # v }l. We refer tom() as the motion of The motion of a graph G, m( G) is defined as m(G) = min m(). EAut(G) 4>=/=id If we decompose the automorphism into a product of disjoint cycles ( Vu V12 .. VI1 ) ( V21 V22 ... V2e2 ) .. ( vkl vk2 ... vkek), then the cycle norm of is the quantity k c() = I)ei1). i=l The cycle norm of a graph G is defined by c(G) = min c(). EAut(G) 4>=/=id The lemma by Russell and Sundaram, referred to as the motion l emma, showed if the motion of G is sufficiently large then the distinguishing number is small. We now show that the motion lemma works the sa1ne for list-distinguishing co lorings. The proof of the proposition below follows closely with the proof in [45]. Proposition 5.1 Ifc(G) ln d > ln IAut(G)I then G is d-l ist -distinguishable. Proof: Let G be a graph. For each v E ll (G), we assign list L v such that 1 Lv I = d. We select a color for each vertex v independently and uniformly from Lv and cal l this coloring X Let E Aut( G) such that # e The probabilit y 82

PAGE 97

that preserves x is All together subadditivity gives that, 1 -1= e, Vv, x(v) = x((v))] < IAut(G)i(dr(c). By the hypothesis, this quantity is less than 1, so there exists a list-coloring x such that for all-:/: e, there exists a vertex, v, such that x(v) -:/: x((v)). Albertson found that D(Gr) = 2 if r > 4 and if IV( G) I > 5 then D(Gr) = 2 when r > 3 [1]. To proof this statement he observed that any automorphism of a graph G with n vertices is an automorphism of Kn and proved the following two theorems. Theorem 5.2 {1] = r!(n!Y Theorem 5.3 {1] If n > 3, then = 2ne-l Albertson found that r!(n!Y < 2nr-l when r > 4 or when n > 5 and r > 3, and thus this is when < 2. In the same way, we can combine Proposition 5.1, Theorem 5.2, and Theorem 5.3 to arrive at the following corollary. Corollary 5.4 If G is a connected graph that is prime with respect to the Cartesian product, then DI!(Gr) = 2 ifr > 4 and if IV( G) I > 5 then De(Gr) = 2 when r > 3. Albertson points out, using [28] and [34], that almost all graphs satisfy the hypotheses of Corollary 5.4. 83

PAGE 98

5. 2 Products of Cycles We now limit our work to the Carte sian product of two graphs, since these are not covered under Corollary 5.4. In [37] it was found that D( Gr) = 2 r > 3 for any connected graph G # K2 by Klavzar and Zhu. Imrich and Klavzar rounde d out these investigations when they showed that D( Gr) = 2 wh e n r > 2 and G # K2 K3 the same year [35]. We now turn our attention to the Cartesian product of two cycles, also known as the toroidal grid. We label a vertex of CnDCm as ( ui, v 1 ) if it is in fibers c:n and but for simplicity, we denot e L((u, v)) as L(u, v). W e also define S c(G) = {v E V(G) I c E L(v)} and will writ e S c(G) = S c if the context is cl e ar. If n # m the automorphism group of CnDCm is gen erate d by the Cartesian product of the generators of Cn and Cm This leads us to the following elementary lemma about the action of an automorphis1n of a cycl e factor Cn, which will b e used in subsequent proofs. Lemma 5.5 Let G ( CnDCm) such that n # m. Let E Aut( Cn), 7/J E Aut(Cm) and' E Aut(CnDCm) such that' : (ui, Vj) (u i 'l/;vj) If' ( ui v1 ) ( UkJ 'lf;v1 ) then : ( ui vp) ( uk, 7/Jvp) for all p E {1, ... m}. Proof: Let G = (CnDCm) n # m and (ui, Vj) E V(G). Let E Aut(Cn) 'ljJ E Aut(Cm) and E Aut(CnDCm) such that : (ui, Vj) (ui, 'l/;vj) Let : (ui, v1 ) (uk, 'lf;v1 ). This implies that (ui) = (uk) Since Aut(Cn) = Dn = ,we can write' = 7/J) where a E { 0 ... 2n -1} and b E { 0, 1}. Let ( u i Vp) E V (G). Now ( ui, Vp) = 'lj;)(ui, vp) = 'l/;vp) Since ui uk, 7/Jvp) = (uk, 'l/;vp) Since p was arbitrary, this is true for all p E {1, ... m}. 84

PAGE 99

Figure 5.1: Let/ : (ui, vJ) (ui, O"gvJ) E Aut(C4DC5 ) to illustrate Lemma 5.5. If (u1,v1) (u4,v5) in', then (u1,v2) (u 4,v1 ) (u 1,v3 ) (u 4,v2), (u1, v4) (u4, v3), and (u1, v5) (u4, v4). To prove that D( CnDCm) = De( CnDCm) for all n and m, we use the fol-lowing lemma, which says that if we can 2-list-distinguish any fiber of CnDCm in a specific way then the entire graph can be 2-list-distinguished. Lemma 5.6 Let G = CnDCm, and assign a list L( ui, Vj) of size 2 to each (ui, Vj) E V(CnDCm) If there exists a fiber that can be -list-distinguished with a vertex that has a unique color in that fiber, then G can be -list-distinguished. Proof: Let G = CnDCm, and assign a list L(ui, vJ) such that IL(ui, vJ)I = 2 to each (ui, vJ) E V(CnDCm) Assume we can color using a unique color on the vertex ( u1, v1). Case 1: Suppose C Bc1 Color each vertex ( Ui' v2) E with cl. Assign list L' ( Ux' Vy) = L ( Ux' Vy) -cl to all uncolored vertices and '-list-color these vertices arbitrarily (see Case 1 in Figure 5.2). 85

PAGE 100

Case 2: There exist vertices (ui, v2 ), i =11 and (ull vj),j =11 such that ( Ui, V2) ( U 1 1 V j) :_ B c1 For all uncolored vertices, assign list L' (ux, vy) = L(ux, vy) -c1 Color ( ui, Vm) with some c2 E L' ( ui, Vm), color ( ui, v2 ) with some c 3 E L' ( ui, v2 ) such that =1c2, and '-list-color the rest of the vertices. Since they are the only two fibers with a vertex colored cl, must map to in any non-trivial color-preserving automorphism; furthermore, has been list-distinguished, so there is at most one automorphism, a, that could map to Assume that a(ui, vi) f---+ (u1 vj), and let the vertex (ui, v1 ) be colored ck. The vertex ( U1, Vj) :_ Bc1 so recolor ( ui, Vj) with Ca E L' ( ui, Vj) such that Ca =1Ck (see Case 2 in Figure 5.2). Case 3: There exists a vertex (ui,v2 ) i =11 such that (ui,v2 ) :. Bc1 and ( ui Vj) E Bc1 for all j =11. Color (u1, v2) with c1, and assign list L' (ux, vy) = L(ux, vy) ci to all uncolored vertices. Let vertex ( ui, VI) be colored Cp, and color ( ui, v2 ) with cb E L' ( ui, v2 ) such that cb =1cp. Now L' -list color the rest of the vertices (see Case 3 in Figure 5.2). We claim that in each of the three cases above the coloring is list-distinguishing. First consider an automorphism of the form e), =1e which maps ( Ut, vi) to ( un v1 ) for some t =1r by Lemma 5. 5. The graph induced by the ver tices of has been assigned a distinguishing coloring. Thus an automorphism of this form does not preserve colors. Also by Lemma 5.5 the automorphism ( e, T:;), T:; =1e maps either (ui v 2 ) to (ui vj), 2 =1j for all i E {1, ... n}, or (ub v1) to (ui vi), 1 =1j. 86

PAGE 101

However in case 1, n -1 vertices of are colored ci, and this is the only fiber with such a coloring. The vertex ( ui, vi) is colored ci while the rest of the fiber is not; again this is the only fiber with such a coloring. In Case 2, ( U1, vi) is the only vertex colored ci, and we know that ( ui, v2 ) must map to (ui, vm), which are colored differently. In Case 3, (ui, vi) and (ui, v 2 ) are the only two vertices colored ci, so any non-trivial automorphism must interchange (ui, vi) and (ui, v2), which will also interchange (ui, vi) and (ui, v 2 ), which have different colors. Therefore in each of these cases, automorphisms of this type are not color-preserving. The automorphism is equal to (e, o e). In Case 1, the automorphism ( e) will map ( ui, VI) to ( UJ, vi) for some j E { 1 ... n} and ( ui, v2) to ( uk, v 2 ) for all i E {1, ... n }. Then-1 vertices of are colored with CI and the vertex ( UI, VI) is in fiber SO as in the previous paragraph, e) is not color-preserving. Similarly, e) is not color-preserving in Cases 2 and 3. Therefore in each of these cases, automorphisms of this type are not color-preserving. If n = m consider the automorphism a, such that a( ui, vi) f---* ( ui, vJ) for some i and j, which would map to In Case 1, has n -1 vertices colored ci and there is no Cm fiber with this number of vertices colored ci. In Case 2, a is not color-preserving by coloring (ui, vi) and (ui, vJ) differently. In Case 3, has two vertices colored ci and no Cn fiber has more than one vertex colored ci. Therefore in each of these cases, a automorphisms are not colorpreserving. 87

PAGE 102

In every case, colors can be chosen from the list of size 2 to list-distinguish CnDCm. If there exists a fiber that can be -list-distinguished, IL( v) I = 2 for all v E V (G), with a vertex that has a unique color for that fiber, then G can be -list-distinguished. In Figure 5.2, rvC refers to any color that that is not c and vertices colored black represent the vertices colored ci in the proof of Lemma 5.6. We now use Lemma 5.6 to 2-list-distinguish all graphs that are the Cartesian product of two cycles except C3DC3 Case 1 Case2 Case3 Figure 5.2: Examples of colorings described in Lemma 5.6. Vertices represented by open circles cannot be colored black. Lemma 5.7 Let n > 3 and m > 3 such that at most one ofn and m is 3. Th en Proof: Assign a list L( ui, VJ) such that IL( ui, VJ) I = 2 to each ( ui, VJ) E V(CnDCm) If I U L(ui, vJ)I = 2, then color the vertices as in [6) if n = m = 4 or as in (35) otherwise. If not, then there must be two vertices whose lists are different. Since CnDCm is connected, there exist two adjacent vertices with different lists, and these two vertices are either on the same Cn or Cm fiber. Without loss of generality, assume they are the vertices ( ui, VI) and ( u2, vi) on Color the vertex ( Un, VI) with c3 E L( Un, VI); color vertices ( ui, VI) and 88

PAGE 103

( u2, VI) from their lists such that the colors are different and both not c 3 say ci and c2 respectively, which is possible since their lists are not the same. Color the rest of the vertices of anything from their list other than ci. Since ( ui, VI) is the only vertex with color ci, any colorpreserving automorphism on the fiber must map (ui, VI) to itself. Therefore, either ( Un, vi) f-* ( u2, vi) or ( Un, vi) f-* ( Un, vi) In the former case, the automorphism does not preserve the colors. The latter case is the trivial automorphism, so the coloring is an -list-distinguishing coloring on that uses a unique color ci. By Lemma 5.6, we know that we can extend this coloring to a -list-distinguishing coloring of CnDCm. Therefore, D(CnDCm) = 2 if at most one of nand m is 3 Proof: V(C3DC3). Color the vertices (ui, vi), i E {1, 2, 3} from their list such that each vertex received a unique color. Let vertex ( ui, vi) for i E { 1, 2 3} be colored ci, and we will not use the color ci on any other vertex. If one of the vertices (ui, v2 ) and (ui, v3 ) has a color that is not cr, c2, or c3 in its list, say c 4 then use that color. Then color the other anything from its list that is not ci nor c4 (see G in Figure 5. 3). If both of their lists are { ci c 2 c 3 }, then color them both c 2 (see H in Figure 5. 3). Lastly, color ( u 3 v2 ) and ( u3, v3) from their list such that the colors are different and both not ci, and then color the remaining vertices anything from their list that is not ci. 89

PAGE 104

By Lemma 5.5 and since Cj has a list-distinguishing coloring there is no color-preserving automorphism of the form e). Since (u1 v1 ) is the only vertex with color c1 the only non-trivial automorphism of the form ( e T:;J or would map (u3 v2 ) to (u3 v3). However, these vertices are colored differently. Lastly, the automorphism a : ( ui, vJ) ( vJ, ui) must map ( u1 v1 ) to itself. However, (u2 vi) and (u3 v1 ) are colored differently than (u1 v2 ) and ( u1, V3). Thus the only color preserving automorphism is the identity, and De( C3DC3) = D( C3DC3) = 3. G H Figure 5.3: Examples of colorings described in Lemma 5.8. The proof of the next theorem follows immediately from Lemma 5.7 and Lemma 5.8. 5.3 Products of Complete Graphs We now turn our attention to the Cartesian product of complete graphs. Imrich, Jerebic and Klavzar [35] and Fischer and Isaak [22] independently determined the distinguishing number of Cartesian products of complete graphs 90

PAGE 105

Theorem 5.10 ([35]) Let k, n, d be integers so that d > 2 and (d-1)k < n < dk. Then d if n < dk flogdk l -1; d + 1 if n > dk flogdk l + 1. If n = dk llogdk l then D(KkDKn) is either d or d + 1 and can be computed recursively in 0 (log* ( n)) time. Again, list-distinguishing this class of graphs has proved more difficult Fisher and Isaak investigated this topic by coloring the cells of an n x m matrix such that the only row and column permutations that preserve colors is the identity. We present a proof that Dt(K30K4 ) = 2; however, our method does not seem to generalize to KnDKm. In the proof, we use the tern1 multiset to mean a set where each member can have more than one membership (ie {3, 3 4 5} is a multiset). q ci CJ -q c2 c2 -C) --c2 C3 -Cj -q -q Figure 5.4: A list-distinguishing coloring of the matrix that represents K 30K4; c1 c2 and c3 need not be distinct. Proof: We consider the automorphism group of K30K4 as the group generated by arbitrary cell permutations of a 3 x 4 matrix. Hence we assign lists of size two to the cells of a 3 x 4 matrix, color from those lists, and show that 91

PAGE 106

the only composition of column and row permutations that is color-preserving is the identity. Consider the coloring in Figure 5.4, and notice that after any permutation the four cells of row 1 will still comprise a row. Cell (1, 4) is the only cell in row 1 that is not colored c1 thus column 4 must remain the fourth column after any color-preserving permutation. Similarly, cell (2, 3) is the only cell in the first three columns that is not colored c2 in row 2. Thus any color-preserving permutation must fix column 3 as well. In the same way we can fix column 2, and now all of the columns must be fixed in any color-preserving permutation. Since the columns must be fixed, it is easy to see that no row permutations will preserve the colors. If we can color the matrix as in Figure 5.4, then we do so. If not then we consider each of the following cases. Case 1: There does not exist a color that appears in three lists in any one row. If there does not exist a row that contains two lists with a common color, then each row has eight distinct colors in the union of the lists. Color row 1 and 2 such that each cell in those two rows gets a unique color and color row 3 such that is not identical to row 1 or 2 (see matrix A in Figure 5. 5). Since each row and column has a distinct multiset of colors, no row and column permutations will preserve colors. Thus this is a list-distinguishing coloring. Without loss of generality, assume now that row 1 has the color c1 in columns 1 and 2; color both of these cells with c1 Now color the other two cells of row 1 with ca and cb such that Ca =/= cb, which are both not equal to c1 If no other row contains two lists with a common element, color each cell in the remaining 92

PAGE 107

two rows uniquely, which we can do because the size of the union of the lists is at least 8 (see matrix B in Figure 5.5). In this case, each row and column has a different multiset of colors, thus this is a list-distinguishing coloring. Now assume that either row 2 or 3 has two lists with a common color, c2 Color both those cells with c2 and consider the other two cells of that row. If both of these cells have lists { ca, cb} then color them both with Ca (see matrix D in Figure 5.5); if not then color them differently such that at least one of them is not equal to Ca nor cb (see matrix C in Figure 5.5). Now color the last row such that each cell contains a unique color in that row. We know w e can do this because there is no row with a color that appears in three lists. In either coloring each row has a distinct multiset of colors so no row permutations are color-preserving. Thus the columns are also fixed, so this is a list-distinguishing coloring. c, Cz C J Ctl c, q Ca ch c, c, c, cb c, c, Ca cb c, c, c1 j-c1 C 5 G5 c 7 Cs c, Cz C:l C4 C a C ; C z c" Ca C ; c l C a I c, C 2 c3 1 -c, i --, q c6 c 1 c, I C:l c6 c 1 C s c, C:J CJ C4 c, cl Cj c4 C4 C:5 1-c1 A B c D E Figure 5.5: Examples of list-distinguishing colorings of the matrix that repre sents K3DK4 from the proof of Theorem 5.11. Case 2: There exists a color c1 that appears in three lists of a row but there is not a color that appears twice in the subset of the three columns in another row. Assume that c1 appears in the first three cells of row 1, color each of these cells with c 1 and color the fourth cell with a color from its list that is not c1. Since no color appears twice in the first three cells of row 2 or 3, each row has six 93

PAGE 108

distinct colors appearing in the lists of the first three cells. Thus we can color each of these six cells uniquely from their lists. Now color the remaining two cells anything from their list that is not c1 (see matrix E in Figure 5.5). Again the set of colors for each row and column is distinct, so this is a list-distinguishing coloring. In every case we are able to list-distinguish the graph, thus D e(K301(4 ) = 2 94

PAGE 109

6. Concluding Remarks and Future Directions In this final chapter, we discuss area for future study based on the work in this thesis. Again, we examine the two main areas of this thesis separately. 6.1 Interval Representations In chapter 2 we give two characterizations for k-trees that have interval p-representations, one being a forbidden subgraph characterization for 2-tree interval p-graphs. In [11] Brown gives a characterization of interval p-graphs based on an ordering of complete r-partite subgraphs (see Theorem 1.2) and a forbidden subgraph characterization of cycle-free interval p-graphs (see Theorem 1.1). However, a complete forbidden subgraph characterization of interval pgraphs appears to be quite difficult, even when restricting p. Thus, we must narrow our focus. One way to do narrow our focus is to restrict p and to examine a w e llunderstood class of graphs. For example, we could narrow our focus to cocomparability graphs that have an interval 3-representation. A cocomparability graph G is one in which the edges or" of the complement of G denoted cc, can be directed so that the resulting directed graph is transitive. Another way to narrow our search for a forbidden subgraph characterization would be to examine ATE-free graphs. Asteroidal triples of edges were enough to characterize the k-trees that have interval p-representations; however, we know that ATEs do not completely characterize interval p-graphs. It would be 95

PAGE 110

interesting to determine what subset of the ATE-free graphs have an interval p-representation. In chapter 3 we give a characterization of probe interval 2-trees. The only forbidden subgraph characterization is of cycle-free probe interval graphs (see Theorem 1.3). There is still hope for the a forbidden subgraph characterization of probe interval 2-trees. However which such a large obstruction set the proof may be a long case analysis. Moreover, the inconsistencies with the idea of minimal may need to be fixed. We use the sparse spiny interior 2-lobster to characterize the probe interval 2-trees, and we believe this structure could be used to characterize k-trees with k < 3, with some tweaking of the definition. Thus we conjecture the following. Conjecture 6.1 Let G be a k-tree. G is a probe interval graph if and only if it is a spare spiny interior k-lobster. 6.2 Symmetries In chapter 4 we found that the list-distinguishing number is equal to the distinguishing number for graphs that realize the dihedral group. These findings bring us back to our original question. Question 6.2 Does there exist a graph G such that D( G) < D e ( G)? In the process of trying to answer Question 6.2, we may narrow our focus to finding the list-distinguishing number of classes of graphs for which the distin guishing number is known. In chapter 5 we investigated the list-distinguishing number of the Cartesian product of complete graphs. We were only able to prove that De(K3DJ{4 ) = 2. As this proof does not see to generalize this is a ripe 96

PAGE 111

area for investigation. Other classes of graphs for which one could determine the list-distinguishing number include trees and forests. 97

PAGE 112

REFERENCES [1] Michael 0. Albertson. Distinguishing Cartesian powers of graphs. Electron. J. Combin., 12:Note 17, 5 pp. (electronic), 2005. [2) Michael 0. Albertson and Karen L. Collins. Symmetry breaking in graphs. Electron. J. Combin., 3(1):Research Paper 18, approx. 17 pp. (electronic), 1996. [3) Noga Alon. Restricted colorings of graphs. In in Surveys in Combinatorics 1993, London Math. Soc. Lecture Notes Series 187, pages 1 33. Cambridge University Press, 1993. [4) L. W. Beineke and R. E. Pippert. Properties and characterizations of ktrees. Mathematika, 18:141 151, 1971. [5) S. Benzer. On the topology of the genetic fine structure. Proc. Nat. Acad. Sci. USA, 47:403 426, 1961. [6) Bill Bogstad and Lenore J. Cowen. The distinguishing number of the hy percube. Discrete Math., 283(1-3):29 35, 2004. [7) B. Bolloba,s and A. J. Harris. List-colourings of graphs. Graphs Combin., 1(2): 115 127, 1985. [8) Debra L. Boutin. Small label classes in 2-distinguishing labelings. Ars Math. Contemp., 1(2):154 164, 2008. [9] Debra L. Boutin. The determining number of a Cartesian product. J. Graph Theory, 61(2):77 87, 2009. [10) R. L. Brooks. On colouring the nodes of a network. Proc. Cambridge Philos. Soc., 37:194 197, 1941. [11) David Brown. Variations on interval graphs. PhD dissertation, University of Colorado Denver, Department of Mathematics, 2004. 98

PAGE 113

[12] David E. Brown, Stephen C. Flink, and J. Richard Lundgren. Character izations of interval bigraphs and unit interval bigraphs. In Proceedings of the Thirty-third Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 2002}, volume 157, pages 7993, 2002. [13] David E. Brown, Stephen C. Flink, and J. Richard Lundgren. Interval kgraphs. In Proceedings of the Thirty-third Southeastern International Con fere nce on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 2002}, volume 156, pages 5 16, 2002. [14] David E. Brown and J. Richard Lundgren. Bipartite probe interval graphs, circular arc graphs, and interval point bigraphs. A ustralas. J. Combin., 35:221 236, 2006. [15] David E. Brown, J. Richard Lundgren, and Cary Miller. Variations on interval graphs. In Proceedings of the Thirty-second Southeastern Interna tional Conference on Combinatorics, Graph Theory and Computing (Baton Rouge, LA, 2001}, volume 149, pages 7795, 2001. [16] David E. Brown, J. Richard Lundgren, and Li Sheng. A characterization of cycle-free unit probe interval graphs. Discrete Appl. Math., 157(4):762 767, 2009. [17] Christine T. Cheng. On computing the distinguishing numbers of trees and forests. Electron. J Combin., 13(1):Research Paper 11, 12 pp. (electronic), 2006. [18] Jeong Ok Choi, Stephen G. Hartke, and Hemanshu Kaul. Distinguish ing chromatic number of Cartesian products of graphs. SIAM J. Discrete Math., 24(1):82 100, 2010. [19] Karen L. Collins and Ann N. Trenk. The distinguishing chromatic number. Electron. J. Combin., 13(1):Research Paper 16, 19 pp. (electronic), 2006. [20] Jiirgen Eckhoff. Extremal interval graphs. J. Graph Theory, 17(1):117 127, 1993. [21] Paul Erdos, Arthur Rubin, and Herbert Taylor. Choosability in graphs. Congr. Numer., 26:125 157, 1980. [22] Michael Fischer and Garth Isaak. Distinguishing colorings of cartesian products of complete graphs. Discrete Math, 308:2240 2246, 2008. 99

PAGE 114

[23] D. R. Fulkerson and 0. A. Gross. Incidence matrices and interval graphs. Pacific J. Math., 15:835 855 1965. [24] D. R. Fulkerson and 0. A. Gross. Incidence matrices and interval graphs. Pacific J. Math., 15:835 855, 1965. [25] P. C. Gilmor e and A. J. Hoffman. A ch a racterization of comparability graphs and of interval graphs. Canad. J. Math. 16:539 548 1964. [26] Martin Charles Golumbic. Algorithmic graph theory and p e rfect graphs. Academic Press [Harcourt Brace Jovanovich Publishers], New York 1980. With a foreword by Claude Berge Computer Science and Applied Mathe matics. [27] Martin Charle s Golumbic and Marina Lipsht e yn. On the hi e rarchy of in terval, probe and tolerance graphs. In Proceedings of the Thirty-s e cond Southeastern International Confe renc e on Combinatorics Graph Th e ory and Computing (Baton Rouge, LA, 2001 ) volume 153 pages 97 106 2001. [28] R. L. Graham. Isometric embeddings of graphs. In Selected topics in graph th e ory 3, pages 133 150. Academic Press San Diego CA 1988 [29] G Haj6s. Uber eine art von graphen. Internat. Math. Na chr, 11, 1957. Problem 65. [30] Frank Harary, Jerald A. Kabell and F. R. McMorris. Bipartite intersection graphs. Comment. Math. Univ. Carolin. 23(4):739 745 1982. [31] Pavol Hell and Jing Huang. Interval bigraphs and circular arc graphs. J. Graph Theory, 46(4):313 327 2004. [32] W. Imrich. Kartesisches Produkt von Mengensystemen und Graphen. Stu dia Sci Math. Hungar. 2:285 290 1967. [33] Wilfried hnrich, Janja Jerebic and Sandi Klavzar. The distinguishing number of Cartesian products of complete graphs. European J. Combin. 29(4):922 929 2008 [34] Wilfried Imrich and Sandi Klavzar. Product Graphs. John Wiley Sons Inc. New York 2000. [35] Wilfried Imrich and Sandi Klavzar Distinguishing Cartesian powers of graphs. J. Graph Theory 53(3):250 260 2006. 100

PAGE 115

[36] Sandi Klavzar, Tsai-Lien Wong, and Xuding Zhu. Distinguishing labellings of group action on vector spaces and graphs. J. Algebra, 303(2):626 641, 2006. [37] Sandi Klavzar and Xuding Zhu. Cartesian powers of graphs can be distin guished by two labels. European J. Combin., 28(1):303 310, 2007. [38] C. G. Lekkerkerker and J. Ch. Boland. Representation of a finite graph by a set of intervals on the real line. Fund. Math., 51:45 64, 1962/1963. [39] In-Jen Lin, Malay K. Sen, and Douglas B. West. Classes of interval di graphs and 0, 1-matrices. In Proceedings of the Twenty-eighth Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 1997), volume 125, pages 201209, 1997. [40] F. R. McMorris, Chi Wang, and Peisen Zhang. On probe interval graphs. Discrete Appl. Math., 88(1-3):315 324, 1998. [ 41] Haiko M tiller. Recognizing interval digraphs and interval bigraphs in poly nomial time. Discrete Appl. Math., 78(1-3):189 205, 1997. [42] Andrzej Proskurowski. Separating subgraphs in k-trees: cables and cater pillars. Discrete Math., 49(3):275 285, 1984. [43] Nata8a Przulj and Derek G. Corneil. 2-tree probe interval graphs have a large obstruction set. Discrete Appl. Math., 150(1-3):216 231, 2005. [44] Frank Rubin. Problem 729: the blind man's keys. Journal of Recreational Mathematics, 11(2):128, 1979. solution in 12(2) (1980)). [45] Alexander Russell and Ravi Sundaram. A note on the asymptotics and computational complexity of graph distinguishability. Electron. J. Combin., 5:Research Paper 23, 7 pp. (electronic), 1998 [46] M. Sen, S. Das, A. B. Roy, and D. B. West. Interval digraphs: an analogue of interval graphs. J. Graph Theory, 13(2):189 202, 1989. [47] [48] Li Sheng. Cycle free probe interval graphs. In Proceedings of the Thirtieth Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1999), volume 140, pages 3342, 1999. Li Sheng, Chi Wang, and Peisen Zhang. On the perfectness of tagged probe interval graphs. In Discrete mathematical problems with medical applica tions (New Brunswick, NJ, 1999), volume 55 of DIMACS Ser. Discrete 101

PAGE 116

Math. Theoret. Comput. Sci., pages 159 163. Amer. Math. Soc., Provi dence, RI, 2000. [49] Douglas B. West. Introduction to graph theory. Prentice Hall Inc. Upper Saddle River, NJ, second edition, 2001. [50] P. Zhang. Probe interval graphs and its applications to physical mapping of DNA. manuscript, 1994. [51] P. Zhang. United States Patent. http://www.cc.columbia.edu/cu/cie/ tech lists/patents/5667970.htm 1997. [52] P. Zhang, E.A. Schon, E. Cayanis, J. Weiss, S. Kistler, and P.E. Bourne. An algorithm based on graph theory for the assembly of contigs in physical mapping of DNA. CABIOS, 10(3):309 317 1994. 102