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 pgraph, 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 cyclefre e interval bigraphs in [13). In 2002 Brown, Flink, and Lundgren introduced a further e xtension of in terval bigraphs called interval kgraphs [11). We change the name to interval pgraphs here to avoid confusion. Let G = {X1,X2 ... ,XP} b e a multipartite graph. A graph G is an interval pgraph 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 2graphs (interval bi graphs) has proven difficult hence a forbidden subgraph char a cterization for interval pgraphs 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 ktrees. The class of ktrees is the set of all graphs that c an be obtained b y the following construc tion: (i) the kcomplete graph, Kk, is a ktree; (ii) to a ktree Q' with n1 vertices (n > k) add a new vertex adjacent to a kcomplete subgraph of Q'. In chapter 2 two characterizations of ktree interval pgraphs 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 2trees. 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 2tree probe interval graphs have a large set of forbidden subgraphs
PAGE 5
at least 62. We give a characterization of 2tree 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 rdistinguishing 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 rdistinguishing }. 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 ngon. 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 listdistinguishing 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 listdistinguishing number for several families of graphs and highlight a number of distinctions between the problems of dis tinguishing and listdistinguishing a graph. We first give a Brookstype result for listdistinguishing colorings. By determining precisel y when the distinguishing number is 3 in small cases we show that the listdistinguishing number is equal to the distinguishing number for all graphs that realize the dihedral group. Lastly we give the listdistinguishing 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 GK12 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. ktree Interval pGraphs 14 2.1 Definitions and Background 14 2.2 A Characterization of kTree Interval pGraphs 20 2.3 Forbidden Subgraph Characterization for 2Tree Interval pGraphs 26 3. 2tree Probe Interval Graphs . 32 3.1 Structure of Probe Interval 2trees 32 3.2 Probe Interval 2tree Characterization 3.3 Forbidden Subgraphs for Probe Interval 2trees 4. Listdistinguishing Dihedral Graphs 4.1 Brookstype 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 3sun which contains an AT, and on the right is a 2tree 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 nonisomorphic 2paths oflength five and six nonisomorphic 2paths of length six. . . 15 2.2 A 2tree with the 3cliques of G2 labeled. 16 2.3 HL is a 2caterpillar, but not an interior 2caterpillar, and HR is an interior 2caterpillar. . . . . . . 16 2.4 On the left is a 2lobster that is not a spiny interior 2lobster, and on the right is a spiny interior 2lobster. . 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 prepresentation (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 2lobster that is labeled as in Theorem 2.7. 25 XI
PAGE 12
2.9 The interval prepresentation of the 2tree in Figure 2.8. 25 2.10 Forbidden subgraphs for 2trees interval pgraphs. 27 2.11 The four graphs for Case 1 in Theorem 2.10. 28 2.12 Possible forbidden subgraphs for 2tree interval pgraphs 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 2lobsters that are not probe interval graphs in [43]. . . . . . . . . 32 3.2 A spiny interior 2lobster with the vertices and 3cliques of G2 labeled. . . . . . . . . 34 3.3 Three sparse spiny interior 2lobsters with the vertices and 3cliques 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 3sun with their possible (P, N)partitions up to isomorphism. The white vertices are nonprobes, black are probes, and the grey can be either a probe or nonprobe. . 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 ssi2lobster 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 2trees. 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 listdistinguishing colorings using white, black, and grey. . . . . 7 4 Xlll
PAGE 14
4. 7 Two graphs that realize D4 with example lists and listdistinguishing colorings using white, black, and grey. . . . . 75 4.8 Two graphs that realize D6 with example lists and listdistinguishing colorings using white, black, and grey. . . . . 77 4.9 Two graphs that realize D10 with example lists and listdistinguishing 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 listdistinguishing coloring of the matrix that represents K 3DK4; c1 c2 and c3 need not be distinct. . . . . 91 5.5 Examples of listdistinguishing 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 nondecreasing order. A kcoloring 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 kcolorable if it has a proper kcoloring. The chromatic number x( G) is the least k such that G is kcolorable. A kedgecoloring of G is a labeling f : E( G) S, where lSI = k. A kedgecoloring is proper if incident edges have different labels. A graph is kedgecolorable if it has a proper kedgecoloring. The edgechromatic number x' (G) of a loopless graph G is the least k such that G is kedgecolorable. 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 kcolorable if every assignment of kelement lists to the vertices permits a proper list coloring. The list chromatic number xe( G) is the minimum k such that G is list kcolorable. Let L( e) denote the list of colors available for an edge e. A list edgecoloring is a proper edgecoloring f with f(e) chosen from L( e) for each e. The edgechoosability G) is the rninimum k such that every assignment of lists of size k yields a proper list edgecoloring. 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 breadthfirst 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 a1 of G 3
PAGE 18
called an inverse of a, such that a* a1 = a1 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 3sun 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 cyclefree 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 cyclefree 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 kgraphs [13]. We change the name to interval pgraphs here to avoid confusion. Let G = {X11 X2 ... Xp} be a multipartite graph. The graph G is an interval pgraph 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 prepresentation 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 pgraphs is with a consecutive ordering of completerpartite subgraphs (see Theorem 1.2). 6
PAGE 21
Theorem 1.2 {13} A graph is an. interval pgraph if and only if there exists a cover of completerpartite subgraphs that can be consecutively ordered, when 1 < r < p for each subgraph. 3sun Figure 1.2: On the left is the 3sun which contains an AT, and on the right is a 2tree with an ATE. A forbidden subgraph characterization for interval pgraphs 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 ktrees. The class of k trees is the set of all graphs that can be obtained by the following construction: (i) the kcomplete graph, Kk, is a ktree; (ii) to a ktree Q' with n1 vertices ( n > k) add a new vertex adjacent to a kcomplete subgraph of Q'. Both graphs in Figure 1.2 are 2trees. Chapter 2 contains a characterization of ktree interval pgraphs and a forbidden subgraph characterization of 2tree interval pgraphs. 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 =10 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 nonprobe in any probe interval representation, which will be used often in this thesis. Moving up from trees, Przulj and Corneil found in (43) that 2tree 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 2tree PIGs and add to the list of forbidden subgraphs. 8
PAGE 23
Theorem 1.3 [4 7} A cyclefree 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 rdistinguishing 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 rdistinguishing }. 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 ngon. 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 ngon, 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 listdistinguishing 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 Ldistinguishabl 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 Ldi 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 listcoloring 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 kcolorable. On the other hand, the longstanding 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 listdistinguishing 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 indepth 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+2i, which is across from vi. There exists x E L( Vn+2i) such that x ::/= c; color Vn+2i 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 colorpreserving automorphism must map vi to VI, since it is the only vertex colored c. Therefore, either vi 1t Vn+2i or vi 1t 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 listdistinguishing, 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 listdistinguishing Brookstype 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. ktree Interval pGraphs In this chapter we give two characterizations. First we characterize ktrees interval pgraphs as spiny interior klobsters We next use this result to give a forbidden subgraph characterization of 2tree interval pgraphs. 2.1 Definitions and Background To describe the structure of ktrees, we use the generalized idea of a path introduced by Beineke and Pippert in [4]. Definition 2.1 A kpath of G is an alternating sequence of distinct kand (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 kcliques: eil and ei (I < i < p). The length of the kpath is the number p of (k +I)cliques. The letters e and t in the definition of a kpath are used to stand for edges and triangles, in the case of 2trees. This gives one good intuition for the structure of a 2path, a sequence of distinct edges and triangles. Although there is a unique path of length p up to isomorphism, this is not true for kpaths. For example, Przulj and Corneil [43] proved that there are three nonisomorphic 2paths of length five and six nonisomorphic 2paths of length six (See Figure 2.I) Drawing further parallels to trees, Proskurowski introduced the notion of a kcaterpillar in [42], and we introduce a spiny interior klobster. Before we do this, we classify some of the structure of a ktree I4.
PAGE 29
Figure 2.1: The three nonismnorphic 2paths of length five and six nonisomorphic 2paths of length six. A vertex v E V(G) is a kleaf of G if Na(v) is a clique. Let G beaktree and define G1 to be GPa, where Pais the set {v E V(G): vis a kleaf of G}; iteratively, G2 = G1Pa1. Suppose G is a ktree such that G2 is the kpath (eo, t1, e1, h, ... tp, ep), such that e0 and ep are defined in the following way. L e t a0 be a kleaf of G1 such that Na1(a0 ) C t1 and ap be a kleaf 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 kleaves in G and G1 respectively. 81 G = { v E V (G) : v is a kleaf of G N a ( v) =1e i ( 0 < i < p)}; 82G = {v E V(G1): vis a kleaf 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 2leaves of G1 x and z, respectively. For this 2tree, 81 G = {a, b, c, d, f, g, h, j} and 82G = 0 since the 2leaves of G1 are {x,y,z,u}, all of which are adjacent to some ei in G2. Definition 2.2 A 2caterpillar is a 2tree G such that G1 is a 2path. An interior 2caterpillar is a 2caterpillar G such that there does not exist a vertex a 15
PAGE 30
Figure 2.2: A 2tree with the 3cliques 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 2caterpillar but not an interior 2caterpillar, and HR is an interior 2caterpillar Although HL and HR in Figure 2.3 are 2caterpi.llars, HL is not an interior 2caterpillar for two reasons. First the vertex a is in the set al H L since it is a 2leaf 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 2caterpillar. Moreover the vertices x andy violate the second condition of being an interior 2caterpillar. 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 kcaterpillar 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 2caterpillar since all of the 2leaves are adjacent to the 'interior' edges of the 2path Hk. The first condition of being an interior kcaterpillar says that all kleaves are adjacent to interior cliques of the kpath G2. The second condition of being an interior kcaterpillar makes sure that nothing goes wrong at the ends of the kpath G2, since it deletes two vertices on either end of the longest kpath in the original graph G. This brings us to our next definition. Definition 2.3 A graph G is a klobster if G2 is a kpath. A spiny interior klobster is a klobster G with 82G = 0. Figure 2.4: On the left is a 2lobster that is not a spiny interior 2lobster, and on the right is a spiny interior 2lobster. Since caterpillar and lobster are names used to define trees, it seems natural to use the name klobster for ktrees. The modifier of interior is put on the klobster to signify that all kpaths of length 2 originate from the interior cliques of the kpath G2 in a spiny interior klobster (see vertex y in Figure 2.4). The word spiny is added to signify that there could be kleaves whose adjacency is not an interior clique (see vertex z in Figure 2.4). In the 2tree on the left in Figure 2.4, x E 82H, which is why it is not a spiny interior 2lobster. Another way to define a spiny interior is that G is a interior klobster if G1 is an interior kcaterpillar. It is well known that a tree is an interval graph if and only if it is a caterpillar [15]. However, a 2caterpillar 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 ktrees 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 kcaterpillar. Therefore, interior kcaterpillars are the class of ktrees that are interval graphs. We include a simplified proof for completeness. Theorem 2.4 If G is an interval ktree the n G is an interior kcaterpillar. Proof: Let G be a ktree that is not. an interior kcaterpillar and let P = (eo, t1, e1 ... tP, ep) be a longest kpath in G 1 such that e0 and e p ar e the neighborhoods of kleaves of G. Either G is not a kcaterpillar or it is a kcaterpillar that is not an interior kcaterpillar. If it is not a kcaterpillar then there is some vertex v that is not on P. If it is a kcaterpillar that is not an interior kcaterpillar, 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 kcaterpillar that is interior is violated; otherwise, the first condition of being a kcaterpillar 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 eib e i =/=Np(v). If no such v exists, then G is not a kcat e rpillar and there are two vertices a, bE V(G) such that Np(a) = e i for 1 < i < p1 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 eib ei =/=Np(v). Label z as the vertex not inti with ei1 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 kpath in G1. Label N p ( v) = 1, 2, .. k such that z is adjacent to 1, 2, .. k1 and w is adjacent to 2, 3, .. k. Notice that y is one of the vertices labeled as {3, ... k1}, 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 < p1 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 kpath in G1 and G is not an interior kcaterpillar. 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 pGraphs 19
PAGE 34
Now we turn our attention to interval pgraphs. Brown, Flink and Lundgren found in [13] that although interval pgraphs 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 prepresentation 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 pgraph. 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 cyclefree interval bigraphs and Theorem 2.4 as motivation, one might hope that either klobsters or interior k lobsters characterize ktrees that have an interval prepresentation. However, in Figure 2.4 the 2lobster on the left has an ATE Interior klobsters are interval pgraphs, but do not completely characterize the family. We now show that spiny interior klobsters characterize ktrees that have an interval prepresentation. Lemma 2.6 If G is a ktree that is not a spiny interior klobster then G con tains an asteroidal triple of edges. Proof: Let G be a ktree that it is not a spiny interior klobster. Let P = (e0 t1, ell ... tp, ep) be the longest kpath in G2, such that e0 and ep are the neighborhoods of kleaves of G1. It follows from the definition of a spiny 20
PAGE 35
interior klobster 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 klobster 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 ei1, 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 kpath 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 ei1 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 kpath 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 kpath 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 ktree G zs an interval pgraph if and only if it is a spzny interior klobster. Proof: Let G beaktree that has an interval prepresentation, and assume for contradiction that G is not a spiny interior klobster. By Lemma 2 .6, G contains an asteroidal triple of edges. By Theorem 2.5, interval pgraphs can not contain an ATE, which is a contradiction to our assumption. Suppose G is a spiny interior klobster. Let G2 = ( e 0 t 1,e1 ... ,tp,ep), where eo and ep are the neighborhoods of some kleaves of G1, g and h. La bel to = eo + g and tp+l = ep + h. Since g and h are kl e av e s of G1, the re must be kleaves 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 e2 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 kand k + 1cliqu e s (e2, t_l, e_I, to, eo, t1, e1, ... tp, ep, tp+b e p+l, tp+2, e p+2) is a longest kpath 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 = eil + ai and til = ei1 + bi1 assign ai the same color as bil 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 k1 possible unique neighborhoods for a kleaf, wi,1 ... wi,k1, such that N(wi,j) c ti, but N(wi, j) =f. ei or eil For each unique neighborhood there 23
PAGE 38
may be many kleaves, which all are assigned the same label. Assign the interval wi, j = ( i + 2fk_\), i + 2(/_1)) to each of these kleaves. Each kleaf 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 kleaves wi,1 ... wi,kl intersect, so no adjacencies result between them. Each kleaf is the color of the vertex that is not in its neighborhood. So although each kleaf's interval intersects all the intervals of the clique, adjacencies only result amongst each kleaf 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 kpaths 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 kleaves, 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 kleaves 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 kleaves 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 kleaves with the same label are the same color, so there is no resulting adjacency from their overlapping intervals. Therefore, we have a pinterval representation for the spiny interior klobster. 24
PAGE 39
a 112.1 m 3,1,1 h m '4,1,1 Figure 2.8: An example of a spiny interior 2lobster that is lab eled as in Theorem 2.7. Figure 2.8 gives a spiny interior 2lobster 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 prepresentation for the graph in Figure 2.8 based on the proof above. mJ.I.I11).1= m' r;;m;JmJ 1 2 1 1 '3,1,111)/= 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 prepresentation of the 2tree 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 ktree G is a spiny interior klobster 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 passignment. This is the minimal number of colors that can be used, since Kk+l is a subgraph of any nontrivial ktree. In fact, interval pgraphs 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 klobster, we can use a different color for each vertex of G1 since it is a interior kcaterpillar' 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 ktree G is an interval (k + 1)graph if and only if G zs a spiny interior klobster. 2.3 Forbidden Subgraph Characterization for 2Tree Interval pGraphs Next we use Theorem 2.7 to find a forbidden subgraph list for 2tree interval pgraphs. Recall that Przulj and Corneil found in [43] that 2trees PIGs have a large set of forbidden subgraphs, at least 62. For ktrees interval pgraphs the forbidden subgraph list also appears to be prohibitively long, so we restrict our 26
PAGE 41
Figure 2.10: Forbidden subgraphs for 2trees interval pgraphs. consideration to 2trees interval pgraphs. Theorem 2.10 A 2tree G has an interval prepresentation if and only if G contains no subgraph isomorphic to Gi, 1 < i < 12 in Figure 2.1 0. Proof: Let G be a 2tree that has an interval prepresentation. By Theorem 2. 7, G is a spiny interior 2lo bster. Consider the 2trees G i, 1 < i < 12 in Figure 2.10. The graphs c;, 1 < i < 10 are not 2paths, so Gi, 1 < i < 10 are not 2lobsters. In both G11 and G12, we have x, y, and z as the 2leaves 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 2lobsters. Therefore, G contains no subgraph isomorphic to Assume that G does not have an interval prepresentation. By Theorem 2.7, G is not a spiny interior 2lobster. Let P = (eo, t1 e1 ... tp, ep) be the a longest 2path in G2, such that e0 and ep are the neighborhoods of 2leaves of G1. It follows from the definition of a spiny interior 2lobster 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 eill 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 2lobster is if there exists a E V(G2)P such that Np(a) = ei for 1 < i < p1. 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) = tiz Thus ei1 = z + y, ei = x + z, and Np(a) = x + y. For eil and ei to be defined as such there must be vertices b, c distinct from x, y or z such that eil c Np(b) and ei C Np(c). Now the graph induced by the vertices {a,b,c,x,y,z} is a 3sun, 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 2tree interval pgraphs from Case 2 in Theorem 2.10. The graphs G11 and G12 are minimal; that is, the removal of any vertex creates an interval pgraph. Figure 2.13 gives two examples of G12 with a vertex removed and the corresponding interval prepresentation. Notice that G12 cis not a 2tree, but G12 e is a 2tree. ad 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 prepresentation. 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 prepresentation 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 2tree. If we were to remove a 2leaf from any graph of Gi, 1 < i < 10 the resulting graph would be a spiny interior 2lobster and hence hav e an inte rval prepresentation. Thus they are minimal in the sense that the removal of any vertex creates a subgraph that is either an interval pgraph or is not a 2tree. Minimality will be of more importance in Chapter 3. 31
PAGE 46
3. 2tree Probe Interval Graphs In this chapter we build on the structure of the spiny interior klobster introduced in the last chapter to characterize 2tree 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 2trees We let k = 2 in all of the definitions introduced in the second chapter. Although spiny interior 2lobsters characterize the 2trees that are interval pgraphs, the same is not true for 2trees that are probe interval graphs. Figure 3.1 gives three forbidden subgraphs for probe interval 2trees in [43], S25, S13 and S19. Each of Si5, Sfi, and Sf9 are 2paths. In addition the 2leaves of Sii and st;; are { x, y, z} and the 2leaves 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 2lobsters. However every PIG is an interval pgraph, so we look for a subset of spiny interior 2lobsters that characterize 2tree PIGs. This leads us to more definitions. Fif?ure 3.1: Three spiny interior 2lobsters that are not probe interval graphs in l43]. Suppose G is a 2tree such that G2 is the 2path (eo, t1,e1,t2, ... tP, ep) We classify the 2leaves 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 2leaves are of particular importance to us, we label some of the vertices of G2 as follows: W1(G) = {v E V(G2): Nc(x) = tiv 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 2lobster with the vertices and 3cliques of G2 labeled. Definition 3.1 Let G be a spiny interior 2lobster with G2 the 2path ( e0 t1, e1, t2, ... i]J,ep). If the following four conditions all hold then G is a sparse spiny interior 2lobster (ssi2lobster). 1. No ti, 1 < i < p, has two vertices in WW3 2. No ti, 1 < i < p, has two vertices X andy such that X E wW3 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 2tree in Figure 3.2 is not an ssi2lobster since t1 has two vertices in WW3 w1 and w2 The graphs A1 B and C in Figure 3.3 are sparse spiny interior 2lobsters. 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 ssi2lobster. 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 ssi2lobster. 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)+ bc = e0 + bc and Nc(g) = Nc2(b) + bc = e0 + bc, 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 ssi2lobster 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 ssi2lobster. In order to prove that ssi2lobsters are exactly the class of 2trees 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 2lobsters with the vertices and 3cliques 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 nonprobe. Corollary 3.3 [43] At least one asteroidal set of an asteroidal collection of a 35
PAGE 50
PIG G must consist entirely of nonprobes. 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 nonprobe internal vertex. Corollary 3.5 [43] There exists only one (P, N)partition of vertices of a 3sun up to isomorphism. Figure 3.8 gives the (P, N)partition of the 3sun from Corollary 3.5. We now prove a lemma that says that the vertices of W1 must be nonprobes. Lemma 3.6 Let G be a spiny interior 2lobster with a probe interval representation such that G2 = (eo, tl, el, t2, ... 'tp, ep) Any Wx E W1 must be a nonprobe. Proof: Let G be a spiny interior 2lobster with a probe interval representation such that G2 = (eo, t1, e1, t2, ... tp, ep), and let X E 8}G such that Nc(x) = tiWx. If i > 2 then let a E ti2ei2, and let bE tileiI If i = 2 let a be a 2leaf of G1 such that Nc1(a) = e0 and let b E t 1 e 1 If i = 1 then let b beakleaf 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 2leaf of G1 such that Nc1(d) = ep, and let c E tpep1 If i = p then let c be a 2leaf 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 ei1 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 nonprobes. Now consider the subgraph H induced by the vertices {b, c, r, s, x, wx}, which is isomorphic to the 3sun. By Corollary 3.5, since x must be a nonprobe, Wx must also be a nonprobe. Figure 3.4: Two labeled examples for Lemrpa 3.6. Figure 3.4 gives two ssi2lobsters 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 nonprobes of an induced subgraph that is common in 2trees. 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 nonprobe AT vertex u such that there exists a path between the other two AT vertices that avoids N(u) and has a nonprobe 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 nonprobe can be either b, .f, or c. Assume that b is the nonprobe 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========= cd 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 nonprobe 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 nonprobe and r t < rb, so if hE N then b tJ. N. ch======:= d b===::==== !====?= aFigure 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 nonprobes 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 nonprobe vertex being a, which forces b, c E P. By Lemma 3.4, we know that either d or f must be a nonprobe. Assume that f is a nonprobe, which means that d and g are probes. We also know from above that h must be a probe iff is a nonprobe, and thus the only vertices that are nonprobes 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 nonprobe. 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 nonprobe 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 3sun Figure 3.8: Graphs Q and the 3sun with their possible (P, N)partitions up to isomorphism. The white vertices are nonprobes, 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 2lobster with a probe interval representation such that G2 = (eo, ti, el, t2, ... 'tp, ep) Any Wy E W2 must be a nonprobe. Proof: Let G be a spiny interior 2lobster with a probe interval rep resentation such that G2 = (eo, t1, e1, t2, ... tp, ep) Let y E a; such that . : Nc2(y) = eiWy for Wy E W2(G); from the definition of W2 i #O,p. If i > 2 let a E ti_2 ei2 and let b E til eil If i = 2 let a be a 2leaf of G1 such that N01(a) = e0 and let b E t 1 e 1 If i = 1 let b be a 2leaf of G1 such 40
PAGE 55
that Nc1(b) =eo, and let a E BrG such that Nc(a) c (eo+ b). If i < p2 let c E ti+2ei+1, and let dE ti+3 ei+2 If i = p2 let d be a 2leaf of G1 such that Nc1(d)= ep, and let c E tpep_1 If i = pllet c be a 2leaf of G1 such that Nc1(c) = ep, and let dE BrG such that Nc(d) C (ep +c). Lets E tiei. Let r E ti+1 ei. Lastly, let Nc(y) = ei + uWy. 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 nonprobe Therefore, wy is a nonprobe. 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 nonprobes 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 nonprobe. 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 nonprobes 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 nonprobe. 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 nonprobe. Now consider subgraph induced by the vertices {r, b x, d1 Wx, wy} which is a 3sun with wy as a nonprobe. By Corollary 3.5 b must also be a nonprobe 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 nonprobe. However we already said 42
PAGE 57
that b must be a nonprobe, 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 2tree Characterization Now that we have established much of the structure of a probe interval 2tree, we proceed with the main result of this chapter. Lemma 3.11 Let G be a 2tree. If G is an ssi2lobster then G is a PIG. Proof: Suppose G is a sparse spiny interior 2lobster 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 epl as a). If not then by conditions 1, 2 and 3 of the definition of an ssi2lobster' 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) + ca = ep + ca, and label ep = a+ b. Now we let e2 = Y + z, t1 = x + y + z, e1 = 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 nonprobe. If w or a is in W1 U W2 U W3 then it will be a nonprobe; however, if it is just in W3 W3 then it will be a probe. By conditions 1, 2, 3 of the definition of an ssi2lobster, 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 nonprobe vertices; therefore from the definition of a 2tree, no two nonprobe 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 ssi2lobster. Thus this (P, N)partition has no adjacencies between nonprobe vertices. Now we must assign intervals using this (P, N)partition. Let G2* = (e2, t1, 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 nonprobes, so their intersecting intervals do not represent adjacencies. Since the spiny interior 2lobster is sparse, each Y(i,J,k) E M(i,j) in not adjacent to a distinct vertex of ei, which is a nonprobe. Therefore, no adjacency results between each Y(i,j,k) and its nonadjace,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 nonprobes, so their intersecting intervals do not result in an adjacency. Since G is an ssi2lobster, the vertex wi E ti such that wi : N02.. (c(i,j)) is the same for all j, and wi is a nonprobe 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 ssi2lobster 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 nonprobe, 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 nonprobe vertices in the same clique. Given w's labeling, X(1 1 ) could have been labeled 45
PAGE 60
Figure 3.11: A ssi2lobster with v e rtices labeled as in Lemma 3.11 as y. Notice on the other end of the 2tree 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 2leaves 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 nonprobe. 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 2leav 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 2leaf and its nonadjacency on G2 a nonprobe. This is the intuition for the ssi2lobster: you can' t have two of these nonadjacenc ie s for 2leaves in one clique because they must be nonprobes (although we have 46
PAGE 61
more flexibility at the ends of the 2path G2). =Jf!.l.li =Cro. l ) '16.2)= Xf/.1) "t(l.l) Ci6.1)= x(6.1J Yw \.j c z '1 a dX '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 2tree. G is a probe interval graph if and only if it is a ssi2lobster. Proof: Let G be a 2tree that has a probe interval representation. Assmne that it is not a ssi2lobster. Thus it is either not a spiny interior 2lobster or it is a spiny interior 2lobster that is not sparse. If it is not a spiny interior 2lobster then by Theorem 2.7 it is not an interval pgraph. Since probe inte rval graphs are contained in interval pgraphs, it is not a probe interval graph. Therefore, we assume that G is a spiny interior 2lobster that is not sparse. Let G2 = (eo, tb el, ... tp, ep). Either there is a ti with two vertices Wx and Wy in WW3 there is a ti with two vertices Wx and Wy such that Wx E WW3 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 nonprobes 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 WW3 d 3' an wy E W Without loss of generality, let Nc(Y) = Nc2(z) + zwy = ep + z wy and Nc(s) = Nc2(r)+rwy = ep+rwy 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 ei1 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 nonprobe (see A1 in Figure 3.13). By Lemmas 3.6 and 3.8, Wx is a nonprobe, 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 =10 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 nonprobe 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)+zwY = ei+zwy and Nc(s) = Nc2(r)+rwY = ei + rWy for y, s E oiG and distinct z, r E V(G), (i = 0 or i = p), and Nc(x) = Nc2(v)+vwx = ei+vwx and Nc(c) = Nc2(d)+dwx = ei+dwx for x, c E ofG and distinct v, d E V(G), (i = 0 or i = p). First consider the case that Wx + wy =1e0 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 nonprobes, which is a contradiction since they are adjacent. Therefore, let us assume without loss of generality that Wx + Wy = ep and that Wx :. epl 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 nonprobe. 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 nonprobe, d must be a probe. By Lemma 3. 7 this forces Wy to be a nonprobe, 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 nonprobes. 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 nonprobes, 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 nonprobe such that there exists a path between the other two ATvertices that avoids the neighborhood of the nonprobe and has a nonprobe internal vertex. Since g is adjacent to b which is a nonprobe, the nonprobe 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 nonprobe, 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)+vwx = ep+vwx and Nc(z) = Nc2(d)+dwz = ep+dwz 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)+cwy = e0+cwy and Nc(s) = Nc'l (r)+rwy = 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 nonprobe. The graph H induced by the vertices { Wy, Wz, Wx, v, z, x} is isomorphic to the 3sun. With wy already a nonprobe, we know that v must also be a nonprobe 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 tp1 = 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 nonprobe, but since a is adjacent to wy, the nonprobe must be either z or x. However, both z and x are adjacent to v, which has already been shown to be a nonprobe, 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 nonprobe. By Lemmas 3.6 and 3.8, if Wy E W1 u W2 then Wy is a nonprobe. In either case, there is a vertex r that is either a 2leaf 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 nonprobe, which is a contradiction. Since in every case we get a contradiction if G is not a sparse spiny interior 2lobster, then it is not a PIG. Figure 3.15: The graphs H1 S and G1 Now let G be a ssi2lobster. By Lemma 3.11 G has a probe interval r epre sentation. 3.3 Forbidden Subgraphs for Probe Interval 2trees 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 2trees. We have already given one new family of forbidden subgraphs for 2tree PIGS in Figure 3.10. If any v ertex is d e leted from the infinite family, the graph ceases to be a 2tree 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 2tree PIGs. 52
PAGE 67
Proof: Label H1 as in Figure 3.15 The removal of any 2leaf, {r, x, h, y,} results in a ssi2lobster; 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 2trees 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 2trees being ssi2lobsters, 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 2tress 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 2trees. Proof: In each 2tree Ni 1 < i < 6, t1 has two vertices in W2 Thus they are not ssi2lobsters 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 2tree 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, N1xis not a 2tree 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 2trees or they have probe interval presentations. For example, in Figure 3.19 N1 y is an ssi2lobster, 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 2tree 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 nonminimal forbidden subgraphs for probe interval 2trees. 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 2tree PIGs. 57
PAGE 72
4. Listdistinguishing Dihedral Graphs In this chapter, we begin investigations into the listdistinguishing number of a graph. We start by giving a listdistinguishing Brookstype 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 Brookstype 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 listdistinguishing 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) < Brookstype 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 Brookstype theorem for listdistinguishing 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 colorpreserving 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 colorpreserving 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 colorpreserving 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 colorpreserving automorphism. Thus the coloring so constructed is a listdistinguishing 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 Brookstype 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 listdistinguishing 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 an = e, T 2 = e and Ta= an1 7 It is important to note that there are three types of nontrivial subgroups of Dn The first is (aJ), which is a cyclic subgroup. The second is Dm = (aJ, Tai), where m divides n and the third is generated by an element of order two (Tai). 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 2listdistinguishing 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 colorpreserving 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 alataL = at and TaiatTai = O"nt, the conjugacy class of O"t in Dn is {at, O"nt}. 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 listcoloring framework. The intuition for the following proof comes from Proposition 1.6. Although an orbit of the forn1 0( u) = { u ua, ua2 uO"Jl} 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 2listdistinguishable. 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 ... ,uan1}. Either way, we have that O(u) = {u,ua,ua2 ... ,ua11 } 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 2listdistinguishing 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(!jl)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,uan2,uan3 } 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 2listdistinguishing 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 uan2 any color c f= Cu in L(uan2). 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 colorpreserving 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"n2 Since we have constructed our coloring so that U0"2 and UO"n2 have different colors, this yields a 2listdistinguishing 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 =/= uCJnI 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"n2 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"nl 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"n2 Thus as UO"n2 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"nI, implying that this coloring 2listdistinguishes 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 listdistinguishing 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"n2' UO"n3} ATO"i+3 = { U0"3 UO", u}. Therefore, we would like to choose colors x E L( UO") and y E L( UO"n2 ) 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"n2 ) = {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 2listdistinguishing coloring of O(u), as we cannot have L(ua) = L(uan2 ) = 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, uan2 uan3 } ATad1+i+3 = { ua3 ua, u}. Since j divides n and n is at least seven, uan3 =/= 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 2listdistinguished, we show that if a graph has one of these large orbits that the 2listdistinguishing coloring on the orbit can be extended to 2listdistinguish 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 2listdistinguishable and thus by Lemma 4.8, De(G) = 2. Therefore, assume St( u) = (rJJ, TrJi). Since 0( u) is 2listdistinguishable, 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 1orbits 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 listdistinguishing 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 2listdistinguishing 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 2listdistinguishable, 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 (aJ, Tai). 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 2orbits if n = 15; since 4 doesn't divide 30, there is no 4orbit if n = 30. If n = 12, 20, or 60, then there is no 2orbit, or we could choose a stabilizer from the 2orbit and 4orbit whose intersection is (a4 ). Then by Lemma 4.9, the intersection of the stabilizers from all orbits is the identity, and by Lemma 4.8 we can 2list distinguish G. Thus we can assume that, except for the 1orbits, 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 transitive 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 2listdistinguished 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 = ni (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(}nl} 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(}nl }. 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 2listdistinguish 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 2listdistinguish 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 2listdistinguish 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 listdistinguishing 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 vo2). 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 2listdistinguishes 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) = (o2 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 2listdistinguishes 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 3listdistinguished, 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 2list 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,uo2}. 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 2distinguish G with any 2coloring, as without loss of generality both uoand uo2 will receive the same color. However, then the automorphism cPu described above is nontrivial and colorpreserving, 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 2listdistinguishable (and hence 2distinguishable). 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 colorpreserving. 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 2listdistinguish 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 3listdistinguishable, 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 listdistinguishing coloring. Again we can easily 2listdistinguish 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 2distinguishable. In any 2coloring 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 colorpreserving regardless of how the remainder of G is colored. It follows that G is not 2listdistinguishable and, by our above observation, that G must therefore be 3listdistinguishable. 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 colorpreserving. It follows that G is 2listdistinguishable. 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 2listcoloring 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 2listdistinguish 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. ListDistinguishing Cartesian Products In this chapter we look at the listdistinguishing 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 listdistinguishing 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, ... ,giI,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 ddimensional 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 listdistinguishing 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 dl 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 listcoloring 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 = 2nel Albertson found that r!(n!Y < 2nrl 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 following lemma, which says that if we can 2listdistinguish any fiber of CnDCm in a specific way then the entire graph can be 2listdistinguished. 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 listdistinguished with a vertex that has a unique color in that fiber, then G can be listdistinguished. 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 'listcolor 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 'listcolor the rest of the vertices. Since they are the only two fibers with a vertex colored cl, must map to in any nontrivial colorpreserving automorphism; furthermore, has been listdistinguished, 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 listdistinguishing. 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 nontrivial 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 colorpreserving. 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 }. Then1 vertices of are colored with CI and the vertex ( UI, VI) is in fiber SO as in the previous paragraph, e) is not colorpreserving. Similarly, e) is not colorpreserving in Cases 2 and 3. Therefore in each of these cases, automorphisms of this type are not colorpreserving. 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 colorpreserving 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 listdistinguish CnDCm. If there exists a fiber that can be listdistinguished, 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 listdistinguished. 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 2listdistinguish 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 listdistinguishing coloring on that uses a unique color ci. By Lemma 5.6, we know that we can extend this coloring to a listdistinguishing 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 listdistinguishing coloring there is no colorpreserving automorphism of the form e). Since (u1 v1 ) is the only vertex with color c1 the only nontrivial 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 (d1)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, listdistinguishing 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 listdistinguishing 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 colorpreserving 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 colorpreserving permutation. Similarly, cell (2, 3) is the only cell in the first three columns that is not colored c2 in row 2. Thus any colorpreserving 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 colorpreserving 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 listdistinguishing 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 listdistinguishing 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 colorpreserving. Thus the columns are also fixed, so this is a listdistinguishing coloring. c, Cz C J Ctl c, q Ca ch c, c, c, cb c, c, Ca cb c, c, c1 jc1 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 1c1 A B c D E Figure 5.5: Examples of listdistinguishing 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 listdistinguishing coloring. In every case we are able to listdistinguish 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 ktrees that have interval prepresentations, one being a forbidden subgraph characterization for 2tree interval pgraphs. In [11] Brown gives a characterization of interval pgraphs based on an ordering of complete rpartite subgraphs (see Theorem 1.2) and a forbidden subgraph characterization of cyclefree interval pgraphs (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 3representation. 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 ATEfree graphs. Asteroidal triples of edges were enough to characterize the ktrees that have interval prepresentations; however, we know that ATEs do not completely characterize interval pgraphs. It would be 95
PAGE 110
interesting to determine what subset of the ATEfree graphs have an interval prepresentation. In chapter 3 we give a characterization of probe interval 2trees. The only forbidden subgraph characterization is of cyclefree probe interval graphs (see Theorem 1.3). There is still hope for the a forbidden subgraph characterization of probe interval 2trees. 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 2lobster to characterize the probe interval 2trees, and we believe this structure could be used to characterize ktrees with k < 3, with some tweaking of the definition. Thus we conjecture the following. Conjecture 6.1 Let G be a ktree. G is a probe interval graph if and only if it is a spare spiny interior klobster. 6.2 Symmetries In chapter 4 we found that the listdistinguishing 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 listdistinguishing number of classes of graphs for which the distin guishing number is known. In chapter 5 we investigated the listdistinguishing 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 listdistinguishing 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(13):29 35, 2004. [7) B. Bolloba,s and A. J. Harris. Listcolourings of graphs. Graphs Combin., 1(2): 115 127, 1985. [8) Debra L. Boutin. Small label classes in 2distinguishing 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 Thirtythird 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 Thirtythird 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 Thirtysecond 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 cyclefree 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 Thirtys 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, TsaiLien 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] InJen Lin, Malay K. Sen, and Douglas B. West. Classes of interval di graphs and 0, 1matrices. In Proceedings of the Twentyeighth 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(13):315 324, 1998. [ 41] Haiko M tiller. Recognizing interval digraphs and interval bigraphs in poly nomial time. Discrete Appl. Math., 78(13):189 205, 1997. [42] Andrzej Proskurowski. Separating subgraphs in ktrees: cables and cater pillars. Discrete Math., 49(3):275 285, 1984. [43] Nata8a Przulj and Derek G. Corneil. 2tree probe interval graphs have a large obstruction set. Discrete Appl. Math., 150(13):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
