Citation |

- Permanent Link:
- http://digital.auraria.edu/AA00007312/00001
## Material Information- Title:
- On characterizations and structure of interval digraphs and unit probe interval graphs
- Creator:
- Dasgupta, Shilpa
- Place of Publication:
- Denver, CO
- Publisher:
- University of Colorado Denver
- Publication Date:
- 2012
- Language:
- English
## Thesis/Dissertation Information- Degree:
- Doctorate ( Doctor of philosophy)
- Degree Grantor:
- University of Colorado Denver
- Degree Divisions:
- Department of Mathematical and Statistical Sciences, CU Denver
- Degree Disciplines:
- Applied mathematics
- Committee Chair:
- Lundgren, J. Richard
- Committee Members:
- Jacobson, Michael S.
Ferrara, Michael Cherowitzo, William E. Brown, David E.
## Record Information- Source Institution:
- University of Colorado Denver
- Holding Location:
- Auraria Library
- Rights Management:
- Copyright Shilpa Dasgupta. Permission granted to University of Colorado Denver to digitize and display this item for non-profit research and educational purposes. Any reuse of this item in excess of fair use or other copyright exemptions requires permission of the copyright holder.
## Auraria Membership |

Downloads |

## This item has the following downloads: |

Full Text |

ON CHARACTERIZATIONS AND STRUCTURE OF INTERVAL DIGRAPHS
AND UNIT PROBE INTERVAL GRAPHS by Shilpa Dasgupta M.S., University of Colorado Denver, 2007 A thesis submitted to the Faculty of the Graduate School of the University of Colorado in partial fulfillment of the requirements for the degree of Doctor of Philosophy Applied Mathematics 2012 This thesis for the Doctor of Philosophy degree by Shilpa Dasgupta has been approved by J. Richard Lundgren, Advisor and Chair Michael S. Jacobson Michael Ferrara William E. Cherowitzo David E Brown Date n Dasgupta, Shilpa (Ph.D., Applied Mathematics) On Characterizations and Structure of Interval Digraphs and Unit Probe Interval Graphs Thesis directed by Professor J. Richard Lundgren ABSTRACT Interval graphs and their variations have been studied extensively for the last 50 years from both a theoretical standpoint and due to their importance in applications. In this thesis we will explore several variations of interval graphs and unit interval graphs including interval digraphs, interval bigraphs and probe interval graphs. Interval graphs were mathematically introduced by Hajos [22], The origin of interval graphs may also be regarded as an application to the research of Benzer in 1959 [1] in his study of the structure of bacterial genes. Many nice characterizations have been found for interval graphs, but the same cannot be said about the various generalizations. The work presented in this thesis will indicate that characterization of the broadest classes of the generalizations poses a very difficult problem and so the focus in this thesis is on subclasses of interval digraphs, interval bigraphs, and probe interval graphs. Interval digraphs were introduced by Sen et al. in [39] (1989). In 1998 West gave adjacency matrix characterizations of interval digraphs and unit interval digraphs [42], So far, in the most generic sense, no forbidden subgraph characterization of interval digraphs has been been found, but those tournaments which are interval digraphs have been characterized in various ways by Brown, Busch and Lundgren in 2007. In this thesis we generalize some of their results to other classes of interval digraphs. A natural extension of interval graphs, called interval bigraphs, were introduced by Harary, Kabell, and McMorris [23] in 1982. Unit and proper interval graphs were iii introduced and characterized by Roberts in 1969 [36]. He proved that the classes of proper interval graphs and unit interval graphs coincide. Proskurowski and Telle [33] extended the idea of proper interval graphs to p-proper interval graphs. Recently Beyerl and Jamison introduced p-improper interval graphs. They focussed on a special case of p-improper interval graphs. Here we generalize and obtain similar results for p-improper interval bigraphs. The probe interval graph was invented in order to aid with the task called physical mapping faced in connection with the human genome project, cf. work of Zhang and Zhang et al. [43], [45], [44], No generalized characterization of probe interval graphs have been found so far. Li Sheng first characterized probe interval graphs for trees[41], Following this characterization of cycle-free probe interval graphs, in 2009 Brown, Sheng and Lundgren gave a characterization for cycle-free unit probe interval graphs [15]. Recently Brown and Langley characterized unit probe interval graphs for bipartite graphs [10]. In this thesis we give a characterization of 2-trees that are unit probe interval graphs. In 2005 Przulj and Cornell found at least 62 distinct minimal forbidden induced subgraphs for probe interval graphs that are 2-trees [34], More recently Brown, Flesch and Lundgren extended the list to 69 and also gave a characterization [7]. In this thesis we follow the idea of Przulj and Cornell for the next best case which is for 2-trees. The restriction to 2-trees is a reasonable thing to do because of the progression of the Sheng, Brown-Sheng-Lundgren, and Brown-Langely results, and also because of the Corneil-Przulj and Brown-Flesch-Lundgren results. We first characterize 2-caterpillars and interior 2-caterpillars in terms of forbidden induced subgraphs and show that 2-trees that are unit probe interval graphs have to be interior 2-caterpillars. Then we look at 2-paths that are unit probe interval graphs and characterize them. Using similar ideas we subsequently characterize interior 2-caterpillar which are unit probe interval graphs. Finally we use these results to get a complete characterization of 2-trees which are unit probe interval graphs. IV The form and content of this abstract are approved. I recommend its publication. Approved: J. Richard Lundgren v DEDICATION Mom and dad and my sweethearts Isha, Sheila, Anoushka and Bubai. ACKNOWLEDGMENTS First of all I would like to thank my adviser, Dr. J. Richard Lundgren, for guiding, mentoring and engaging me in mathematics. I would also like to thank my professors, friends and colleagues with whom Iâ€™ve worked over the past few years. Lastly, and certainly most importantly, I thank my family, especially my sister for her love and support. Vll TABLE OF CONTENTS Figures .................................................................... ix 1. Introduction................................................................ 1 1.1 Background................................................................ 1 1.2 Introduction to the research.............................................. 5 2. Interval Digraphs........................................................... 7 2.1 Introduction.............................................................. 7 2.2 Motivation from Interval Tournaments..................................... 11 2.3 Digraphs with a Transitive (n â€” 2)- subtournament........................ 14 2.4 More than one nontrivial strong component ............................... 22 3. Interval Bigraph Impropriety.............................................. 27 3.1 Introduction............................................................. 27 3.2 Impropriety and Weight of Interval Bigraphs.............................. 29 3.3 p-critical interval bigraphs............................................. 36 3.4 Conclusions and future work.............................................. 47 4. Characterization of unit probe interval 2-trees.......................... 48 4.1 Introduction............................................................. 48 4.2 Preliminaries............................................................ 49 4.3 Characterization of 2-caterpillars....................................... 56 4.4 Forbidden subgraphs for 2-paths which are unit probe interval graphs . . 61 4.5 2-path unit probe interval graph characterization........................ 70 4.6 forbidden subgraphs for interior 2-caterpillars which are unit probe interval graphs ............................................................ 119 4.7 Characterization of interior 2-caterpillars which are unit probe interval graphs ............................................................ 130 References.................................................................. 172 viii FIGURES Figure 2.1 Interval digraph............................................................... 9 2.2 Zero partition................................................................ 10 2.3 Interval bigraph.............................................................. 10 2.4 Insect........................................................................ 11 2.5 Bigraph representation of a digraph........................................... 11 2.6 D-v........................................................................... 13 2.7 ATE in the bigraph............................................................ 15 2.8 6-cycle....................................................................... 16 2.9 10-cycle...................................................................... 16 2.10 Induced 6-cycle in the bigraph representation................................ 17 2.11 More restrictions on the arcs ....................................... 17 2.12 Example of a digraph satisfying a condition of the theorem 2.3.1 and its zero partition .............................................................. 25 2.13 Example of a digraph satisfying a condition of the theorem 2.3.2 and its zero partition............................................................... 26 2.14 Example of a digraph that fails the hypothesis of theorem 2.3.2 since v beats vâ€ and hence forms a 6-cycle in its bigraph representation......... 26 2.15 Strong components............................................................ 26 3.1 K1>3.......................................................................... 29 3.2 p-Improper Interval Graph .................................................... 30 3.3 0-Improper Interval Bigraph ....................................... 30 3.4 Forbidden subgraphs for proper Interval bigraph with their interval representations to force containment from X .................................. 31 3.5 Interval representations of Bl, B2, B3 to force containment from Y . . . 31 3.6 Impropriety of imp(B(f>1) = 2, imp(B(f>2) = 1................................. 33 IX 3.7 Exterior local components .................................................. 33 3.8 Interval bigraph with impropriety 1 34 3.9 Interval bigraph with impropriety 2 34 3.10 Calculation of weight ..................................................... 35 3.11 Interval bigraph with weight 2 35 3.12 Changes in weight due to variation in definition .......................... 37 3.13 Interval bigraph where wt(X) = 0 < irrip(B) = 1 37 3.14 Interval bigraph where wt(X) = 1 = irrip(B) = 1 38 3.15 Illustrations of balance and p-criticality ................................ 39 3.16 Choice..................................................................... 40 3.17 Possible structures of an interval bigraph with a balanced and p-critical partite set................................................................ 44 4.1 Examples of some 2-paths.................................................... 50 4.2 On the left is a 2-caterpillar, and on the right is an interior 2-caterpillar 51 4.3 4-fan....................................................................... 53 4.4 Unit probe interval representation of a 4-fan............................... 53 4.5 An illustration where unit probe interval representation of a 4-fan fails to work....................................................................... 53 4.6 FI.......................................................................... 54 4.7 Probe interval representation of a 3-sun or FI.............................. 55 4.8 El.......................................................................... 56 4.9 Forbidden subgraphs for 2-caterpillar ...................................... 58 4.10 Construction 1............................................................ 58 4.11 Construction 2............................................................ 59 4.12 Construction 3............................................................ 59 4.13 Six 2-trees called Ai s ................................................... 60 4.14 F2...................................................................... 63 x 4.15 F3......................................................................... 63 4.16 F4......................................................................... 64 4.17 F5......................................................................... 65 4.18 F6......................................................................... 66 4.19 F7......................................................................... 67 4.20 F8......................................................................... 67 4.21 F9......................................................................... 68 4.22 F10 ....................................................................... 69 4.23 Fll ....................................................................... 70 4.24 Non-isomorphic 2-paths of length 6......................................... 72 4.25 Construction that shows possible merge of two-4-fans....................... 73 4.26 Construction of two edge-consecutive 4-fans................................ 76 4.27 All possible two edge-consecutive 4-fans and their representations .... 76 4.28 Formation of three edge-consecutive-4-fans................................. 77 4.29 Formation of three edge-consecutive-4-fans................................. 77 4.30 Formation of three edge-consecutive-4-fans................................. 78 4.31 three edge-consecutive-4-fans ............................................. 78 4.32 Formation of two vertex-consecutive-4-fans................................. 80 4.33 The only structure possible for two vertex-consecutive-4-fans.............. 80 4.34 Representations of three vertex-consecutive-4-fans......................... 81 4.35 Another representation of three vertex-consecutive-4-fans.................. 81 4.36 Three possible structures of two edge-consecutive 4-fans .................. 82 4.37 Straight 2-path............................................................ 83 4.38 Staircase.................................................................. 84 4.39 2-snake ................................................................... 84 4.40 Extended-staircase+staircase .............................................. 85 4.41 Staircase representation................................................... 85 xi 4.42 2-snake representation.................................................... 86 4.43 extended-staircase+staircase representation............................... 86 4.44 Four edge-consecutive 4-fans, structure 1................................. 91 4.45 Four edge-consecutive 4-fans, structure 2................................. 92 4.46 Four edge-consecutive 4-fans, structure 3................................. 92 4.47 Example of merges for different values of n .............................. 97 4.48 n = 1 : edge-consecutive merge for 2-paths.............................. 97 4.49 n = 1 : edge-consecutive merge for 2-paths.............................. 98 4.50 n = 1 : edge-consecutive merge for 2-paths.............................. 99 4.51 n = 2 : edge-consecutive merge for 2-paths.............................. 100 4.52 n = 2 : edge-consecutive merge for 2-paths.............................. 101 4.53 n = 2 : edge-consecutive merge for 2-paths.............................. 101 4.54 n = 2 : edge-consecutive merge for 2-paths.............................. 102 4.55 n = 2 : edge-consecutive merge for 2-paths.............................. 103 4.56 n = 3 : edge-consecutive merge for 2-paths ............................. 103 4.57 n = 3 : edge-consecutive merge for 2-paths ............................. 104 4.58 n = 3 : edge-consecutive merge for 2-paths.............................. 104 4.59 n = 0 : vertex-consecutive merge for 2-paths............................ 108 4.60 n = 1 : vertex-consecutive merge for 2-paths............................ 109 4.61 n = 2 : vertex-consecutive merge for 2-paths............................ 110 4.62 n = 3 : vertex-consecutive merge for 2-paths ..................... 110 4.63 vertex-consecutive-edge-consecutive for 2-path........................... 112 4.64 vertex-consecutive-edge-consecutive for 2-path........................... 113 4.65 n = 1 : vertex-consecutive-edge-consecutive for 2-path.................. 113 4.66 n = 2 : vertex-consecutive-edge-consecutive for 2-path.................. 114 4.67 n = 2 : vertex-consecutive (2-snake)-edge-consecutive for 2-path........ 114 4.68 Straight-2-path+end-2-leaves ............................................ 116 xii 4.69 Staircase+end-2-leaves ................................................... 117 4.70 2-snake+end-2-leaves...................................................... 118 4.71 Non-probe restriction in 4-fans .......................................... 120 4.72 Non-probe restriction .................................................... 121 4.73 Unit probe interval representation ....................................... 122 4.74 3-fan with a 2-leaf....................................................... 122 4.75 E2........................................................................ 123 4.76 probe interval representation for E2...................................... 123 4.77 E3........................................................................ 124 4.78 E4........................................................................ 125 4.79 E5........................................................................ 126 4.80 Probe interval representation of E5....................................... 126 4.81 E6........................................................................ 127 4.82 Probe interval representation of E6....................................... 127 4.83 E7........................................................................ 128 4.84 E8........................................................................ 129 4.85 E9........................................................................ 129 4.86 E10 ...................................................................... 130 4.87 Group-Ell- ul,u2 are end 2-leaves of Â£>* and Bj ...................... 131 4.88 Possible places of 2-leaves............................................... 132 4.89 Representation of 2-snake with all possible 2-leaves...................... 133 4.90 Representation of extended staircase with all 2-leaves ................... 133 4.91 Representation of staircase with all 2-leaves............................. 134 4.92 Representation of vertex-consecutive 4-fans with all 2-leaves............. 134 4.93 Representation of 2-snake with all 2-leaves............................... 135 4.94 Representation of extended-staircase and staircase with all 2-leaves ... 135 4.95 Edge-consecutive 4-fans with all 2-leaves................................. 136 xiii 4.96 4-fan with all 2-leaves .............................................. 136 4.97 Vertex consecutive 4-fans with all 2-leaves........................... 142 4.98 n = 1 : h............................................................. 150 4.99 n = 1 : h............................................................. 151 4.100n = 2: h............................................................. 152 4.101 n = 3 : h............................................................. 153 4.102n = 4 : /i............................................................. 154 4.103 Representation of straight 2-path with all 2-leaves ................. 154 4.104n = 0 : I2............................................................. 159 4.105n =1: I2............................................................. 160 4.106n = 2: I2............................................................. 160 4.107n = 3 : I2............................................................. 161 4.108n = 0 : h............................................................. 165 4.109n = 1 : h............................................................. 166 4.110ra = 2: h............................................................. 166 4.111 Interior 2-caterpillars with fewer 2-leaves .......................... 167 xiv 1. Introduction 1.1 Background Interval graphs and their variations have been studied extensively for the last 50 years from a theoretical standpoint and due to their importance in applications. In this thesis we will explore several variations of interval graphs namely interval digraphs, interval bigraphs and probe interval graphs. The work on interval bigraphs will focus on p-improper interval bigraph and the work on probe interval graphs will be on unit probe interval graphs. Let a graph G have vertex set V(G) and edge set E(G). If x,y E V(G) are adjacent, then we denote xy E E(G). If G is bipartite, we denote the partitions of the vertex set as V(G) = {X Ub}. 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 Ix H Iy ^ 0. Interval graphs were theoretically introduced in 1957 by Hajos [22] and also appeared in applied research by Benzer in 1959 [1] in his study of the structure of bacterial genes. Interval graphs were characterized by the absence of induced cycles larger than 3 and asteriodal triples by Lekkerkerker and Boland [26] 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 in G that avoids all neighbors of the third. Other useful characterizations of interval graphs were given by Gilmore and Hoffman in 1964 [19] and Fulkerson and Gross [17]. Extensive study and research has been done on interval graphs for several decades by both mathematicians and computer scientists. These graphs are used to provide numerous models in diverse areas such as genetics, psychology, sociology, archaeology, or scheduling. For more details on interval graphs and their applications, see books by Roberts [36], Golumbic [20] and Mckee and McMorris [29]. Interval digraphs were introduced by Sen et al. in [39](1989). Langley, Lundgren, Merz gave results on Competition Graphs of Interval Digraphs (1995) in [25]. They 1 showed that the competition graph of an interval digraph is an interval graph and that every interval graph is in fact the competition graph of some interval digraph. Lin, Sen and West gave some interesting results on Interval digraphs and (0,l)-matrices in [27]. In 1998 West gave adjacency matrix characterizations of interval digraphs and unit interval digraphs [42], At this point there is no forbidden subgraph characterization of interval digraphs, but recently, in 2007, interval tournaments were characterized by a complete list of forbidden subtournaments by Brown, Busch, and Lundgren [6]. In chapter 2 we generalize some of the results from this paper. A natural extension of interval graphs, called interval bigraphs, were introduced by Harary, Kabell, and McMorris [23] in 1982. Let G be a bipartite graph with bipartition X U Y; we may write G = (X, Y, E) to denote this. A bipartite graph G is an interval bigraph if to every vertex, v G V(G), we can assign an interval of the real line, Iv, such that xy G E(G) if and only if Ix C\Iy yt 0 and x G X and y eY. Interval bigraphs have been studied by several authors ([9], [14], [23], [24], [27], and [31]). Initially it was thought that the natural extension of asteriodal triples of vertices to asteriodal triples of edges along with induced cycles larger than 4 would give a forbidden subgraph characterization [23]. However, Muller [31] found insects and Hell and Huang [24] found edge asteriods and bugs as forbidden subgraphs, and to date a complete characterization remains elusive. Three edges a, c and e of a graph G form an asteriodal triple of 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 the third edge. Cycle free interval bigraphs were characterized by Brown et al in 2001 [14], and ATEs played a significant role in that characterization. In 2002 a generalization of interval bigraph called an interval fc-graph was introduced by Brown et al [8]. More recently, in 2010, Lundgren and Tonnsen characterized 2-trees that are interval fc-graphs [28]. 2 A graph is a probe interval graph if there is a partition of V(G) into sets P and N and a collection {Iv : v G V(G)} of intervals of R such that, for u,v G V(G), uv G E(G) if and only if Iu n Iv ^ (f) and at least one of u or v belongs to P. The sets P and N are called the probes and nonprobes, respectively. An interval graph is a probe interval graph with an empty non-probe set and this class of graphs has been studied extensively. The probe interval graph model was invented in order to aid with the task called physical mapping faced in connection with the human genome project (cf. work of Zhang and Zhang et al. [43], [45], [44]). The paper by Mc-Morris, Wang and Zhang [30] has results similar to those for interval graphs found in [17] by Fulkerson and Gross and [20] by Golumbic. For example interval graphs are chordal while probe interval graphs are weakly chordal and maximal cliques are consecutively orderable in interval graphs while quasi-maximal cliques works in probe interval graphs. In 1999 Li Sheng first characterized cycle-free probe interval graphs [41] The classes of graphs related to probe interval graphs are discussed in [11] by Brown and Lundgren, [8] by Brown, Flink and Lundgren, and [21] by Golumbic and Lipshteyn. Relationships between bipartite probe interval graphs, interval bigraphs and the complements of circular arc graphs are presented in [11], The problem of characterizing generic probe interval graphs in terms of forbidden subgraphs for now appears to be difficult. Since trees were the only class of graphs where probe interval graphs were characterized, a natural next step was to look at a class of 2-trees. In 2005 Przulj and Corneil attempted a forbidden subgraph characterization of 2-trees that are probe interval graphs and they found at least 62 distinct minimal forbidden induced subgraphs for probe interval graphs that are 2-trees [34], More recently Brown, Flesch and Lundgren extended the list to 69 and gave a characterization in terms of sparse spiny interior 2-lobsters [7]. In the last 40 years a subclass of interval graphs has been investigated and studied 3 extensively. This class is the class of unit interval graphs introduced by Roberts in 1969. A unit interval graph is an interval graph with all intervals in some interval representation having the same length. A proper interval graph is an interval graph for which there is an interval representation with no interval properly containing another. Roberts [36] proved that the classes of proper interval graphs and unit interval graphs coincide and he showed that interval graphs that contain no Jd1;3 are unit interval graphs. In 1999 Bogart and West gave a shorter proof of the same result of the equality of proper and unit for interval graphs [4], They gave a constructive proof of this result, where proper intervals are gradually converted into unit intervals. Much more recently in 2007 Gardi gave a much shorter new constructive proof of Roberts original characterization of unit interval graphs [18]. A unit interval bigraph is an interval bigraph with all intervals in some interval representation having the same length and a proper interval bigraph is an interval bigraph for which there is an interval representation with no interval containing another properly. Several characterizations of proper interval bigraphs have been found in the last decade including one by Lin and West [27]. The idea of proper interval graphs was naturally extended to p-proper interval graphs by Proskurowski and Telle [33]. The p-proper interval graphs are graphs which have an interval representation where no interval is properly contained in more than p other intervals. Any 0-improper interval graph is a proper interval graph and it is easy to check that X13 is a is a 1-improper interval graph. In chapter 3 we will generalize the class of p-improper interval graph to p-improper interval bigraph. Unit interval digraphs were characterized in 1997 by Lin et al [27]. In 2002, Brown et al [9] conjectured a characterization of unit interval bigraphs. This conjecture was proved by Hell and Huang [24] in 2004. More recently in 2011 Brown and Lundgren gave several additional characterization of unit interval bigraphs [12], Currently Brown, Flesch and Lundgren are working on unit interval fc-graphs for 2-trees. Following up Shengâ€™s characterization of cycle-free 4 probe interval graphs, in 2009, Brown, Lundgren and Sheng gave a characterization of cycle-free unit probe interval graphs [15]. Two natural extensions arise, the first is to characterize bipartite graphs that are unit probe interval graphs and secondly to characterize 2-trees that are unit probe interval graphs. Recently Brown and Langley characterized unit probe interval graphs for bipartite graphs [10]. In chapter 4 we give a characterization of 2-trees that are unit probe interval graphs. 1.2 Introduction to the research We will introduce notation as we move through the thesis. At the initial stage we will use conventional definitions. As mentioned earlier the study of interval graphs has long been a much researched area in Graph Theory. The majority of work in this thesis is an effort to characterize various classes of variations of interval graphs and unit interval graphs. In chapter 2 we study different classes of digraphs and determine the scenarios when they are bound to be interval. Since the problem of finding a complete characterization of interval digraphs is extremely difficult, we concentrate on specific classes of interval digraphs. We focus our research in this chapter on a paper of Brown, Busch, and Lundgren [6] where a complete characterization of interval tournaments is found. We look at oriented graphs with certain properties and fold restrictions that need to be imposed on its structure for it to be interval. We fold several classes of directed graphs on n vertices which are interval with restrictions such as containing transitive sub-tournaments on (n â€” 2) or (n â€” 1) vertices and specific adjacencies between vertices. As stated earlier, another natural extension of interval graphs, called interval bigraphs, were introduced by Harary, Kabell, and McMorris in 1982. The p-improper interval graphs, where no interval contains more than p other intervals, were investigated by Beyerl and Jamison [3]. In chapter 3 we extend the idea by introducing p-improper interval bigraphs, where no interval contains more than p other intervals of the same partite set. In this chapter we determine restrictions on the structure of 5 an interval bigraph for it to be a p-improper interval bigraph. We also study special classes of p-improper interval bigraphs. In chapter 4, we look at unit probe interval graphs. Since they have been characterized for trees and bipartite graphs , we follow the techniques of Przulj and Corneil for the next best case which is for 2-trees. We characterize 2-trees that have a unit probe interval representation. In order to accomplish this we first characterize 2-caterpillars and interior 2-caterpillars in terms of forbidden induced subgraphs and show that 2-trees that are unit probe interval graphs have to be interior 2-caterpillars. At this point we realized that the problem was much more difficult than we originally anticipated it to be. So we look at 2-paths that are unit probe interval graphs and characterize them. Then we use this characterization to fold the characterization of interior 2-caterpillar which are unit probe interval graphs. Finally we use these results to get a complete characterization of 2-trees which are unit probe interval graphs. 6 2. Interval Digraphs 2.1 Introduction A directed graph, or digraph is a graph in which each edge is assigned a direction. An arc (directed edge) from vertex u to vertex v will be denoted u w, and we will say that u beats v. The set of vertices of a digraph D will be denoted V(D), and its size will be denoted | V(D) |. A subdigraph of D is a digraph consisting of a subset of V(D), with only arcs from D between the vertices in this subset. Throughout this paper, we will only be considering digraphs that have no 2- cycles or loops; so for two vertices u,v E V(D), if u iâ€”> v, then we cannot have v iâ€”> u, or u = v A tournament T is an oriented complete graph, so for any x,y E V(T) either x i y y or y i y x, but never both, and x e-> x can never happen. An interval tournament is a tournament that is an interval digraph. Naturally a subtournament of some digraph D is a subdigraph of D that happens to be a tournament. A directed graph D is an interval digraph if for each vertex u there corresponds an ordered pair of intervals (SU,TU) such that for any two vertices u,v E V(D), u iâ€”y Vj if and only if Su fl Tv yt
7
Case II: If v G X has exactly 1 exterior component then it has a non-exterior side component. Let Cn be the exterior component. Again by Lemma 3.3.6 it must have at least 2 focal components Cj and C\ such that \C\ fl X\ = \CjC\X\ > \Ci fl X\ for all i = 2...., (n â€” 1) and one of these, say C\, must be the focal side component. Thus B ~ Â£>2. By arguments similar to those used in Case I, C\ also has a vertex from Y which is adjacent to all vertices from X inC\. This is illustrated in Figure 3.17. |

Full Text |

PAGE 1 ONCHARACTERIZATIONSANDSTRUCTUREOFINTERVALDIGRAPHS ANDUNITPROBEINTERVALGRAPHS by ShilpaDasgupta M.S.,UniversityofColoradoDenver,2007 Athesissubmittedtothe FacultyoftheGraduateSchoolofthe UniversityofColoradoinpartialfulllment oftherequirementsforthedegreeof DoctorofPhilosophy AppliedMathematics 2012 PAGE 2 ThisthesisfortheDoctorofPhilosophydegreeby ShilpaDasgupta hasbeenapproved by J.RichardLundgren,AdvisorandChair MichaelS.Jacobson MichaelFerrara WilliamE.Cherowitzo DavidEBrown Date ii PAGE 3 Dasgupta,ShilpaPh.D.,AppliedMathematics OnCharacterizationsandStructureofIntervalDigraphsandUnitProbeInterval Graphs ThesisdirectedbyProfessorJ.RichardLundgren ABSTRACT Intervalgraphsandtheirvariationshavebeenstudiedextensivelyforthelast50 yearsfrombothatheoreticalstandpointandduetotheirimportanceinapplications. Inthisthesiswewillexploreseveralvariationsofintervalgraphsandunitinterval graphsincludingintervaldigraphs,intervalbigraphsandprobeintervalgraphs.IntervalgraphsweremathematicallyintroducedbyHajos[22].Theoriginofinterval graphsmayalsoberegardedasanapplicationtotheresearchofBenzerin1959[1] inhisstudyofthestructureofbacterialgenes.Manynicecharacterizationshave beenfoundforintervalgraphs,butthesamecannotbesaidaboutthevariousgeneralizations.Theworkpresentedinthisthesiswillindicatethatcharacterizationof thebroadestclassesofthegeneralizationsposesaverydicultproblemandsothe focusinthisthesisisonsubclassesofintervaldigraphs,intervalbigraphs,andprobe intervalgraphs. IntervaldigraphswereintroducedbySenetal.in[39].In1998Westgave adjacencymatrixcharacterizationsofintervaldigraphsandunitintervaldigraphs [42].Sofar,inthemostgenericsense,noforbiddensubgraphcharacterizationof intervaldigraphshasbeenbeenfound,butthosetournamentswhichareintervaldigraphshavebeencharacterizedinvariouswaysbyBrown,BuschandLundgrenin 2007.Inthisthesiswegeneralizesomeoftheirresultstootherclassesofinterval digraphs. Anaturalextensionofintervalgraphs,calledintervalbigraphs,wereintroduced byHarary,Kabell,andMcMorris[23]in1982.Unitandproperintervalgraphswere iii PAGE 4 introducedandcharacterizedbyRobertsin1969[36].Heprovedthattheclassesof properintervalgraphsandunitintervalgraphscoincide.ProskurowskiandTelle[33] extendedtheideaofproperintervalgraphstop-properintervalgraphs.Recently BeyerlandJamisonintroducedp-improperintervalgraphs.Theyfocussedonaspecialcaseofp-improperintervalgraphs.Herewegeneralizeandobtainsimilarresults forp-improperintervalbigraphs. Theprobeintervalgraphwasinventedinordertoaidwiththetaskcalledphysicalmappingfacedinconnectionwiththehumangenomeproject,cf.workofZhang andZhangetal.[43],[45],[44].Nogeneralizedcharacterizationofprobeinterval graphshavebeenfoundsofar.LiShengrstcharacterizedprobeintervalgraphsfor trees[41].Followingthischaracterizationofcycle-freeprobeintervalgraphs,in2009 Brown,ShengandLundgrengaveacharacterizationforcycle-freeunitprobeinterval graphs[15].RecentlyBrownandLangleycharacterizedunitprobeintervalgraphs forbipartitegraphs[10].Inthisthesiswegiveacharacterizationof2-treesthatare unitprobeintervalgraphs.In2005PrzuljandCorneilfoundatleast62distinct minimalforbiddeninducedsubgraphsforprobeintervalgraphsthatare2-trees[34]. MorerecentlyBrown,FleschandLundgrenextendedthelistto69andalsogavea characterization[7].InthisthesiswefollowtheideaofPrzuljandCorneilforthenext bestcasewhichisfor2-trees.Therestrictionto2-treesisareasonablethingtodo becauseoftheprogressionoftheSheng,Brown-Sheng-Lundgren,andBrown-Langely results,andalsobecauseoftheCorneil-PrzuljandBrown-Flesch-Lundgrenresults. Werstcharacterize2-caterpillarsandinterior2-caterpillarsintermsofforbidden inducedsubgraphsandshowthat2-treesthatareunitprobeintervalgraphshaveto beinterior2-caterpillars.Thenwelookat2-pathsthatareunitprobeintervalgraphs andcharacterizethem.Usingsimilarideaswesubsequentlycharacterizeinterior2caterpillarwhichareunitprobeintervalgraphs.Finallyweusetheseresultstogeta completecharacterizationof2-treeswhichareunitprobeintervalgraphs. iv PAGE 5 Theformandcontentofthisabstractareapproved.Irecommenditspublication. Approved:J.RichardLundgren v PAGE 6 DEDICATION MomanddadandmysweetheartsIsha,Sheila,AnoushkaandBubai. vi PAGE 7 ACKNOWLEDGMENTS FirstofallIwouldliketothankmyadviser,Dr.J.RichardLundgren,forguiding, mentoringandengagingmeinmathematics.Iwouldalsoliketothankmyprofessors, friendsandcolleagueswithwhomI'veworkedoverthepastfewyears.Lastly,and certainlymostimportantly,Ithankmyfamily,especiallymysisterforherloveand support. vii PAGE 8 TABLEOFCONTENTS Figures.......................................ix 1.Introduction...................................1 1.1Background..................................1 1.2Introductiontotheresearch.........................5 2.IntervalDigraphs................................7 2.1Introduction..................................7 2.2MotivationfromIntervalTournaments...................11 2.3DigraphswithaTransitive n )]TJ/F15 11.9552 Tf 11.955 0 Td [(2-subtournament............14 2.4Morethanonenontrivialstrongcomponent................22 3.IntervalBigraphImpropriety..........................27 3.1Introduction..................................27 3.2ImproprietyandWeightofIntervalBigraphs................29 3.3 p -criticalintervalbigraphs..........................36 3.4Conclusionsandfuturework.........................47 4.Characterizationofunitprobeinterval2-trees................48 4.1Introduction..................................48 4.2Preliminaries.................................49 4.3Characterizationof2-caterpillars......................56 4.4Forbiddensubgraphsfor2-pathswhichareunitprobeintervalgraphs..61 4.52-pathunitprobeintervalgraphcharacterization.............70 4.6forbiddensubgraphsforinterior2-caterpillarswhichareunitprobeinterval graphs..................................119 4.7Characterizationofinterior2-caterpillarswhichareunitprobeinterval graphs..................................130 References ......................................172 viii PAGE 9 FIGURES Figure 2.1Intervaldigraph................................9 2.2Zeropartition.................................10 2.3Intervalbigraph................................10 2.4Insect.....................................11 2.5Bigraphrepresentationofadigraph.....................11 2.6 D )]TJ/F19 11.9552 Tf 11.956 0 Td [(v .....................................13 2.7ATEinthebigraph..............................15 2.86-cycle.....................................16 2.910-cycle....................................16 2.10Induced6-cycleinthebigraphrepresentation...............17 2.11Morerestrictionsonthearcs........................17 2.12Exampleofadigraphsatisfyingaconditionofthetheorem2.3.1andits zeropartition................................25 2.13Exampleofadigraphsatisfyingaconditionofthetheorem2.3.2andits zeropartition.................................26 2.14Exampleofadigraphthatfailsthehypothesisoftheorem2.3.2since v 0 beats v 00 andhenceformsa6-cycleinitsbigraphrepresentation.....26 2.15Strongcomponents..............................26 3.1 K 1 ; 3 ......................................29 3.2 p -ImproperIntervalGraph.........................30 3.30-ImproperIntervalBigraph........................30 3.4ForbiddensubgraphsforproperIntervalbigraphwiththeirintervalrepresentationstoforcecontainmentfrom X .................31 3.5IntervalrepresentationsofB1,B2,B3toforcecontainmentfrom Y ...31 3.6Improprietyof imp B 1 =2, imp B 2 =1................33 ix PAGE 10 3.7Exteriorlocalcomponents.........................33 3.8Intervalbigraphwithimpropriety1....................34 3.9Intervalbigraphwithimpropriety2....................34 3.10Calculationofweight............................35 3.11Intervalbigraphwithweight2.......................35 3.12Changesinweightduetovariationindenition.............37 3.13Intervalbigraphwhere wt X =0 PAGE 11 4.15F3.......................................63 4.16F4.......................................64 4.17F5.......................................65 4.18F6.......................................66 4.19F7.......................................67 4.20F8.......................................67 4.21F9.......................................68 4.22F10......................................69 4.23F11......................................70 4.24Non-isomorphic2-pathsoflength6.....................72 4.25Constructionthatshowspossiblemergeoftwo-4-fans...........73 4.26Constructionoftwoedge-consecutive4-fans................76 4.27Allpossibletwoedge-consecutive4-fansandtheirrepresentations....76 4.28Formationofthreeedge-consecutive-4-fans.................77 4.29Formationofthreeedge-consecutive-4-fans.................77 4.30Formationofthreeedge-consecutive-4-fans.................78 4.31threeedge-consecutive-4-fans........................78 4.32Formationoftwovertex-consecutive-4-fans.................80 4.33Theonlystructurepossiblefortwovertex-consecutive-4-fans.......80 4.34Representationsofthreevertex-consecutive-4-fans.............81 4.35Anotherrepresentationofthreevertex-consecutive-4-fans.........81 4.36Threepossiblestructuresoftwoedge-consecutive4-fans.........82 4.37Straight2-path................................83 4.38Staircase....................................84 4.392-snake....................................84 4.40Extended-staircase+staircase........................85 4.41Staircaserepresentation...........................85 xi PAGE 12 4.422-snakerepresentation............................86 4.43extended-staircase+staircaserepresentation................86 4.44Fouredge-consecutive4-fans,structure1..................91 4.45Fouredge-consecutive4-fans,structure2..................92 4.46Fouredge-consecutive4-fans,structure3..................92 4.47Exampleofmergesfordierentvaluesof n ................97 4.48 n =1:edge-consecutivemergefor2-paths.................97 4.49 n =1:edge-consecutivemergefor2-paths.................98 4.50 n =1:edge-consecutivemergefor2-paths.................99 4.51 n =2:edge-consecutivemergefor2-paths.................100 4.52 n =2:edge-consecutivemergefor2-paths.................101 4.53 n =2:edge-consecutivemergefor2-paths.................101 4.54 n =2:edge-consecutivemergefor2-paths.................102 4.55 n =2:edge-consecutivemergefor2-paths.................103 4.56 n =3:edge-consecutivemergefor2-paths................103 4.57 n =3:edge-consecutivemergefor2-paths................104 4.58 n =3:edge-consecutivemergefor2-paths.................104 4.59 n =0:vertex-consecutivemergefor2-paths................108 4.60 n =1:vertex-consecutivemergefor2-paths................109 4.61 n =2:vertex-consecutivemergefor2-paths................110 4.62 n =3:vertex-consecutivemergefor2-paths...............110 4.63vertex-consecutive-edge-consecutivefor2-path...............112 4.64vertex-consecutive-edge-consecutivefor2-path...............113 4.65 n =1:vertex-consecutive-edge-consecutivefor2-path..........113 4.66 n =2:vertex-consecutive-edge-consecutivefor2-path..........114 4.67 n =2:vertex-consecutive-snake-edge-consecutivefor2-path.....114 4.68Straight-2-path+end-2-leaves........................116 xii PAGE 13 4.69Staircase+end-2-leaves...........................117 4.702-snake+end-2-leaves.............................118 4.71Non-proberestrictionin4-fans.......................120 4.72Non-proberestriction............................121 4.73Unitprobeintervalrepresentation.....................122 4.743-fanwitha2-leaf..............................122 4.75E2.......................................123 4.76probeintervalrepresentationforE2.....................123 4.77E3.......................................124 4.78E4.......................................125 4.79E5.......................................126 4.80ProbeintervalrepresentationofE5.....................126 4.81E6.......................................127 4.82ProbeintervalrepresentationofE6.....................127 4.83E7.......................................128 4.84E8.......................................129 4.85E9.......................................129 4.86E10......................................130 4.87Group-E11-u1,u2areend2-leavesof B i and B j .............131 4.88Possibleplacesof2-leaves..........................132 4.89Representationof2-snakewithallpossible2-leaves............133 4.90Representationofextendedstaircasewithall2-leaves..........133 4.91Representationofstaircasewithall2-leaves................134 4.92Representationofvertex-consecutive4-fanswithall2-leaves.......134 4.93Representationof2-snakewithall2-leaves.................135 4.94Representationofextended-staircaseandstaircasewithall2-leaves...135 4.95Edge-consecutive4-fanswithall2-leaves..................136 xiii PAGE 14 4.964-fanwithall2-leaves............................136 4.97Vertexconsecutive4-fanswithall2-leaves.................142 4.98 n =1: I 1 ...................................150 4.99 n =1: I 1 ...................................151 4.100 n =2: I 1 ...................................152 4.101 n =3: I 1 ...................................153 4.102 n =4: I 1 ...................................154 4.103Representationofstraight2-pathwithall2-leaves............154 4.104 n =0: I 2 ...................................159 4.105 n =1: I 2 ...................................160 4.106 n =2: I 2 ...................................160 4.107 n =3: I 2 ...................................161 4.108 n =0: I 3 ...................................165 4.109 n =1: I 3 ...................................166 4.110 n =2: I 3 ...................................166 4.111Interior2-caterpillarswithfewer2-leaves.................167 xiv PAGE 15 1.Introduction 1.1Background Intervalgraphsandtheirvariationshavebeenstudiedextensivelyforthelast 50yearsfromatheoreticalstandpointandduetotheirimportanceinapplications. Inthisthesiswewillexploreseveralvariationsofintervalgraphsnamelyinterval digraphs,intervalbigraphsandprobeintervalgraphs.Theworkonintervalbigraphs willfocuson p -improperintervalbigraphandtheworkonprobeintervalgraphswill beonunitprobeintervalgraphs. Letagraph G havevertexset V G andedgeset E G .If x;y 2 V G are adjacent,thenwedenote xy 2 E G .If G isbipartite,wedenotethepartitionsof thevertexsetas V G = f X [ Y g .Agraphis interval iftoeveryvertex, v 2 V G , wecanassignanintervaloftherealline, I v ,suchthat xy 2 E G ifandonlyif I x I y 6 = ; .Intervalgraphsweretheoreticallyintroducedin1957byHajos[22]and alsoappearedinappliedresearchbyBenzerin1959[1]inhisstudyofthestructureof bacterialgenes.Intervalgraphswerecharacterizedbytheabsenceofinducedcycles largerthan3andasteriodaltriplesbyLekkerkerkerandBoland[26]in1962.An asteroidaltriple ATin G isaset A ofthreeverticessuchthatbetweenanytwo verticesin A thereisapathin G thatavoidsallneighborsofthethird. OtherusefulcharacterizationsofintervalgraphsweregivenbyGilmoreandHomanin1964[19]andFulkersonandGross[17].Extensivestudyandresearchhas beendoneonintervalgraphsforseveraldecadesbybothmathematiciansandcomputerscientists.Thesegraphsareusedtoprovidenumerousmodelsindiverseareas suchasgenetics,psychology,sociology,archaeology,orscheduling.Formoredetails onintervalgraphsandtheirapplications,seebooksbyRoberts[36],Golumbic[20] andMckeeandMcMorris[29]. IntervaldigraphswereintroducedbySenetal.in[39].Langley,Lundgren, MerzgaveresultsonCompetitionGraphsofIntervalDigraphsin[25].They 1 PAGE 16 showedthatthecompetitiongraphofanintervaldigraphisanintervalgraphandthat everyintervalgraphisinfactthecompetitiongraphofsomeintervaldigraph.Lin, SenandWestgavesomeinterestingresultsonIntervaldigraphsand,1-matrices in[27].In1998Westgaveadjacencymatrixcharacterizationsofintervaldigraphs andunitintervaldigraphs[42].Atthispointthereisnoforbiddensubgraphcharacterizationofintervaldigraphs,butrecently,in2007,intervaltournamentswere characterizedbyacompletelistofforbiddensubtournamentsbyBrown,Busch,and Lundgren[6].Inchapter2wegeneralizesomeoftheresultsfromthispaper. Anaturalextensionofintervalgraphs,calledintervalbigraphs,wereintroduced byHarary,Kabell,andMcMorris[23]in1982.Let G beabipartitegraphwithbipartition X [ Y ;wemaywrite G = X;Y;E todenotethis.Abipartitegraph G is anintervalbigraphiftoeveryvertex, v 2 V G ,wecanassignanintervalofthereal line, I v ,suchthat xy 2 E G ifandonlyif I x I y 6 = ; and x 2 X and y 2 Y .Interval bigraphshavebeenstudiedbyseveralauthors[9],[14],[23],[24],[27],and[31]. Initiallyitwasthoughtthatthenaturalextensionofasteriodaltriplesofverticesto asteriodaltriplesofedgesalongwithinducedcycleslargerthan4wouldgiveaforbiddensubgraphcharacterization[23].However,Muller[31]foundinsectsandHell andHuang[24]foundedgeasteriodsandbugsasforbiddensubgraphs,andtodatea completecharacterizationremainselusive.Threeedges a , c and e ofagraph G form an asteriodaltripleofedges ATEifforanytwothereisapathfromthevertexset ofonetothevertexsetoftheotherthatavoidstheneighborhoodofthethirdedge. CyclefreeintervalbigraphswerecharacterizedbyBrownetalin2001[14],andATEs playedasignicantroleinthatcharacterization.In2002ageneralizationofinterval bigraphcalledaninterval k -graphwasintroducedbyBrownetal[8].Morerecently, in2010,LundgrenandTonnsencharacterized2-treesthatareinterval k -graphs[28]. 2 PAGE 17 Agraphisaprobeintervalgraphifthereisapartitionof V G intosets P and N andacollection f I v : v 2 V G g ofintervalsof R suchthat,for u;v 2 V G , uv 2 E G ifandonlyif I u I v 6 = andatleastoneof u or v belongsto P .Thesets P and N arecalledtheprobesandnonprobes,respectively.Anintervalgraphisa probeintervalgraphwithanemptynon-probesetandthisclassofgraphshasbeen studiedextensively.Theprobeintervalgraphmodelwasinventedinordertoaid withthetaskcalledphysicalmappingfacedinconnectionwiththehumangenome projectcf.workofZhangandZhangetal.[43],[45],[44].ThepaperbyMcMorris,WangandZhang[30]hasresultssimilartothoseforintervalgraphsfound in[17]byFulkersonandGrossand[20]byGolumbic.Forexampleintervalgraphs arechordalwhileprobeintervalgraphsareweaklychordalandmaximalcliquesare consecutivelyorderableinintervalgraphswhilequasi-maximalcliquesworksinprobe intervalgraphs.In1999LiShengrstcharacterizedcycle-freeprobeintervalgraphs [41]Theclassesofgraphsrelatedtoprobeintervalgraphsarediscussedin[11]by BrownandLundgren,[8]byBrown,FlinkandLundgren,and[21]byGolumbicand Lipshteyn.Relationshipsbetweenbipartiteprobeintervalgraphs,intervalbigraphs andthecomplementsofcirculararcgraphsarepresentedin[11].Theproblemof characterizinggenericprobeintervalgraphsintermsofforbiddensubgraphsfornow appearstobedicult.Sincetreesweretheonlyclassofgraphswhereprobeinterval graphswerecharacterized,anaturalnextstepwastolookataclassof2-trees.In 2005PrzuljandCorneilattemptedaforbiddensubgraphcharacterizationof2-trees thatareprobeintervalgraphsandtheyfoundatleast62distinctminimalforbiddeninducedsubgraphsforprobeintervalgraphsthatare2-trees[34].Morerecently Brown,FleschandLundgrenextendedthelistto69andgaveacharacterizationin termsofsparsespinyinterior2-lobsters[7]. Inthelast40yearsasubclassofintervalgraphshasbeeninvestigatedandstudied 3 PAGE 18 extensively.ThisclassistheclassofunitintervalgraphsintroducedbyRobertsin 1969.Aunitintervalgraphisanintervalgraphwithallintervalsinsomeinterval representationhavingthesamelength.Aproperintervalgraphisanintervalgraph forwhichthereisanintervalrepresentationwithnointervalproperlycontaininganother.Roberts[36]provedthattheclassesofproperintervalgraphsandunitinterval graphscoincideandheshowedthatintervalgraphsthatcontainno K 1 ; 3 areunitintervalgraphs.In1999BogartandWestgaveashorterproofofthesameresultofthe equalityofproperandunitforintervalgraphs[4].Theygaveaconstructiveproofof thisresult,whereproperintervalsaregraduallyconvertedintounitintervals.Much morerecentlyin2007GardigaveamuchshorternewconstructiveproofofRoberts originalcharacterizationofunitintervalgraphs[18]. Aunitintervalbigraphisanintervalbigraphwithallintervalsinsomeinterval representationhavingthesamelengthandaproperintervalbigraphisanintervalbigraphforwhichthereisanintervalrepresentationwithnointervalcontaininganother properly.Severalcharacterizationsofproperintervalbigraphshavebeenfoundinthe lastdecadeincludingonebyLinandWest[27].Theideaofproperintervalgraphs wasnaturallyextendedto p -properintervalgraphsbyProskurowskiandTelle[33]. The p -properintervalgraphsaregraphswhichhaveanintervalrepresentationwhere nointervalisproperlycontainedinmorethan p otherintervals.Any0-improper intervalgraphisaproperintervalgraphanditiseasytocheckthat K 1 ; 3 isaisa 1-improperintervalgraph.Inchapter3wewillgeneralizetheclassof p -improper intervalgraphto p -improperintervalbigraph.Unitintervaldigraphswerecharacterizedin1997byLinetal[27].In2002,Brownetal[9]conjecturedacharacterization ofunitintervalbigraphs.ThisconjecturewasprovedbyHellandHuang[24]in2004. Morerecentlyin2011BrownandLundgrengaveseveraladditionalcharacterization ofunitintervalbigraphs[12].CurrentlyBrown,FleschandLundgrenareworkingon unitinterval k -graphsfor2-trees.FollowingupSheng'scharacterizationofcycle-free 4 PAGE 19 probeintervalgraphs,in2009,Brown,LundgrenandShenggaveacharacterization ofcycle-freeunitprobeintervalgraphs[15].Twonaturalextensionsarise,therstis tocharacterizebipartitegraphsthatareunitprobeintervalgraphsandsecondlyto characterize2-treesthatareunitprobeintervalgraphs.RecentlyBrownandLangley characterizedunitprobeintervalgraphsforbipartitegraphs[10].Inchapter4we giveacharacterizationof2-treesthatareunitprobeintervalgraphs. 1.2Introductiontotheresearch Wewillintroducenotationaswemovethroughthethesis.Attheinitialstagewe willuseconventionaldenitions.Asmentionedearlierthestudyofintervalgraphs haslongbeenamuchresearchedareainGraphTheory.Themajorityofworkinthis thesisisaneorttocharacterizevariousclassesofvariationsofintervalgraphsand unitintervalgraphs.Inchapter2westudydierentclassesofdigraphsanddeterminethescenarioswhentheyareboundtobeinterval.Sincetheproblemofnding acompletecharacterizationofintervaldigraphsisextremelydicult,weconcentrate onspecicclassesofintervaldigraphs.WefocusourresearchinthischapteronapaperofBrown,Busch,andLundgren[6]whereacompletecharacterizationofinterval tournamentsisfound.Welookatorientedgraphswithcertainpropertiesandnd restrictionsthatneedtobeimposedonitsstructureforittobeinterval.Wendseveralclassesofdirectedgraphson n verticeswhichareintervalwithrestrictionssuch ascontainingtransitivesub-tournamentson n )]TJ/F15 11.9552 Tf 12.26 0 Td [(2or n )]TJ/F15 11.9552 Tf 12.26 0 Td [(1verticesandspecic adjacenciesbetweenvertices. Asstatedearlier,anothernaturalextensionofintervalgraphs,calledintervalbigraphs,wereintroducedbyHarary,Kabell,andMcMorrisin1982.The p -improper intervalgraphs,wherenointervalcontainsmorethan p otherintervals,wereinvestigatedbyBeyerlandJamison[3].Inchapter3weextendtheideabyintroducing p -improperintervalbigraphs,wherenointervalcontainsmorethan p otherintervals ofthesamepartiteset.Inthischapterwedeterminerestrictionsonthestructureof 5 PAGE 20 anintervalbigraphforittobea p -improperintervalbigraph.Wealsostudyspecial classesof p -improperintervalbigraphs. Inchapter4,welookatunitprobeintervalgraphs.Sincetheyhavebeencharacterizedfortreesandbipartitegraphs,wefollowthetechniquesofPrzuljandCorneil forthenextbestcasewhichisfor2-trees.Wecharacterize2-treesthathaveaunit probeintervalrepresentation.Inordertoaccomplishthiswerstcharacterize2caterpillarsandinterior2-caterpillarsintermsofforbiddeninducedsubgraphsand showthat2-treesthatareunitprobeintervalgraphshavetobeinterior2-caterpillars. Atthispointwerealizedthattheproblemwasmuchmoredicultthanweoriginally anticipatedittobe.Sowelookat2-pathsthatareunitprobeintervalgraphsand characterizethem.Thenweusethischaracterizationtondthecharacterizationof interior2-caterpillarwhichareunitprobeintervalgraphs.Finallyweusetheseresults togetacompletecharacterizationof2-treeswhichareunitprobeintervalgraphs. 6 PAGE 21 2.IntervalDigraphs 2.1Introduction Adirectedgraph,ordigraphisagraphinwhicheachedgeisassignedadirection. Anarcdirectededgefromvertex u tovertex v willbedenoted u 7! v; andwewill saythat u beats v .Thesetofverticesofadigraph D willbedenoted V D ,andits sizewillbedenoted j V D j .Asubdigraphof D isadigraphconsistingofasubset of V D ,withonlyarcsfrom D betweentheverticesinthissubset.Throughoutthis paper,wewillonlybeconsideringdigraphsthathaveno2-cyclesorloops;sofortwo vertices u;v 2 V D ,if u 7! v; thenwecannothave v 7! u; or u = v Atournament T isanorientedcompletegraph,soforany x;y 2 V T either x 7! y or y 7! x ,butneverboth,and x 7! x canneverhappen.Anintervaltournamentisatournamentthatisanintervaldigraph.Naturallyasubtournamentof somedigraph D isasubdigraphof D thathappenstobeatournament. Adirectedgraph D isanintervaldigraphifforeachvertex u therecorresponds anorderedpairofintervals S u ;T u suchthatforanytwovertices u;v 2 V D , u 7! v; ifandonlyif S u T v 6 = asshownintheFigure2.1.Intervaldigraphswere introducedin1989bySen,Das,RoyandWest.Theyintroducedintervaldigraphs asananalogueofIntervalGraphs[39]andgaveseveralcharacterizationofinterval digraphsintermsofconsecutiveonespropertyofcertainmatrices,adjacencymatrix andFerrersdigraphs.InthesameyearSen,DasandRoygaveanotheradjacency matrixcharacterizationofspecialtypesofdigraphswhichareveryclosetointerval digraphscalledcirculararcdigraphs[40].Incircular-arcdigraphstherepresentations aremadebyarcsofacircleinsteadofintervalsofrealline.Alsoin1997,Lin,Senand Westgavesomestrongresultsonclassesofintervaldigraphsand0,1-matrices[27].In 1998Westagaingaveamuchshorterversionoftheadjacencymatrixcharacterization ofintervaldigraphs[42].Sofarthereisnoforbiddensubgraphcharacterizationsof intervaldigraphs,butrecently,in2007,intervaltournamentshavebeencharacterized 7 PAGE 22 withacompletelistofforbiddensubtournamentsbyBrown,Busch,andLundgren[6]. Theyshowthatatournamentonnverticesisanintervaldigraphifandonlyifithas atransitive n )]TJ/F15 11.9552 Tf 11.572 0 Td [(1-subtournament.Ifadigraph D isnotatournament,thenitmay beanintervaldigraphevenifitdoesnotcontainatransitive n )]TJ/F15 11.9552 Tf 11.646 0 Td [(1-subtournament asasubdigraph,aslongastherearespecicrestrictionson D . Weexplorewhatrestrictionswecanplaceon D toguaranteethatitisinterval, andinparticularweinvestigateabroaderclassoforientedgraphsonnverticesthat containatransitive n )]TJ/F15 11.9552 Tf 10.593 0 Td [(2-tournamentasasubdigraph.Acompletecharacterization ofintervaldigraphsappearstobereallydicultbutwemanagedtondclassesof orientedgraphsthatareintervaldigraphs.Thusweinvestigatedierenttypesofdigraphsmostofwhichhavecharacteristicsincommonwithtournamentstotryand determineclassesofdigraphsthatcanbeshowntohaveanintervalrepresentation. ForagraphGthatisnotadirectedgraph,anadjacencybetweenvertices u;v 2 V G willbedenotedas u $ v .Abipartitegraph,orbigraph, B isagraphin whichtheverticesarepartitionedintotwosets X and Y ,suchthat X [ Y = V B , andanytwovertices u;v 2 V B canonlybeadjacentifonevertexfrom u , v isin X andtheotherisin Y andthisdoesnotguaranteethattheywillbeadjacent.A bipartitegraphBisanintervalbigraphiftoeachvertextherecorrespondsaninterval suchthattwoverticesareadjacentifandonlyiftheircorrespondingintervalsintersectandeachofthesetwoverticesbelongstoadierentpartitesetasshowninFigure 2.3.In2004,HellandHuanggavesomeinterestingresultsonintervalbigraphs[24]. Moreinterestingworkhasbeendoneonintervalbigraphsandotherrelatedgraphsby BrownandLundgrenin2006[11].Methodsforrecognitionofintervalbigraphsand intervaldigraphshavealsobeeninvestigatedin[31]byMuller.Hegaveadynamic programmingalgorithmrecognizingintervalbigraphsintervaldigraphsinpolynomialtime.Thisalgorithmrecursivelyconstructsabipartiteintervalrepresentation ofagraphfrombipartiteintervalrepresentationsofpropersubgraphs.Wewillsee 8 PAGE 23 laterthatthemodelsforintervaldigraphsandintervalbigraphsarebasicallysame. Weusetheequivalenceofthemodelsforintervaldigraphsandintervalbigraphsin ourinvestigationofwhichorientedgraphsareintervaldigraphs. Anadjacencymatrixofadigraph D ,denoted A D ,isa0,1-matrixthathas a1intheentry a i;j rowi,columnjifandonlyif v i 7! v j forthetwovertices v i ;v j 2 V D .A0,1-matrixhasazeropartitionifafterindependentrowandcolumnpermutationseveryzerocanbelabeledasCorR,suchthatbeloweveryCis anotherCexceptforC'sinthebottomrowandtotherightofeveryRisanotherR exceptforR'sinthefarrightcolumn.Figure2.2givesazeropartitionofamatrix. Wetakeintoaccountimportantresultsonintervaldigraphsandintervalbigraphs andpointoutaconnectionbetweenthetwotoprovethesignicantresultsinthis chapter. Thefollowingthreetheoremsarehelpfultoolsneededtoshowcertaindigraphsare, orarenot,interval. Figure2.1: Intervaldigraph Theorem2.1.1 Sen,Das,Roy,West[39].Adigraph D isanintervaldigraphif andonlyif A D hasazeropartition. Anasteroidaltripleofedges,orATE,isasetofthreeedgesinagraphforwhich thereisapathbetweenanytwooftheseedgesthatavoidstheneighborhoodofthe thirdtheneighborhoodofanedgeisthesetofverticesthatareadjacenttooneof itsend-vertices. 9 PAGE 24 Figure2.2: Zeropartition Figure2.3: Intervalbigraph Theorem2.1.2 Muller[31].IfBisanintervalbigraph,thenthefollowinghold: aBhasnoinducedcycleonmorethan4vertices; bBhasnoasteroidaltripleofedgesinanyinducedsubgraph; cBhasnoinsect2.4asaninducedsubgraph. Adigraph D canberepresentedasabigraph B D bylettingeveryvertex v 2 V D correspondtotwoverticesin B D onefromeachpartiteset x v 2 X and y v 2 Y ,suchthat u 7! v in D ifandonlyif x u $ y v in B ,andthisrelationaccountsfor alltheedgesin B D .Thefollowingtheoremputstheconceptsofintervaldigraphs andintervalbigraphstogethertohelpusidentifydigraphsthathavenointerval representation. Theorem2.1.3 If D isanintervaldigraph,then B D isanintervalbigraph. 10 PAGE 25 Figure2.4: Insect Figure2.5: Bigraphrepresentationofadigraph Wecangetthisresultbyletting I x v = S v and I y v = T v forany v 2 V D where x v and y v arethecorrespondingverticesin B D .So,essentially,themodelsfor intervaldigraphsandintervalbigraphsarethesame. 2.2MotivationfromIntervalTournaments Recently,intervaltournamentshavebeencharacterizedbyBrown,Busch,Lundgren[6]andwewillusepartofamainresultprovedbythemthefollowingtheorem forourproofs. Theorem2.2.1 Brown,Busch,Lundgren[6].SupposethatTisatournamenton nvertices.Thenthefollowingareequivalent: aTisanintervaltournament; 11 PAGE 26 bThasatransitive n )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 -subtournament; Thenaturalquestionthatrisesfromthischaracterizationis"Whatarethe othertypesofdigraphsthatcanbeclassiedasinterval?".Sowelookatdigraphs withqualitiesthataresimilartointervaltournaments.Weknowthataninterval tournamentonnverticeshasatransitive n )]TJ/F15 11.9552 Tf 11.616 0 Td [(1-subtournament.Sorstwelookat digraphswiththissamecharacteristicandthisleadsustoageneralizationofTheorem 2.2.1 b a usingasimilarproof.Thefollowingtheoremisageneralizationofthe previoustheorem b a andweusetheconceptofzeropartitionforitsproof. Theorem2.2.2 If D isadigraphonnverticeswithnoloopsor2-cyclesanda transitive n )]TJ/F15 11.9552 Tf 11.955 0 Td [(1 -subtournament,then D isanintervaldigraph. Proof: Let D beadigraphonnverticeswithno2-cyclesorloops,andsupposethe inducedsubgraph D )]TJ/F19 11.9552 Tf 12.56 0 Td [(v isatransitivetournamentasshowninFigure2.6.Label theverticesof D )]TJ/F19 11.9552 Tf 12.968 0 Td [(v as v n )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 ;v n )]TJ/F17 7.9701 Tf 6.587 0 Td [(2 ;:::;v 2 ;v 1 suchthatif v i 7! v j ,then i PAGE 27 0.AlsonotethatthisdoesnotrequireustochangetheRlabelingofthe0'sfrom A D )]TJ/F19 11.9552 Tf 10.906 0 Td [(v sinceeachofthese0'shada0totherightofit,andwehaveonlypermuted therows. Wecannowlabelthe0'sinthevrowonthebottomasC's,sincenoneofthem willhave1'sbelow.Allofthe0'sin A D havenowbeenlabeledasRorC,sowe haveazero-partition,andTheorem2.1.1impliesthat D isanintervaldigraph. Figure2.6: D )]TJ/F19 11.9552 Tf 11.955 0 Td [(v Notethatifadigraph D onnverticeshasa n )]TJ/F15 11.9552 Tf 12.358 0 Td [(1-subdigraphthatistransitive,itisnotnecessarilyanintervaldigraph.Weonlyknowthat D hasaninterval representationinthiscaseifthetransitive n )]TJ/F15 11.9552 Tf 12.294 0 Td [(1-subdigraphisactuallyatournament.Infact,atransitivedigraphitselfmaynotbeinterval.Anexampleofthisis inFigure2.8,whichshowsatransitivedigraph D thatisnotintervalbyTheorem 2.1.2becauseitsbigraph B D hasaninduced6-cycle. Supposenowforadigraph D ,theinducedsubgraph D )]TJ/F19 11.9552 Tf 12.837 0 Td [(v istheunionofk disjointtransitivetournamentsforsome k 2 N 0 .Wendthattheredoexistseveral suchdigraphsthatarenotintervaldigraphs.Wefound6-cycles,8-cycles,10-cycles 13 PAGE 28 andevenATEsinthecorrespondingbigraphsofsuchdigraphs. InFigure2.9,theinduced10-cycleinthebigraph B D showsthat D isnot anintervaldigraph.However,ithasbeenshowedthatthe10-cycleisthelargest inducedcyclethatcanexistinthebigraph B D ofsuchadigraph D [16].Thus6,8, and10-cyclesaretheonlycyclesinthebigraph B D thatwouldproduceforbidden structures.Itisworthmentioningherethatithasalsobeenprovedthatthelongest inducedpathinthebigraph B T ofanytransitivetournament T consistsofthree edgesandfourvertices[16]. Unfortunately,wealsodiscoveredthattherearemanywaysthatATE'scanappearinthebigraphscorrespondingtodigraphs D inwhich D )]TJ/F19 11.9552 Tf 10.497 0 Td [(v isaunionofdisjoint transitivetournaments.OneexampleisshownbelowinFigure2.7.Weknowthat thatif B D hasanATE,then B D isnotanintervalbigraph,andhence D is notanintervaldigraph.Theseresultsleadustoconsideradierentgeneralization, namely,digraphsDonnverticessuchthattheinducedsubdigraphonn-2vertices givenby D f v 0 ;v 00 g isatransitivetournament. 2.3DigraphswithaTransitive n )]TJ/F15 11.9552 Tf 11.955 0 Td [(2 -subtournament Adigraph D onnverticeswithatransitive n )]TJ/F15 11.9552 Tf 10.234 0 Td [(2-subtournamentcanhavemany structuresinitsbigraph B D thatpreventitfrombeinganintervaldigraph.Figure 2.10belowisanexamplewherewegetaforbiddensubgraphin B D whichisa 6-cycleforwhich D f v 0 ;v 00 g isatransitivetournament.Itisalsoworth-mentioning herethatforthisparticulardigraph D ,addinganycombinationofthedashedarcs ornoneofthemwillresultinthesameinduced6-cyclein B D .Altogether,there areatotalof36possiblecombinationsofthesedashededgesthatwillresultinthis particularinduced6-cycle. TheexampleintheFigure2.10showsthatwecaneasilyendupwithaninduced 6-cyclein B D foradigraph D inwhich D f v 0 ;v 00 g isatransitivetournament. Furthermorethistypeofdigraph D hasmanyforbiddenstructuresthatwillprevent 14 PAGE 29 Figure2.7: ATEinthebigraph itfromhavinganintervalrepresentationincludingmanyinducedcyclesoflengthat least6andmanyATE'sinitsbigraph.Thissuggeststhatperhapsweneedmore restrictionson D tondatypeofdigraphthatweknowisinterval.Thefollowing theoremplacesmorerestrictionsonthearcsdirectedbetweentheverticesofthe transitive n )]TJ/F15 11.9552 Tf 11.955 0 Td [(2-subtournamentandtheothertwovertices v 0 and v 00 . Theorem2.3.1 Let D beadirectedgraphonnverticeswithno2-cyclesorloops, andwithatransitive n )]TJ/F15 11.9552 Tf 12.454 0 Td [(2 -subtournament D = D f v 0 ;v 00 g .Supposeeitheraor bistrue,butnotboth: aSupposenoverticesin D beat v 0 or v 00 ,and v 00 beatsasubsetoftheverticesin D that v 0 beats; bSupposenoverticesin D arebeatenby v 0 or v 00 ,and v 00 isbeatenbyasubsetof theverticesin D thatbeat v 0 . Then D isanintervaldigraph 15 PAGE 30 Figure2.8: 6-cycle Figure2.9: 10-cycle 16 PAGE 31 Figure2.10: Induced6-cycleinthebigraphrepresentation Figure2.11: Morerestrictionsonthearcs Proof: Let D beadigraphonnverticeswithno2-cyclesorloops,andsuppose D = D f v 0 ;v 00 g isatransitivetournament.Thusthesubdigraph D v 00 hasatransitive n )]TJ/F15 11.9552 Tf 10.961 0 Td [(2-subtournament,andbyTheorem2.2.1itisanintervaldigraph.Theorem 2.1.1nowimpliesthat A D )]TJ/F19 11.9552 Tf 12.417 0 Td [(v 00 hasazeropartition.Assumethat D meetsthe conditionsofeitheraorbabove,butnotboth.Thefollowingcasesmustbe considered: i v 0 ,and v 00 havenoarcbetweenthem, ii v 00 hasanarcdirectedto v 0 , iii v 0 hasanarcdirectedto v 00 . 17 PAGE 32 Arrangetherowsandcolumnsof A D )]TJ/F19 11.9552 Tf 12.3 0 Td [(v 00 asintheproofofTheorem2.2.1Now addthecolumnandrowcorrespondingto v 00 atthefarleftwithcolumn v 0 toits rightandbottomofthematrixwithrow v 0 above,respectively.Recallfromthe proofofTheorem2.2.1thatthesubmatrix A D alreadyhaseachofits0slabeled asR. Ifaistruebutbisnot: iLet v 0 ,and v 00 havenoarcdirectedbetweenthem.Row v 0 justaboverow v 00 hasits0slabeledasCs,asintheproofofTheorem2.2.1.Row v 00 willhavea 0ineverycolumnentrythatrow v 0 hasa0,andwillalsohave0sinsomecolumn entriesinwhichrow v 0 has1sand1sintheotherentries.Soeach0inrow v 00 can belabeledasC,whichwilleachbebelowanotherCora1.Also,columns v 0 and v 00 willhaveall0entriessincenoverticesin D beatthesetwovertices,andeachof these0'scanbelabeledasC.Now A D hasazeropartition. iiIf v 00 hasaarcdirectedto v 0 ,then a v 00 v 0 istheonlyentrythatisdierentfrom A D iniabove,anditnowbecomesa1.This1isaproblembecauseitisbelow the0sincolumn v 0 ,whichhadpreviouslybeenlabeledasCs.Sonowmovecolumn v 0 tothefarright.Becausenoverticesfrom D havedirectedarcsto v 0 or v 00 ,the1 atthebottomofcolumn v 0 istheonly1inthatcolumn,andallthe0saboveitcan berelabeledasRs.Now A D hasazeropartition. iiiIf v 0 hasadirectedarcto v 00 ,then a v 0 v 00 istheonlyentrythatisdierentfrom A D iniabove,anditnowbecomesa1.Inthesamemanneraspartii,move column v 00 tothefarrightandrelabelallentriesaboveentry a v 0 v 00 whichareall0s asRs.Thereisalsoone0below a v 0 v 00 incolumn v 00 ,whichcanbelabeledasC.Now A D hasazeropartition. 18 PAGE 33 Ifbistruebutaisnot: iLet v 0 and v 00 havenoarcdirectedbetweenthem.Therowsof A D )]TJ/F19 11.9552 Tf 12.353 0 Td [(v 00 have alreadybeenpermutedasintheproofofTheorem2.2.1sothattherowswitha 1inthecolumn v 0 justrightofcolumn v 00 areatthetop,withallthe0'sinthis columnbelowthe1'sandlabeledasC's.Nowpermutetheserowswith1'sincolumn v 0 sothattherowswith1'sincolumn v 00 areatthetopwith0'sunderneathnote thatcolumn v 0 willstillhaveallits1'saboveits0's.Nowallthe0'sarebelowthe 1'sincolumn v 0 and v 00 ,andeachofthese0'scanbelabeledasC.Therows v 0 and v 00 willbecomposedentirelyof0's,whichcanbelabeledasC's,sincenoverticesin D arebeatenbythesetwovertices.Now A D hasazeropartition. iiIf v 00 hasadirectedarcto v 0 ,then a v 00 v 0 istheonlyentrythatisdierentfrom A D iniabove,anditnowbecomesa1.This1isnowaproblembecauseitis belowthe0'sincolumn v 0 ,whichhadpreviouslybeenlabeledasC's.Sonowmove row v 00 justbelowthelowestrowin A D )]TJ/F19 11.9552 Tf 12.282 0 Td [(v 00 forwhichthereisa1incolumn v 0 . Because v 0 and v 00 donothavedirectedarcstoverticesin D , a v 00 v 0 istheonlyentry inrow v 00 thatisa1,sothe0totheleftincolumn v 00 isstilllabeledasaC,andall the0'stotherightcanbelabeledasR's.Now A D hasazeropartition. iiiIf v 0 hasadirectedarcto v 00 ,then a v 0 v 00 istheonlyentrythatisdierentfrom A D iniabove,anditnowbecomesa1.This1isnowaproblembecauseitis belowthe0'sincolumn v 00 ,whichhadpreviouslybeenlabeledasC's.Nowmoverow v 0 tothetop.Because v 0 and v 00 donothavedirectedarcstoverticesin D , a v 0 v 00 is theonlyentryinrow v 0 thatisa1,soalltheotherentriesare0's,whichareallto therightofentry a v 0 v 00 andcaneachbelabeledR.Nowwehaveazeropartitionfor A D . Ineverycaseabovewehavefoundazeropartitionof A D ,soTheorem2.1.1implies that D isanintervaldigraph. 19 PAGE 34 Itisworthmentioningherethatifthereisnoarcdirectedbetween v 0 and v 00 thenDcanbeprovedtobeanintervaldigraphwithfewerrestrictionsplacedonthe directedarcsbetweentheverticesof D and v 0 , v 00 .Thefollowingtheoremproves thisfact. Theorem2.3.2 Let D beadirectedgraphonnverticeswithno2-cyclesorloops, andwithatransitive n )]TJ/F15 11.9552 Tf 12.473 0 Td [(2 -subtournament D = D f v 0 ;v 00 g ,where v 0 and v 00 are verticesthathavenoarcdirectedbetweentheminD. Suppose v 0 beatsasubsetoftheverticesin D that v 00 beats,or v 00 beatsasubsetofthe verticesin D that v 0 beats.Alsosupposethat v 0 isbeatenbyasubsetofthevertices in D thatbeat v 00 ,or v 00 isbeatenbyasubsetoftheverticesin D thatbeat v 0 . Then D isanintervaldigraph. Proof: Because D isadigraphwithno2-cyclesorloopsthathasatransitive n )]TJ/F15 11.9552 Tf 12.348 0 Td [(2subtournament D = D f v 0 ;v 00 g ,weknowthatthesubgraph D v 00 hasatransitive subtournamentonallbutoneofitsvertices.Theorem2.2.1impliesthat D v 00 is anintervaldigraph,whichisequivalentto A D )]TJ/F19 11.9552 Tf 12.47 0 Td [(v 00 havingazero-partitionfrom Theorem2.1.1. Arrangethesubmatrix A D )]TJ/F19 11.9552 Tf 12.44 0 Td [(v 00 asintheproofofTheorem2.2.1,wherethe rowscorrespondingtoverticesfrom D witharcsdirectedto v 0 areatthetop,sothat allthe0'sincolumn v 0 arebelowthe1'sandeachislabeledasC. Iftheverticesin D withdirectedarcsto v 00 areasubsetofthosewithdirected arcsto v 0 ,thenwecanplacecolumn v 00 totheleftofcolumn v 0 inADandrearrange thetoprowswith1'sincolumn v 0 sothatalltherowswith1'sincolumn v 00 areon top,withthe0'sunderneaththemlabeledasC's.Notethatcolumn v 0 willstillhave allits1'satthetop,with0'sunderneathandlabeledasC's. 20 PAGE 35 Iftheverticesin D witharcsdirectedto v 0 areasubsetofthosewitharcs directedto v 00 ,thenwecanplacecolumn v 00 totheleftofcolumn v 0 again.Allthe rowswith1sincolumn v 0 arealreadyatthetop,whichalsohave1'sincolumn v 00 , andwecanplacetheotherrowswith1'sincolumn v 00 directlybelowtheserowsso thatcolumns v 0 and v 00 havethe0'slabeledasC'sandplacedbelowallofthe1's. Sincewehavearranged A D )]TJ/F19 11.9552 Tf 11.894 0 Td [(v 00 asintheproofofTheorem2.2.1,row v 0 isat thebottomof A D )]TJ/F19 11.9552 Tf 11.955 0 Td [(v 00 andhaseachofits0'slabeledasC. Iftheverticesin D witharcsdirectedfrom v 00 areasubsetofthosewithdirected arcsfrom v 0 ,thenwecanplacerow v 00 belowrow v 0 in A D andlabeleachofits0's asaC,sinceeachoftheseC'swilleitherbebelowa1oranotherC. Iftheverticesin D witharcsdirectedfrom v 0 areasubsetofthosewitharcs directedfrom v 00 ,thenwecanplacerow v 00 justaboverow v 0 in A D andlabeleach ofits0'sasaC,sinceeachoftheseC'swillalwaysbeaboveanotherC. AsintheproofofTheorem2.2.1,therestofthe0'swhicharefromthesubmatrix A D arelabeledasR's.Therefore A D hasazeropartition,andfromTheorem 2.1.1thisimpliesthat D isanintervaldigraph. Theorem2.3.2willfailtoholdifthereexistanarcbetween v 0 and v 00 .Thegure 2.14showsaninduced6-cyclein B D correspondingtothedigraph D whichhasarc v 0 7! v 00 .In D , v 00 beatsasubsetoftheverticesin D -[ v 0 , v 00 ]that v 0 beatsand v 00 is beatenbyasubsetoftheverticesinD-[ v 0 , v 00 ]thatbeat v 0 . 21 PAGE 36 2.4Morethanonenontrivialstrongcomponent Astrongcomponentofadigraph D isamaximalstronglyconnectedsubgraph. Adirectedgraphisstronglyconnectedifforeverypairofvertices v , u thereexists atleastonepathfrom v to u ,andatleastonepathfrom u to v .Brown,Busch, Lundgren[6]provedthefollowingtheoremaboutstrongcomponentsintournaments. Theorem2.4.1 Notournamentthathastwoormorenon-trivialstrongcomponents isanintervaltournament. However,anintervaldigraphcanhavemorethanonenontrivialstrongcomponent.Infact,certaindigraphswithtwoormorenontrivialstrongcomponentsthat havespecictypesofadjacencymatricesalwayshaveanintervalrepresentation,as thefollowingtheoremshows.Figure2.15showsanintervaldigraphwith2non-trivial strongcomponents.Wewillrequireacoupleofnewdenitionstoprovethatcertain digraphswithspecicadjacencymatricesandtwoormorenon-trivialstrongcomponentswillalwaysbeinterval. Denition2.4.2 AnRzeropartitionofa f 0,1 g -matrixisazeropartitionin whicheachofthe0'softhematrixcanbelabeledasRwheretotherightofeach RisanotherRaftercolumnpermutations.Likewise,aCzeropartitionisazero partitioninwhicheachofthe0'scanbelabeledasCwherebeloweachCisanother Cafterrowpermutations. Thefollowingtheoremshowsthatadigraphwithexactlytwonon-trivialstrong componentswillbeintervaliftheadjacencymatricesofthestrongcomponentsand theadjacencymatrixdeterminingtherelationbetweenthestrongcomponentsare specic.Itisworthmentioningherethatthefollowingresulthasbeengeneralizedto adigraphwith k 2 N non-trivialstrongcomponentsin[16]. 22 PAGE 37 Theorem2.4.3 Let D beadirectedgraphonnverticeswithexactlytwonontrivial strongcomponents, D 1 and D 2 .Supposethatasubsetoftheverticesof D 1 havearcs directedtoasubsetoftheverticesof D 2 butnoverticesin D 2 havearcsdirectedto verticesin D 1 . Ifthesubmatrices A 1 = A D 1 and A 2 = A D 2 bothhaveaCzeropartition, andthesubmatrix B whoserowsrepresenttheverticesof D 1 ,andwhosecolumns representtheverticesof D 2 hasanRzeropartition,thenDisanintervaldigraph. Proof: Lettheadjacencymatrix A D bearrangedasfollows: A D = 0 B @ A 1 B 0 A 2 1 C A Ourhypothesisstatesthatnotonlydoes D containexactlytwonontrivialstrong components D 1 and D 2 ,buttheiradjacencymatrices, A 1 and A 2 ,musthaveaC zeropartitionafterrowpermutations.Also,thearcsdirectedfromverticesin D 1 to verticesin D 2 mustbesuchthattheadjacencysubmatrix B whoserowsrepresent theverticesof D 1 ,andwhosecolumnsrepresenttheverticesof D 2 musthaveanR zeropartitionaftercolumnpermutations.Assumingthattheseconditionsaremet, thecolumnpermutationsusedtogetanRzeropartitionof B whichdonotaect theorderoftheentriesinthecolumnsof A 1 or A 2 willnotchangetheClabelingsof the0sin A 1 and A 2 ,andtherowpermutationsusedtogetaCzeropartitionof A 1 and A 2 whichdonotaecttheorderoftheentriesintherowsof B willnotchange theRlabelingsofthe0sin B .Therefore A D hasazeropartitioninwhicheach ofthe0sinthesubmatricesrepresentedby A 1 , A 2 ,and0arelabeledasC,andthe 23 PAGE 38 submatrix B haseachofits0slabeledasR.ThisimpliesbyTheorem2.1.1that D isanintervaldigraph. Wehavestudiedthestructuresofseveraldigraphsinordertoascertainwhen theyareinterval.Wefocussedondigraphsthatpossesssomesimilarqualitiesof intervaltournamentssuchasthedigraphswithatransitivesubtournamentonallbut twoverticesandthedigraphsforwhichtheremovalofonevertexleavesasubdigraph thatisatransitivesub-tournament.Thesetypesofdigraphsseemedtobethenatural placetostartbecausethereisacompletecharacterizationofintervaltournaments. Wesuccessfullyfounddierentrestrictionsthatforceadigraphtobeintervalthus ndingsomespecialclassesofintervaldigraphs. Therearestillnumerousclassesofdigraphsthatwillbeintervalwithsomerestrictionsontheirarcswhichhavenotbeenexploredyet.Surelytheproblemof ndingacompleteforbiddensubdigraphcharacterizationofintervaldigraphswillbe averydicultonesincethelistofforbiddenstructuresisalreadyverylong.Much workstillneedstobedoneonthistopic. 24 PAGE 39 Figure2.12: Exampleofadigraphsatisfyingaconditionofthetheorem2.3.1and itszeropartition 25 PAGE 40 Figure2.13: Exampleofadigraphsatisfyingaconditionofthetheorem2.3.2and itszeropartition Figure2.14: Exampleofadigraphthatfailsthehypothesisoftheorem2.3.2since v 0 beats v 00 andhenceformsa6-cycleinitsbigraphrepresentation Figure2.15: Strongcomponents 26 PAGE 41 3.IntervalBigraphImpropriety 3.1Introduction Anintervalgraphisproperifandonlyifithasarepresentationinwhichno intervalcontainsanother.BeyerlandJamisonintroducedthestudyof p -improper intervalgraphswherenointervalcontainsmorethan p otherintervalsin2008.Thus aproperintervalgraphisa0-improperintervalgraph.Inthischapterweextendthe ideabyintroducing p -improperintervalbigraphs,wherenointervalcontainsmore than p otherintervalsofthesamepartiteset.Severalauthorshavestudiedproper intervalbigraphs.Oneofthesecharacterizationshasthreeforbiddensubgraphs.We ndboundsonthestructureof p -improperintervalbigraphsandcharacterizeaspecial caseof p -improperintervalbigraphs. Letagraph G havevertexset V andedgeset E . x;y 2 V beingadjacentis denotedby xy 2 E .Anitesimplegraph G V;E isanintervalgraphifwecannd amapping : v )167(! I v fromverticesofGtointervalsontherealline,suchthatthe edge xy existsifandonlyif I x I y 6 = forall x;y 2 V G .Intervalgraphswererst discussedbyHajos[22].Thestudyofintervalgraphsalsohasitsorigininapaperof Benzer[1]whowasstudyingthestructureofbacterialgenes. Awell-knowncharacterizationofintervalgraphswasgivenbyLekkerkerkerand Bolandin1962.TheLekkerkerker-BolandTheorem[26]saysthatchordlesscycles andasteroidaltriplesformadeningclassofforbiddensubgraphsfortheclassof intervalgraphs.An asteroidaltriple ATin G isaset A ofthreeverticessuchthat betweenanytwoverticesin A thereisapathbetweenthemthatavoidsallneighbors ofthethird.AnaturalextensionofATisanAsteroidalTripleofEdges.An asteroidal tripleofedges ATEisasetofthreeedgessuchthatforanytwothereisapath fromthevertexsetofonetothevertexsetoftheotherthatavoidstheneighborhood ofthethirdedge.Anaturalextensionofintervalsgraphs,calledintervalbigraphs, wereintroducedbyHarary,Kabell,andMcMorris[23]in1982.Abipartitegraph 27 PAGE 42 G X;Y;E isanintervalbigraphiftoeveryvertex, v 2 V G ,wecanassignan intervaloftherealline, I v ,suchthat xy 2 E G ifandonlyif I x I y 6 = ; and x 2 X and y 2 Y .Thesegraphshavebeenstudiedbyseveralauthors[13],[27].Todateno forbiddensubgraphcharacterizationofintervalbigraphshasbeenfound,butinitially itwasthoughtthatasteriodaltriplesofedgesalongwithinducedcycleslargerthan 4wouldwork[23].Theyprovedthatif B isanintervalbigraphthen B doesnot haveATE.However,Muller[31]foundinsectsandHellandHuang[24]foundedge asteriodsandbugsasforbiddensubgraphs,andtodateacompletecharacterization isstillnotavailable. FredRoberts[35]in1969characterizedproperintervalgraphs.Properinterval graphsaregraphswhichhaveanintervalrepresentationsuchthatnointervalcontainsanother.Anintervalgraphisproperifandonlyifitdoesnotcontain K 1 ; 3 as aninducedsubgraph.Unitintervalgraphsarethegraphshavinganintervalrepresentationinwhichalltheintervalshavethesamelength.Claw-freeintervalgraphs aretheintervalgraphswithoutaninducedcopyoftheclaw, K 1 ; 3 .Robertshasalso shownthattheclassofproperintervalgraphscoincidewiththeclassesofunitinterval graphsandclaw-freeintervalgraphs. Properintervalbigraphsarebigraphswhichhaveanintervalrepresentations wherenointervalcontainsanother.Severalcharactizationsofproperintervalbigraphshavebeenfoundinthelastdecade.ThegraphsinFigure3.4aretheforbidden subgraphsforproperintervalbigraphsfoundbyLinandWest[27]. Theideaofproperintervalgraphswasnaturallyextendedto p -properinterval graphsbyProskurowskiandTelle[33].The p -properintervalgraphsaregraphswhich haveanintervalrepresentationwherenointervalisproperlycontainedinmorethan p otherintervals.BeyerlandJamison[3]investigatedavariationincontainmentand introduced p -improperintervalgraphswherenointervalcontainsmorethan p other intervals.A p -improperrepresentationofagraphisanintervalrepresentationof 28 PAGE 43 thegraphwherenointervalcontainsmorethan p otherintervals.Figure3.2isan illustrationofa1-improperintervalgraph.Thusany0-improperintervalgraphisa properintervalgraph.ItcanbeeasilycheckedinFigure3.1that K 1 ; 3 isa1-improper intervalgraph. Inthischapterwegeneralizetheclassof p -improperintervalgraphsto p -improper intervalbigraphs.WelookatideaswhichBeyerlandJamisoninvestigatedforinterval graphsandapplytheminintervalbigraphs.Somedenitionshadtobemodiedsince weareworkingwithtwopartitesets. A p -improperintervalbigraphisanintervalbigraphwherenointervalcontains morethan p intervalsfromthesamepartiteset.Inordertobeabletogeneralizethe ideasfor p -improperintervalgraphsto p -improperintervalbigraphs,werestrictthe containmentofintervalstoanindividualpartitesetasshownintheFigure3.3.Beyerl andJamisoninvestigatedideassuchasimpropriety,weight, p -criticalandbalancefor intervalgraphs,andweinvestigatethesameideaswithsomemodieddenitionsfor intervalbigraphs.Inthischapterwendrestrictionsinthestuctureofaninterval bigraphforittobea p -improperintervalbigraph.Wealsostudyspecialclassesof p -improperintervalbigraphs. Figure3.1: K 1 ; 3 3.2ImproprietyandWeightofIntervalBigraphs Fromthispointon B = B X;Y;E willdenoteanite,connected,intervalbigraphwithbipartition f X;Y g andthesets X and Y willbereferredtoasthepartite 29 PAGE 44 Figure3.2: p -ImproperIntervalGraph Figure3.3: 0-ImproperIntervalBigraph sets.A0-improperintervalbigraphisaproperintervalbigraph.Thefollowing propositionjustiesourwayofdeninga p -improperintervalbigraph.Itexplains thesuciencyofrestrictingtheinclusionofintervalstoasinglepartitesetinan intervalbigraph. Proposition3.2.1 B isaproperintervalbigraphifandonlyifithasaninterval representationwherenointervalfromapartitesetcontainsanotherintervalfromthe samepartiteset. Proof: Suppose B X;Y;E isaproperintervalbigraph.Itfollowsfromthe denitionthatithasanintervalrepresentationwherenointervalfromapartite setcontainsanotherintervalfromthesamepartiteset,sincenointervalcontains another. Suppose B hasanintervalrepresentationwherenointervalfromapartiteset 30 PAGE 45 containsanotherintervalfromthesamepartiteset.If B isnotproperthenithas oneofthegraphsinFigure3.4asaninducedsubgraph[27].Itiseasytocheckfrom theintervalrepresentationofB1,B2andB3illustratedinFigure3.4andFigure 3.5thattheyallareforcedtohaveanintervalwhichcontainsanotherintervalfrom thesamepartiteset.InFigure3.4weavoidthecontainmentofanintervalfrom Y inanotherintervalfrom Y .Thisforcesthecontainmentofanintervalfrom X in anotherintervalfrom X .InFigure3.5weavoidthecontainmentofanintervalfrom X inanotherintervalfrom X .Thisforcesthecontainmentofanintervalfrom Y or X inanotherintervalfrom Y or X .B1istheonlyexamplewhereweneverattain acontainmentfrom Y .Italwayshasanintervalfrom X containinganotherfrom X .Thuswecannotavoidan X intervalproperlycontaininganotherfrom X ora Y intervalproperlycontaininganotherfrom Y .Hence B hasanintervalwhichcontains anotherintervalfromthesamepartitesetwhichcontradictsourassumption. Figure3.4: ForbiddensubgraphsforproperIntervalbigraphwiththeirinterval representationstoforcecontainmentfrom X Figure3.5: IntervalrepresentationsofB1,B2,B3toforcecontainmentfrom Y 31 PAGE 46 FirstwewillgeneralizethenotionofimproprietyintroducedbyBeyerlandJamison.Theideaofimproprietycomesfrom p -improperintervalbigraphs. Denition3.2.2 The improprietyofavertex z 2 X withrespecttotheinterval representation isthenumberofvertices x 2 X suchthat I x I z ,whichwewill denoteas imp z . Denition3.2.3 The improprietyofarepresentation isthemaximum imp z forall z 2 X;Y whichwewilldenoteas imp B . Denition3.2.4 The improprietyoftheintervalbigraph B istheminimum imp B overallpossibleintervalrepresentationswhichwewilldenoteas imp B .Arepresentationwhichgivestheminimumimproprietywillbecalledaminimalrepresentation. Anyintervalbigraphcanhaveaninnitenumberofintervalrepresentations.So itiseasytoseethattheimproprietyistheleast p forwhichthegraphisa p -improper intervalbigraphasshownintheFigure3.6.Figures3.8and3.9giveexamplesof graphswhoseimproprietyis1and2respectively.Itiseasytocheckthat I z I x ;I y isforced. Denition3.2.5 For z 2 B X;Y;E ,acomponentof B )]TJ/F19 11.9552 Tf 12.418 0 Td [(z willbecalleda local component of z .Alocalcomponentof z is exterior ifandonlyifitcontainsanedge xy suchthat x;y= 2 N z .SeeFigure3.7. Itisworthmentioningherethatallthebigraphsherehaveconnectivityone. Thefollowinglemmagivesusaboundonthenumberofexteriorlocalcomponents anyvertexofanintervalbigraphcanhave. Lemma3.2.6 Avertex z inanintervalbigraphcanhaveatmosttwoexteriorlocal components. 32 PAGE 47 Figure3.6: Improprietyof imp B 1 =2, imp B 2 =1 Figure3.7: Exteriorlocalcomponents Proof: Wewillprovethisbycontradiction.Letusassumethat B X;Y isa connectedintervalbigraphand z 2 X isavertexin B withatleast3exteriorlocal components.Sothereexists3edges x 1 y 1 ;x 2 y 2 ;x 3 y 3 in3oftheseexteriorcomponents suchthat x 1 ;y 1 ;x 2 ;y 2 ;x 3 ;y 3 = 2 N z .Wecanndapathbetweenanytwopairs oftheseedges,sayfrom x 1 y 1 to x 2 y 2 through z whichavoidstheneighborhoodof x 3 y 3 since x 3 ;y 3 = 2 N z .Hencetheedges x 1 y 1 ;x 2 y 2 ;x 3 y 3 formanasteroidaltriple ofedgeswhichisaforbiddensubgraphforanintervalbigraph[23].Thusweget acontradiction.Henceanyvertex z inanintervalbigraphcanhaveatmosttwo exteriorlocalcomponents. 33 PAGE 48 Note: Let B X;Y beanintervalbigraph.If C i isanexteriorcomponentofany vertex z 2 X thenintheintervalrepresentationthereexistavertex y 2 C i Y such that I y I z = .So C i mustalwaysbeonthesideof I z . Figure3.8: Intervalbigraphwithimpropriety1 Figure3.9: Intervalbigraphwithimpropriety2 Thefollowingdenitionandtheoremleadstoaboundontheimpropriety. Denition3.2.7 Let B X;Y;E beanintervalbigraph.Let z 2 X and C 1 ;C 2 ;::::;C n bethelocalcomponentsof z orderedfromlefttorightthelefthandcomponents haveintervalsonthelefthandsideoftheintervalrepresentationandtherighthand componentswillhaveintervalsontherighthandsideoftheintervalrepresentation suchthat C 1 and C n arechoseneithertobeexteriorcomponentsiftheyexistor non-exteriorlocalcomponentssuchthat j C 1 X jj C i X j ;i =2 ;::: n )]TJ/F15 11.9552 Tf 12.707 0 Td [(1 and j C n X jj C i X j ;i =2 ;::: n )]TJ/F15 11.9552 Tf 11.959 0 Td [(1 .The weightofthevertex z isthetotalnumber 34 PAGE 49 ofverticesin C 2 X [ :::: [ C n )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 X ,whichwewilldenoteas wt z .Wewill call C 2 ;C 3 ;::::;C n )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 thesmallernon-exteriorlocalcomponentsof z .The weight of X isthemaximumoftheweightsofallthevertices x 2 X ,whichwewilldenoteas wt X .Theweightofavertexin Y andtheweightof Y aredenedsimilarly.The weightofanintervalbigraph , wt B ,isthemaximumoftheweightsofitstwopartite sets. ThegraphsinFigure3.9andFigure3.11haveweights2eventhoughtheyhave adierentnumberofexteriorcomponents.Thisisbecauseweconsiderthesmallest non-exteriorlocalcomponentstocalculatetheweights. Figure3.10: Calculationofweight Figure3.11: Intervalbigraphwithweight2 Thenexttheoremgivesusaboundontheimpropriety. Theorem3.2.8 Let B X;Y;E beanintervalbigraph.Let z 2 B .Thentheimproprietyof B isatleasttheweightof z . Proof: Let beaminimalintervalrepresentationoftheintervalbigraph B . Let z 2 X and C 1 ;C 2 ;::::::C n bethelocalcomponentsof z orderedfromlefttoright 35 PAGE 50 asinDenition3.2.7.Let I z denotetheintervalof z .So wt z = P i =2 ;::: n )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 j C i X j . Theintervalsofverticesfrom X in C 2 ;::::::;C n )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 mustbeinside I z becausethereare vertices y 1 2 C 1 ;y n 2 C n thatarenotadjacenttoanyvertexfrom X in C 2 ;::::::;C n )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 butareadjacentto z .Hence,forany andforany z 2 Xwt z imp z .Since imp B =max[ imp z i forall z i 2 B ], imp z imp B ,andso wt z imp B . Hencetheimproprietyof B isatleasttheweightof z . Corollary3.2.9 Foranyintervalbigraph B X;Y;E , imp B wt B . Proof: Theprooffollowsdirectlyfromtheprevioustheoremanddenitions. Note :Nowthatwehavetheaboveboundonweight,thereasonbehindthe restrictionofthecontainmenttoasinglepartitesetcanbediscussedmoreexplicitly. Ifwedidnotconneittoanindividualpartiteset,theaboveresultwouldfailto holdforintervalbigraphs.Forexample,consider K 1 ; 4 .Thisisanintervalbigraph. Letuscallit B X;Y;E .Withoutlossofgenerality,thereisonlyonevertexin X andtheremainingfourverticesbelongto Y .Byourdenitionofimproprietyand weight,wehavethe wt X =0= imp B .Thustheabovebound wt X imp B holdshere.Ifwehadnotrestrictedtheimproprietytoasinglepartitesetthenthe denitionofweightwouldalsobedierent.Weightalsowouldnothavebeenconned toanindividualpartiteset.Itwouldtakeintoaccountalltheverticesinthe n )]TJ/F15 11.9552 Tf 12.181 0 Td [(2 smallestnonexteriorcomponentsofanyvertexwith n localcomponents.Therefore imp B =0and wt X =2whichisillustratedinFigure3.12.Thisdeesthebound wt X imp B .Thisboundholdsforintervalgraphsandsinceitiseasierto calculate wt B than imp B ,wewantedthisusefulboundhere. 3.3 p -criticalintervalbigraphs Wehaveseenincorollary2.9thattheweightofanypartitesetofaninterval bigraphcanbeatmosttheimproprietyofthebigraph.Figure3.13andgure3.14 36 PAGE 51 Figure3.12: Changesinweightduetovariationindenition Figure3.13: Intervalbigraphwhere wt X =0 PAGE 52 Figure3.14: Intervalbigraphwhere wt X =1= imp B =1 Notethatinanybalancedpartitesetofanintervalbigraphwith imp B > 0the basepointmusthaveatleast3localcomponents.Otherwisetheweightbecomes0 andhencetheimproprietyis0,leadingtoacontradiction.Moreoverifthe wt X > 0 thenthebasepointof X musthaveatleast3localcomponentswithverticesfrom X inallthreecomponents. Denition3.3.2 Apartiteset X ofanintervalbigraph B X;Y;E is p -critical with respecttoimproprietyifandonlyif B hasimpropriety p ,andtheremovalofany vertex z 2 X decreasestheimproprietyof B . Thebalanceandcriticalityofdierentpartitesetsmightnotbethesameforan intervalbigraph.InFigure3.15wehaveillustrationsofbalanceandcriticalityofthe partitesetsofvariousintervalbigraphs.Weprovelaterinthissectionthatboththe partitesetsofanintervalbigraphcannotbebalancedand p -criticalatthesametime. Wewillnowfocusourattentiononaspecialclassofgraphs.Fortheremaining partofthissectionwewillconsiderintervalbigraphswithabalancedand p -critical partiteset.Withthisrestrictiononapartitesetofanintervalbigraphwewillprove interestingresultsaboutthestructuresofthisparticularclassofbigraphs.Thenext theoremsandlemmasgiveusanideaaboutthestructureofanintervalbigraphwith abalancedand p -criticalpartiteset. 38 PAGE 53 Figure3.15: Illustrationsofbalanceand p -criticality Theorem3.3.3 Let z beabasepointofabalanced p -criticalpartiteset X ofthe Bigraph B X;Y .IfCisanexteriorlocalcomponentof z ,thenChasexactlyone vertexfromX. Proof: Let B X;Y beanintervalbigraph.Suppose X isbalancedand p criticaland z isitsbasepoint.Wewillprovethisbycontradiction.Weusetechniques similartothoseusedbyBeyerlandJamison[3].LetCbeanexteriorlocalcomponent of z thathasatleast2vertices x;v 2 X .Let x betheclosestvertexto z suchthat itisonanedge xy and y= 2 N z .Figure3.16illustratespossiblepositionsofthe vertex x .Let H bethegraphobtainedfrom B X;Y bydeletingallthevertices fromCexceptthoseonthepathfrom z to y thatcontains x .Bytheorem3.2.8 wt H z imp H .Since X is p -critical, imp H PAGE 54 non-exteriorcomponentsremainthesame,whichimplies wt X z = wt H z : Hence wt H z imp H PAGE 55 Lemma3.3.4 Anybalancedand p -critical p> 0 partitesetofanintervalbigraph B X;Y;E hasexactlyonebasepoint. Proof: Let X beabalancedandp-criticalpartitesetofanintervalbigraph B X;Y;E .Weneedtoshowthat X hasonlyonebasepoint.Wewillprovethisby contradiction.Letusassumethat X hastwobasepointsnamely x and v .Since X is balancedand p -critical p> 0,both x and v musthaveatleast3localcomponents withverticesfrom X .Since x isabasepoint,ithasatleast3localcomponentsand v mustbeinoneofthem.Thisleadstothefollowingcases: Case1:If v 2 CwhereCisanexteriorlocalcomponentof x ,then,byTheorem 3.3.3, v istheonlyvertexfrom X inC.Thisimpliesthat v canhaveexactlyonelocal componentcontainingverticesfrom X .Thisisacontradiction. Case2:If v 2 CwhereCisanon-exteriorlocalinnercomponentof x thenevery vertexfrom Y whichisadjacentto v isalsoadjacentto x sinceCisnotexterior. Thus B v isconnected.So v hasjustonelocalcomponentwhichisacontradiction. Case3:If v 2 CwhereCisanon-exteriorlocalsidecomponentof x ,everyvertex from Y whichisadjacentto v isalsoadjacentto x becauseCisnotexterior.Wecan concludethat v againhasjustonelocalcomponent,whichisacontradiction. Thefollowingtheoremprovesthatboththepartitesetsofanintervalbigraph cannotbebalancedand p -criticalatthesametime. Theorem3.3.5 LetBX,Ybeanintervalbigraph.BothXandYcannotbebalanced and p -critical p> 0 atthesametime. Proof: Wewillprovethisbycontradiction.Letusassumethatboth X and Y are balancedand p -critical.Let v and w bethebasepointsof X and Y respectively. Since X isbalancedand p -criticaland p> 0,itsbasepointmusthaveatleast3local 41 PAGE 56 componentswithverticesfrom X .Let C 1 ;C 2 ;::C j ;::::C n be n localcomponentsof v orderedfromlefttorightand n 3.Hence v isadjacenttoatleast n verticesfrom Y .Since B isconnected, w mustbeinsomelocalcomponentof v .Let w 2 C k ;k 2 1 ; 2 ;:::n .Since Y isbalancedand p -critical, w musthaveatleast3localcomponents withonelocalcomponentcontaining v [ C i , i =1 ;:::n and i 6 = k asaninduced subgraph,whichhasatleast n )]TJ/F15 11.9552 Tf 10.742 0 Td [(1verticesfrom Y .Letuscallthislocalcomponent ofw A 1 where j A 1 Y j n )]TJ/F15 11.9552 Tf 10.949 0 Td [(1.Since n 3thereareatleast2localcomponents of v say C j ;C m and j;m 6 = k ,eachofwhichcontainsavertexfrom X notadjacentto w .Since C j and C m arecontainedin A 1 ,itimpliesthat A 1 isanexteriorcomponent of w .Since A 1 isanexteriorcomponentof w itcancontainexactlyonevertexfrom Y [Theorem3.3.3].But j A 1 Y j n )]TJ/F15 11.9552 Tf 12.513 0 Td [(1and n 3whichisacontradiction. Henceboth X and Y cannotbebalancedand p -criticalatthesametime. Nextwedeterminethegeneralstructureofanintervalbigraphthathasabalancedand p -criticalpartiteset.Thefollowinglemmaandtheoremgiveanexplicit ideaaboutthecardinalityofthelocalsidecomponentsofthebasepointofanybalancedand p -criticalpartitesetofanintervalbigraph.Thelemmagivesusthecardinalityandthefollowingtheoremusesthelemmatodemonstratethestructure.If arepresentationhasbeengiven, l v and r v willdenotetheleftandrightendpoints, respectively,oftheinterval I v representinganyvertex v . Lemma3.3.6 Let X beabalancedandp-criticalpartitesetofanintervalbigraph B X;Y and v 2 X bethebasepointof X withatmostoneexteriorcomponent.Let C 1 ;C 2 ;::::::::C n belocalcomponentsof v orderedfromlefttorightasinDenition 3.2.7.Let beaminimalintervalrepresentationsuchthat C 1 isanon-exteriorlocal sidecomponentof v in and C n istheotherlocalsidecomponent.If C j isalocal innercomponentof v suchthat j C j X j islargestamongalltheotherlocalinner componentsof v ,then j C j X j = j C 1 X j if C n isexteriorand j C j X j = j C 1 X j 42 PAGE 57 = j C n X j if C n isnon-exterior. Proof: Wewillprovethisbycontradiction.Let v 2 X bethebasepointof X withthe correspondingminimalintervalrepresentation .Thelocalcomponentsof v with respecttotheminimalintervalrepresentation are C 1 ;C 2 ;::::::::C n orderedfromleft torightwith C 1 asthenon-exteriorlocalsidecomponentand C n astheotherlocal sidecomponent.Firstlet C n beanexteriorlocalcomponentandpick j suchthat j C j X jj C i X j forall i =2 ; 3 ;:::: n )]TJ/F15 11.9552 Tf 11.955 0 Td [(1. FromDenition3.2.7, j C 1 X jj C j X j .Assumethat j C 1 X j > j C j X j , then j C 1 X j > j C i X j ;i =2 ; 3 ;:::: n )]TJ/F15 11.9552 Tf 12.198 0 Td [(1.Let x 1 2 C 1 X andlookat B )]TJ/F19 11.9552 Tf 12.198 0 Td [(x 1 . Since C 1 isnon-exterior,everyvertexfromYin C 1 adjacentto x 1 isadjacentto v . So B )]TJ/F19 11.9552 Tf 12.166 0 Td [(x 1 isstillconnected.Since j C 1 X j > j C i X j ;i =2 ; 3 ;:::: n )]TJ/F15 11.9552 Tf 12.166 0 Td [(1,removal of x 1 from C 1 doesnotaecttheweightof X .Hence wt X )]TJ/F19 11.9552 Tf 11.802 0 Td [(x 1 = wt X .Since X is p -critical,removalofanyvertexfrom X willreducetheimproprietyof B byone. Thus imp B )]TJ/F19 11.9552 Tf 11.418 0 Td [(x 1 PAGE 58 Figure3.17: Possiblestructuresofanintervalbigraphwithabalancedand p -critical partiteset then B hasoneofthefollowingstructures: i B ' B 1 where B 1 X;Y isanintervalbigraphand v isthebasepointof X which hasnlocalnon-exteriorcomponents C 1 ;C 2 ;::C i ;::::C n orderedfromlefttorightas inDenition3.2.7suchthatthereareatleast3localcomponents C 1 ;C j ;C n where j C j X j = j C 1 X j = j C n X jj C i X j ;i =2 ;:::::; n )]TJ/F15 11.9552 Tf 12.066 0 Td [(1 .Furthermoreeachof C 1 and C n hasavertexfrom Y whichisadjacenttoallverticesfrom X in C 1 and C n . 44 PAGE 59 ii B ' B 2 where B 2 X;Y isanintervalbigraphand v isthebasepointof X which hasexactlyoneexteriorcomponent C n and n )]TJ/F15 11.9552 Tf 12.855 0 Td [(1 localnon-exteriorcomponents C 1 ;C 2 ;::C i ;::::C n )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 orderedfromlefttorightasinDenition3.2.7suchthatithasat least2localcomponents C 1 ;C j where j C j X j = j C 1 X jj C i X j ;i =2 ;::::: n )]TJ/F15 11.9552 Tf 10.462 0 Td [(1 . Furthermoretheleftmostlocalcomponent C 1 hasavertexfrom Y whichisadjacent toallverticesfrom X in C 1 . iii B ' B 3 where B 3 X;Y isanintervalbigraphand v isthebasepointof X which has C 1 ;C 2 ;::C i ;::::C n localcomponentsorderedfromlefttorightwithexactlytwo exteriorcomponents C 1 ;C n andtheremaining n )]TJ/F15 11.9552 Tf 12.857 0 Td [(2 componentsarelocalinner components. Proof: B X;Y;E isanintervalbigraphwhere X isbalancedand p -critical. Weneedtoprovethat B isisomorphicto B 1 ;B 2 or B 3 dependingonthenumber ofexteriorcomponentsthebasepointof X has.Let v 2 X bethebasepointof X with n localcomponents C 1 ;C 2 ;::C i ;::::C n orderedfromlefttoright.ByLemma 3.2.6weknowthat v canhaveatmost2exteriorcomponentsandthisgivesus3cases. CaseI:If v 2 X hasnoexteriorcomponentsthenallthecomponentsof v arenonexteriorlocalcomponents.HencebyLemma3.3.6theremustbeatleast3components C 1 ;C j ;C n where j C j X j = j C 1 X j = j C n X jj C i X j ;i =2 ;::::: n )]TJ/F15 11.9552 Tf 11.904 0 Td [(1.Thus B ' B 1 . Letusnowanalyzethelocalsidecomponent C 1 .Since C 1 isnotanexteriorcomponent of v 2 X ,itcanhavemorethanonevertexfrom X .Sincetheweightof v isdetermined bythesmallest n )]TJ/F15 11.9552 Tf 12.959 0 Td [(2localinnercomponentsof v andbythepreviousLemma j C 1 X j = j C j X jj C i X j forall i =2 ; 3 ;:::: n )]TJ/F15 11.9552 Tf 11.443 0 Td [(1,thecomponent C 1 doesnot contributeanythingtowardstheweightof v .Letusassumethat j C j X j = k .Hence j C 1 X j = k .Since X isbalanced, p -criticalwith p> 0, C 1 musthaveverticesfrom 45 PAGE 60 both X and Y .Let x 1 ;x 2 ;::::::::x k 2 C 1 .Therecanbemorethanonevertexfrom Y in C 1 .Since C 1 isanon-exteriorcomponent, I y j I v 6 = forall y j 2 C 1 *. Since X isbalanced,no x i contributestotheimproprietyof v for x i 2 C 1 ,which impliesthatnoneofthe x i ;i =1 ; 2 ;::::n arecontainedin I v **. Since C 1 istheleftmostlocalcomponent,itimpliesthat l x i PAGE 61 3.4Conclusionsandfuturework Weinvestigatedthestructuresandcharacteristicsofp-improperintervalbigraphs. Thesameideascouldbenaturallyextendedtointerval k -graphs.Thesearegraphs withapropercoloringwhereeachvertex v canbeassignedaninterval I v ofthereal linesuchthattwoverticesareadjacentifandonlyiftheircorrespondingintervals overlapandeachvertexhasadierentcolor.Itwouldbeinterestingtostudythe rolesplayedbyimproprietyandcriticalityoninterval k -graphs. 47 PAGE 62 4.Characterizationofunitprobeinterval2-trees 4.1Introduction IntervalgraphswereintroducedbyHajos[22],andwerethencharacterizedbythe absenceofinducedcyclesoflengthlargerthan3andasteroidaltriplesbyLekkerkerker andBoland[26]in1962.Unitintervalgraphsaretheintervalgraphsthathavean intervalrepresentationinwhicheachintervalhasunitlength.In1969,Roberts[36] provedthattheclassesofproperintervalgraphsandunitintervalgraphscoincideand heshowedthatintervalgraphsthathavenoinduced K 1 ; 3 areunitintervalgraphs. Muchmorerecentlyin2007Gardigaveamuchshorternewconstructiveproofof Robertsoriginalcharacterizationofunitintervalgraphs[18]. Agraphisaprobeintervalgraphifthereisapartitionof V G intosets P and N andacollection f I v : v 2 V G g ofintervalsofRsuchthat,for u;v 2 V G , uv 2 E G ifandonlyif I u I v 6 = andatleastoneof u or v belongsto P .Thesets P and N arecalledtheprobesandnonprobes,respectively.If,for G aprobeinterval graph,themembersof I v : v 2 V G areclosedintervalsofidenticallength,then G isaunitprobeintervalgraph.Theprobeintervalgraphmodelwasinventedin connectionwiththetaskcalledphysicalmappingusedinconnectionwiththehuman genomeprojectbyZhangandZhanget.al.[43],[44]. Onewaytodescribethestructureofaclassofgraphsisbyndingitscompletelist ofminimalforbiddeninducedsubgraphs;Nocompleteforbiddeninducedsubgraph characterizationforgeneralprobeintervalgraphshasbeenfoundsofar.Asthe characterizationofprobeintervalgraphsseemstobedicult,researchhasfocussed onclassesofprobeintervalgraphs. Familyof2-treesarethesetofallgraphsthatcanbeobtainedbythefollowing construction:ithe2-completegraph, K 2 ,isa2-tree;iitoa2-tree Q 0 with n )]TJ/F15 11.9552 Tf 12.021 0 Td [(1 vertices n> 2addanewvertexadjacenttoa2-completesubgraphof Q 0 .LiSheng rstcharacterizedcycle-freeprobeintervalgraphs[41].Asanaturalextensionof 48 PAGE 63 thecharacterizationfortrees,PrzuljandCorneilattemptedaforbiddensubgraph characterizationof2-treesthatareprobeintervalgraphsandtheyfoundatleast62 distinctminimalforbiddeninducedsubgraphsforprobeintervalgraphsthatare2trees[34].MorerecentlyBrown,FleschandLundgrenextendedthelistto69and gaveacharacterizationintermsofsparsespinyinterior2-lobsters[7].In2009Brown, ShengandLundgrengaveacharacterizationofcycle-freeunitprobeintervalgraphs [15].In[11]variouscharacterizationsaregivenfortheprobeintervalgraphsthatare bipartite.Thesecharacterizationsareforclassesofbipartitegraphs,butnogeneral characterizationofbipartiteprobeintervalgraphsweregiventhere.Howeverrecently, BrownandLangleycharacterizedunitprobeintervalgraphsforbipartitegraphs[10]. Thischapterrestrictstotheunitcaseofprobeintervalgraphswhichare2-trees. Inthischapterwecharacterize2-treesthatareunitprobeintervalgraphs.In Section2weintroducesomeimportantsubclassesof2-trees.Inaddition,weintroduce severalbasicresultsthatwillbeusefulinthecharacterization.IntheSection3we characterize2-caterpillarsandinterior2-caterpillarsintermsofforbiddeninduced subgraphsandshowthat2-treesthatareunitprobeintervalgraphshavetobeinterior 2-caterpillars.Whilethissignicantlyreducesourfocus,itturnsouttheproblem remainsverydicult.Amajorreasonforthisisthatevendeterminingwhich2pathsareunitprobeintervalgraphsisdicult.SoinSection4wegivealistof forbiddensubgraphsfor2-pathsthatareunitprobeintervalgraphs.TheninSection 5wecompletethecharacterizationfor2-pathswhichareunitprobeintervalgraphs. InSection6weextendthelistofforbiddensubgraphsfromsection4toincludethe remainingforbiddensubgraphsforinterior2-caterpillars.InSection7wecompletethe listofforbiddensubgraphsfor2-treeunitprobeintervalgraphsusing27subgraphs. Thesizeofthelistillustratesthedicultyofthisproblem. 4.2Preliminaries 49 PAGE 64 Figure4.1: Examplesofsome2-paths Inthissectionweintroducesomesubclassesof2-trees.Alsowegiveseveralbasic resultsthatwillbeusefulthroughoutthechapter.Todescribethestructureof2-trees, weusetheideaofa2-pathintroducedbyBeinekeandPippertin[2]. Denition4.2.1 [2]A 2 -pathisanalternatingsequenceofdistinct 2 and 3 -cliques, e o ;t 1 ;e 1 ;t 2 ;e 2 ;:::;t p ;e p ,startingandendingwitha 2 -cliqueandsuchthat t i contains exactlytwodistinct 2 -cliques e i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 and e i i p .The length of 2 -pathisthe number, p ,of 3 -cliques. Ingeneral2-pathsaremuchmorecomplexthanpaths.Aswewillseelaterthat characterizationfor2-pathswhichareunitprobeintervalgraphsisverydicult. Drawingtheconnectiontotreefurther,Proskurowskiintroducedthenotionofa 2-caterpillarin[32].A2-leafisavertexwhoseneighborhoodisa2-clique. Denition4.2.2 [32]A 2-caterpillar P isa 2 -treeinwhichthedeletionofall 2 -leaves resultsina 2 -path,calledthebodyof P .A 2 -caterpillar P isan interior2-caterpillar ifforany 2 -leaf v , v isadjacenttoallverticesofsome 2 -completesubgraph e i ofany longest 2 -pathof P . IntheSection3wewillobtainacharacterizationof2-caterpillarsandinterior 2-caterpillars. Denition4.2.3 The 2-distance betweena 2 -leafandalongest 2 -pathof G isthe lengthoftheshortest 2 -pathbetweenthem. Denition4.2.4 An asteroidaltriple ATin G isaset A ofthreeverticessuch 50 PAGE 65 Figure4.2: Ontheleftisa2-caterpillar,andontherightisaninterior2-caterpillar thatbetweenanytwoverticesin A thereisapaththatavoidsallneighborsofthe third. Itiswell-knownthatintervalgraphscannotcontainasteroidaltriples.However, probeintervalgraphscancontainasteroidaltriplesprovidedtherestrictionsinthe followinglemmasareobeyed.Thefollowinglemmaswillalsobeveryusefulinproving someoftheresultsinthepresentandforthcomingsectionsspeciallyinshowingthat certain2-treesthatareprobeintervalgraphsarenotunitprobeintervalgraphs. Lemma4.2.5 [41]AtleastonevertexinanATofaprobeintervalgraphmustbea nonprobe. Lemma4.2.6 [41]IneveryATtheremustexistanon-probevertexusuchthatthere existapathbetweentheothertwoverticesintheATthathasanon-probeinternal vertex. Lemma4.2.7 [6]Thevertexofdegree3inanyinduced K 1 ; 3 ofaunitprobeinterval graphmustbeaprobeandatleasttwooftheverticesofdegree1oftheinduced K 1 ; 3 mustbenon-probes. Denition4.2.8 A k -fan isa 2 -pathoflength k suchthatall e i 'sareincidentto acommonvertexwhichwecallthecenter;allotherverticesarecalledtheradial vertices. Denition4.2.9 4-fanisa2-treemadeupoffour2-cliquessuchthatallthecliques shareoneparticularvertexcalledthecentralvertexasinFigure4.3.Thevertices 51 PAGE 66 alongthecircumferenceofthe4-fanarecalledtheradialvertices.Radialverticeswith degree2arethe endradialvertices .Thevertexwithdegree3whichisequidistantfrom boththeendradialverticeswillbecalledthe centralvertex or midradialvertex . Denition4.2.10 The Merge oftwo2-trees T i and T j takesplaceiftheintersection oftheirvertexsetisnotnull.So V T i V T j 6 = where V T i and V T j denotes thevertexsetsof T i and T j respectively. Forconvenience,wewillintroducesomenotation.Fromnowontherightend pointandleftendpointoftheintervalcorrespondingtoavertexvwillbedenoted by r I v and l I v respectively.By u $ v wewillmeanadjacencybetween u and v . WewillalsousetheacronymUPIGforunitprobeintervalgraph. Wewillnamea4-fanbyalistofsixvertices,say a )]TJ/F19 11.9552 Tf 12.375 0 Td [(b )]TJ/F19 11.9552 Tf 12.374 0 Td [(c )]TJ/F19 11.9552 Tf 12.375 0 Td [(d )]TJ/F19 11.9552 Tf 12.374 0 Td [(e )]TJ/F19 11.9552 Tf 12.375 0 Td [(f with centerat c bywhichwemean a;b;d;e;f isthepathofradialverticesand c isthe centerofthe4-fan. Lemma4.2.11 Thecenterofa4-fanmustbeaprobe,themid-radialorthecentral vertexvertexandatleastoneoftheend-radialverticesmustbenon-probes;theother twoverticesmustbeprobes. Proof: Let F = f c;r 1 ;r 2 ;r 3 ;r 4 ;r 5 g ,Ebea4-fanwhere r 1 ;:::::;r 5 ,inorder,fromthe pathwhichcontainstheradialverticesand c isthecentervertex.ByBrown,Sheng, Lundgren, c isaprobeandatmostoneof f r 1 ;r 3 ;r 5 g isaprobeandhence r 2 and r 4 mustbeprobes.Nowobservetherepresentation I r 1 = I r 2 =[0 ; 1], I c = I r 3 =[1 ; 2], I r 4 = I r 5 =[2 ; 3],workswith r 1 , r 5 asnon-probes;if r 5 isaprobeor r 1 isaprobe, then I r 3 =[0 : 5 ; 1 : 5] I r 3 =[1 : 5 ; 2 : 5]canbeused. A3-sun,denotedF1anddepictedintheFigure4.6isa2-caterpillarformedby three3-cliqueswitha2-leafonthenon-interioredgeofthe3-cliqueatthemiddle.It 52 PAGE 67 Figure4.3: 4-fan Figure4.4: Unitprobeintervalrepresentationofa4-fan Figure4.5: Anillustrationwhereunitprobeintervalrepresentationofa4-fanfails towork 53 PAGE 68 Figure4.6: F1 isawell-knownfactthatthe3-sunisnotanintervalgraph.Itiseasytoshowthatit isaprobeintervalgraph.Inthenextlemmawewillprovethatitisnotaunitprobe intervalgraph. Lemma4.2.12 The2-treeF1-sunisnotaunitprobeintervalgraph. Proof: Letusassumethat F 1isaUPIG.ItcanbeobservedfromFigure4.7that F 1is aprobeintervalgraph.Withoutlossofgenerality,byLemma4.2.5,let u 6 beanon probe.Since u 2 and u 4 areadjacentto u 6 ,sotheyareprobes.ByLemma4.2.6, u 3 mustbeanonprobe.Hence u 1 and u 5 areprobes.Wenowattempttodrawtheunit proberepresentationofF1.Weknowthat I u 3 I u 1 6 = and I u 3 I u 5 6 = .Wemake theintervalsof u 1 and u 5 asfarapartaspossible.Thus I u 3 isankedonbothsides by I u 1 and I u 5 . I u 2 and I u 4 aredrawnsuchthat r I u 1 PAGE 69 Figure4.7: Probeintervalrepresentationofa3-sunorF1 intervalgraph. Wewillnowprovethatprobeintervalgraph E 1showningure4.8isnotaunit probeintervalgraph.Wewilllaterusethesetworesults F 1and E 1donothave unitprobeintervalrepresentationstocharacterizeinterior2-caterpillars. Lemma4.2.13 The2-treeprobeintervalgraphE1showninFigure4.8isnotaunit probeintervalgraph. Proof: Weknowthat E 1isaprobeintervalgraph.Letusassumethat E 1has aunitprobeintervalrepresentation.Vertices u 2 ;u 1 ;u 3 ;u 4 ;u 5 and u 6 forma4-fanas inFigure4.8.Thevertex u 2 isthecenterofthe4-fanandsoitmustbeaprobe.The vertex u 4 isthecentralradialvertexofthesame4-fanandsoitmustbeanon-probe. AsseeninFigurethat u 4 ;u 3 ;v 1 and u 5 formaninduced K 1 ; 3 withcenterat u 4 and so u 4 mustbeaprobewhichisacontradiction.Hence E 1isnotaunitprobeinterval graph. 4.3Characterizationof 2 -caterpillars 55 PAGE 70 Figure4.8: E1 Inthissectionwesignicantlyreducetheclassof2-treesweneedtoconsiderfor unitprobeintervalgraphs.Firstwereducetheclassof2-treeunitprobeinterval graphsto2-caterpillarsandthentointerior2-caterpillars.Thusinthissectionwe giveacompletecharacterizationof2-caterpillarsandinterior2-caterpillars.Wewill seethatthecompletelistofforbiddensubgraphsfor2-treeswhichare2-caterpillars consistsof4subgraphs.Furthermorewealsoprovethatall2-treeswhichareunit probeintervalgraphsmustbeinterior2-caterpillars.Thisresultsignicantlyreduces ourspectrumfromawiderangeofgraphstoarelativelysmallclassofinterior2caterpillars. Theorem4.3.1 A2-treeisa2-caterpillarifandonlyifitdoesnotcontainB1,B1', B2,B3asinducedsubgraphs. Proof: Let G bea2-treewhichisa2-caterpillar.Bythedenitionof2caterpillar, G isa2-treesuchthatafterdeletionofall2-leavesof G wegeta2-path, calledthebodyof P .If G = B 1 ;B 1 0 ;B 2 ;B 3then G f 2-leavesof G g isnota2-path asseeninFigure4.9andso G cannotcontainthemasinducedsubgraphs. Let G bea2-treewithout B 1 ;B 1 0 ;B 2 ;B 3asinducedsubgraphs.Suppose G isnot a2-caterpillar.Let e o ;t 1 ;e 1 ;t 2 ;e 2 ;:::;t p ;e p bealongest2-pathof G andlabelit P . 56 PAGE 71 Since G isnota2-caterpillar, G f 2-leavesof G g isnota2-path.Ifevery2-leafof G werea2-leafatdistance1from P then G f 2-leaves g wouldbea2-pathwhichis acontradiction.Hence G musthavea2-leafat2-distance2ormorefrom P andthis canhappenintwoways. G hasa2-pathoflengthatleast2originatingfromsome e i orithasa2-pathoflengthatleast2originatingfromapairofverticesofsome t i notequalto e i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 or e i Case:Assumethat G hasa2-pathoflengthatleast2originatingfromsome e i .Since P isassumedtobealongest2-pathof G ,thereexistsa2-pathoflengthat least2oneithersideof e i on P .LetXbea2-pathoflength2whichoriginatesfrom 2-clique e i .Thereforethesmalleststructuresatisfyingtheseconditionsisa2-path P oflength4withXstartingfromthemiddle2-clique, e i anditslengthis2.According toPrzuljandCorneil[34],thereare2non-isomorphic2-pathsoflength4whichare A 1 4 and A 2 4 asinFigure4.10.Therstvertex x 1 ofXhas2choicesofpositionsasin Figure4.11andthesecondvertex x 2 ofXhas2choicesagain.Thereforewegetfour 2-treesubgraphs A i , i =1 ; 2 ; 3 ; 4asinFigure4.11.Observingthat A i , i =1 ; 2 ; 3 ; areisomorphicto B 1and A 4 isisomorphicto B 1 0 ,itfollowsthat G cannotcontain these2-paths.Hence G cannothave2-pathsoflength2ormoreoriginatingfrom someinterioredge e i . Case:Nowletusassumethat G hasa2-pathXoflengthatleast2originating fromapairofverticesofsome t i notequalto e i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 or e i .Since P isassumedtobea longest2-pathof G ,thereexistsa2-pathoflengthatleast2oneithersideof t i on P .LetXbea2-pathoflength2whichoriginatesfromapairofverticesofsome t i notequalto e i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 or e i .Thereforethesmalleststructuresatisfyingtheseconditions isa2-path P oflength5withXstartingfromthemiddleclique, t i anditslength is3.AccordingtoPrzuljandCorneil[34],therearethreenon-isomorphic2-paths oflength5whichare A 1 5 ;A 2 5 ;A 3 5 giveninFigure4.12.Since t i hasjustoneedge otherthan e i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 ;e i ,thereisexactlyonewaytoaddtherstvertex x 1 ofX.Let x 2 57 PAGE 72 Figure4.9: Forbiddensubgraphsfor2-caterpillar Figure4.10: Construction1 bethesecondvertexofX.Theverticesadjacentto x 2 are x 1 andoneofthevertices from N x 1 .Thuswegetsix2-trees A i ;i =1 ; 2 ; 3 ;:::; 6asinFigure4.13.Observe that A 1 ;A 2 ;A 3 ;A 4 and A 5 areisomorphicto B 3and A 6 isisomorphicto B 2.But G cannothave B 2 ;B 3asinducedsubgraphs.Hence G cannothaveany2-pathof lengthatleast2originatingfromapairofverticesofsome t i notequalto e i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 or e i . Hencefromcasesandwecanconcludethat G cannothaveany2-leafat 2-distance2ormore.So G mustbea2-caterpillar. 58 PAGE 73 Figure4.11: Construction2 Figure4.12: Construction3 59 PAGE 74 Figure4.13: Six2-treescalled A i 's Theorem4.3.2 A 2 -caterpillarisaninterior 2 -caterpillarifandonlyifitdoesnot containF1asaninducedsubgraph. Proof: Let G bea2-treewhichisa2-caterpillarwith[ e 0 ;t 1 ;:::::e n ],alongest 2-pathof G whichwecall P .Werstassumethatitisaninterior2-caterpillar.Soit cannothaveany2-leafadjacenttotheendpointsofanon-interioredge.Since F 1isa 2-caterpillarwithalongest2-pathbeing e 0 ;t 1 ;e 1 ;t 2 ;e 2 ;t 3 ;e 3 anda2-leaforiginating fromapairofverticesof t 2 notequalto e 1 or e 2 ,itisanon-interior2-caterpillar. Hence G cannothave F 1initasaninducedsubgraph. Nowweassume G isa2-caterpillarwithout F 1.If G isnotinteriorthenithas a2-pathoflength1originatingfromapairofverticesofsome t i 6 = e i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 ;e i .Since P isassumedtobealongest2-pathof G ,thereexistsa2-pathoflengthatleast1on 60 PAGE 75 eithersideof t i on P .LetXbea2-pathoflength1whichoriginatesfromapairof verticesofsome t i notequalto e i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 or e i .Thereforethesmalleststructuresatisfying theseconditionsisa2-path P oflength3withXstartingfromthemiddleclique, t 2 anditslengthis1.AccordingtoPrzuljandCorneil[34],thereisjustone2-path oflength3whichis A 1 3 depictedinFigure4.10.Thusthevertex x 1 thatformsXis adjacenttoapairofverticesin t 2 suchthat x 1 = e 1 ;e 2 .Thus x 1 canbeaddedto P injustoneway,asinnumber3ofFigure4.11whichforms F 1.Thisisacontradiction since G doesnotcontainanysubgraphisomorphicto F 1.Hence G cannothavea 2-leafatanon-interioredge.So G mustbeaninterior2-caterpillar. Theorem4.3.3 A2treeUPIGGisaninterior 2 -caterpillar Proof: Let G be2-treeunitprobeintervalgraph.If G isnota2-caterpillar then,bytheorem4.3.1,itmustcontainoneof B 1 ;B 1 0 ;B 2 ; or B 3asaninduced subgraph.FurthermoreasseeninFigure4.9 B 1and B 1 0 contains E 1, B 2and B 3contains F 1asinducedsubgraphs.Hence G shouldalsocontain E 1orF1as inducedsubgraphsprovided G isnota2-caterpillarwhichisacontradictionsince E 1and F 1areforbiddensubgraphsforunitprobeintervalgraphs.Hence G cannot contain B 1 ;B 1 0 ;B 2or B 3asinducedsubgraphs.SobyTheorem4.3.1 G mustbea 2-caterpillar. Wehaveprovedthatany2-caterpillarisinteriorifandonlyifitdoesnotcontain F 1asaninducedsubgraph.But F 1isaforbiddensubgraphforunitprobeinterval graphs.Hence G cannotcontain F 1asaninducedsubgraphandsoitmustbean interior2-caterpillar. 4.4Forbiddensubgraphsfor2-pathswhichareunitprobeintervalgraphs Interior2-caterpillarscanbethoughtofas2-pathswith2-leavesonsomeofthe interioredges.Sowhencharacterizinginterior2-caterpillarswhichareunitprobe 61 PAGE 76 intervalgraphsthenaturalstepistocharacterize2-pathswhichareunitprobeinterval graphs.Oncewehaveacompletecharacterizationofthe2-pathunitprobeinterval graphswewillkeepadding2-leavesateverypossibleinterioredgetodeterminewhich structuresfailtobeaunitprobeintervalgraphsthusderivingalistofforbidden subgraphsforinterior2-caterpillarswhichareunitprobeintervalgraphs.Aswehave mentionedearlierthecharacterizationproblemfor2-pathsinitselfturnsouttobe verydicult.Inthissectionwegivealistofforbiddensubgraphsfor2-pathswhich areunitprobeintervalgraphs.Theforbiddensubgraphsarenamedas F 2, F 3, F 4, F 5, F 6, F 7, F 8, F 9, F 10and F 11.Allofthesesubgraphsareprobeintervalgraphs buttheyfailtohaveaunitprobeintervalrepresentation. ItisworthmentioningherethatweuseeitherLemma4.2.7orLemma4.2.11 forthefollowingproofs.WeuseLemma4.2.11fortheproofsthat F 2, F 3, F 4, F 4, F 5, F 6, F 10, F 11areforbiddensubgraphsforunitprobeintervalgraphsandLemma 4.2.7forprovingthat F 7, F 8, F 9arealsoforbiddensubgraphsforunitprobeinterval graphs. Lemma4.4.1 The2-pathF2-fangiveninFigure4.14isnotaunitprobeinterval graph. Proof: Letusassumethat F 2asshowninFigure4.14isaUPIG.Itcanbe observedfromthegurethat u 2 ;u 3 ;u 4 ;u 5 ;u 6 ;u 7 and u 2 ;u 1 ;u 3 ;u 4 ;u 5 ;u 6 arevertices oftwo4-fansandbothofthemhavecenterat u 2 .Thecentralradialvertexoftherst 4-fanis u 5 andthecentralradialvertexofthesecond4-fanis u 4 .Hencebylemma 4.2.11 u 4 and u 5 mustbenon-probes.But u 4 $ u 5 andhencewegetacontradiction. Thus F 2isnotaunitprobeintervalgraph. Lemma4.4.2 The2-path F 3 giveninFigure4.15isnotaunitprobeintervalgraph. Proof: Letusassumethat F 3isaUPIG.WecanseefromFigure4.15that x )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 , x 1 , x 8 and x 10 arecentersof4-fansand x )]TJ/F17 7.9701 Tf 6.587 0 Td [(2 , x 2 , x 7 and x 11 arecentralradialvertices 62 PAGE 77 Figure4.14: F2 Figure4.15: F3 ofthefour4-fans.Also x )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 and x 1 areendradialverticesofthe4-fanswithcenters at x 1 and x )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 respectively.So x 1 and x )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 mustbeprobes.Furthermore x 8 and x 10 arealsoendradialverticesofthe4-fanswithcentersat x 10 and x 8 respectively.So x 10 and x 8 mustbeprobesaswell.Hence x )]TJ/F17 7.9701 Tf 6.586 0 Td [(3 , x 3 , x 6 and x 12 theotherendradial verticesofthe4-fansmustbenon-probes.But x 3 $ x 6 andsowegetacontradiction. Lemma4.4.3 The2-path F 4 giveninFigure4.16isnotaunitprobeintervalgraph. 63 PAGE 78 Figure4.16: F4 Proof: Letusassumethat F 4isaUPIG.WecanseefromFigure4.16that x )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 , x 1 , x 8 and x 11 arecentersof4-fansand x )]TJ/F17 7.9701 Tf 6.587 0 Td [(2 , x 2 , x 9 and x 12 arecentralradial verticesofthefour4-fans.Also x )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 and x 1 areendradialverticesofthe4-fanswith centersat x 1 and x )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 respectively.Sotheymustbeprobes.Furthermore x 8 and x 11 arealsoendradialverticesofthe4-fanswithcentersat x 11 and x 8 respectively.So theymustbeprobestoo.Hence x )]TJ/F17 7.9701 Tf 6.587 0 Td [(3 , x 3 , x 6 and x 13 theotherendradialverticesof the4-fansmustbenon-probes.But x 3 $ x 6 andsowegetacontradiction. Lemma4.4.4 The2-pathF5giveninFigure4.17isnotaunitprobeintervalgraph. Proof: Letusassumethat F 5isaUPIG.WecanseefromFigure4.17that x )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 , x 1 , x 8 and x 12 arecentersof4-fansand x )]TJ/F17 7.9701 Tf 6.587 0 Td [(2 , x 2 , x 9 and x 13 arecentralradialvertices ofthefour4-fans.Also x )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 and x 1 areendradialverticesofthe4-fanswithcentersat x 1 and x )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 respectively.So x 1 and x )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 mustbeprobes.Furthermore x 8 and x 12 are alsoendradialverticesofthe4-fanswithcentersat x 12 and x 8 respectively.So x 12 64 PAGE 79 Figure4.17: F5 and x 8 mustbeprobestoo.Hence x )]TJ/F17 7.9701 Tf 6.586 0 Td [(3 , x 3 , x 6 and x 14 theotherendradialvertices ofthe4-fansmustbenon-probes.But x 3 $ x 6 andsowegetacontradiction. Lemma4.4.5 The2-pathF6giveninFigure4.18isnotaunitprobeintervalgraph. Proof: Letusassumethat F 6isaUPIG.WecanseefromFigure4.18 x )]TJ/F17 7.9701 Tf 6.586 0 Td [(2 , x 1 , x 9 and x 12 arecentersof4-fansand x )]TJ/F17 7.9701 Tf 6.587 0 Td [(3 , x 2 , x 8 and x 13 arecentralradialvertices ofthefour4-fans.Hence x )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 and x 11 cannotbenon-probeswhicharealsotheend radialverticesforthesecondandthethird4-fan.So x 3 and x 6 theotherendradial verticesofthe4-fansmustbenon-probes.But x 3 $ x 6 andsowegetacontradiction. Lemma4.4.6 The2-pathF7giveninFigure4.19isnotaunitprobeintervalgraph. Proof: Letusconsidera2-treeprobeintervalgraph F 7asinFigure4.19. Assumethat F 7hasaunitprobeintervalrepresentation.Notethat u 4 isthecenter ofaninduced K 1 ; 3 formedby u 4 ;u 2 ;u 3 and u 6 .SobyLemma4.2.7 u 4 mustbea probe.Notethat u 6 isalsoacenterofaninduced K 1 ; 3 formedby u 6 ;u 4 ;u 7 and u 8 . So u 6 mustbeaprobeandatleasttwoof u 4 ;u 7 and u 8 mustbenon-probes.Since 65 PAGE 80 Figure4.18: F6 u 4 isaprobe, u 7 and u 8 mustbenon-probes.But u 8 isthecenterofanotherinduced K 1 ; 3 withleaves u 6 ;u 10 and u 12 andso u 8 mustbeaprobewhichisacontradiction. Lemma4.4.7 The2-pathF8giveninFigure4.20isnotaunitprobeintervalgraph. Proof: Letusconsidera2-treeprobeintervalgraph F 8whichisamergeof three4-fansasinFigure4.20withcentersat u 4 ;u 11 and u 6 .LetusassumethatF8 hasaunitprobeintervalrepresentation.Thevertex u 4 isthecenterofaninduced K 1 ; 3 formedby u 4 ;u 2 ;u 3 and u 6 so u 4 mustbeaprobe.Notethat u 6 isalsoacenter ofaninduced K 1 ; 3 withleaves u 4 ;u 7 and u 8 ;so u 6 mustbeaprobeandatleast twoof u 4 ;u 7 and u 8 mustbenon-probes.Since u 4 isalreadyaprobe,then u 7 and u 8 mustbenon-probes.Also u 9 and u 10 areadjacentto u 8 ,so u 9 and u 10 mustbe probes.Now, u 11 ;u 9 ;u 10 and u 13 formaninduced K 1 ; 3 withcenter u 11 .Soatleast twoverticesoutof u 9 ;u 10 and u 13 mustbenon-probes.But u 9 and ;u 10 areprobes, so u 13 istheonlyvertexwhichisanon-probeandhencewegetacontradiction. 66 PAGE 81 Figure4.19: F7 Lemma4.4.8 The2-pathF9giveninFigure4.21isnotaunitprobeintervalgraph. Proof: Letusconsidera2-treeprobeintervalgraph F 9whichisamergeof three4-fans G 1 ;G 2and G 3withcentersat x )]TJ/F17 7.9701 Tf 6.586 0 Td [(2 ;x 1 and x 6 asinFigure4.21.let usassumethat F 9hasaunitprobeintervalrepresentation. x )]TJ/F17 7.9701 Tf 6.587 0 Td [(2 isthecenterofan induced K 1 ; 3 formedby x )]TJ/F17 7.9701 Tf 6.587 0 Td [(2 ;x )]TJ/F17 7.9701 Tf 6.586 0 Td [(4 ;x )]TJ/F17 7.9701 Tf 6.586 0 Td [(3 and x 0 .So x )]TJ/F17 7.9701 Tf 6.587 0 Td [(2 mustbeaprobeandeither x )]TJ/F17 7.9701 Tf 6.587 0 Td [(3 Figure4.20: F8 67 PAGE 82 Figure4.21: F9 and x 0 or x )]TJ/F17 7.9701 Tf 6.586 0 Td [(3 and x )]TJ/F17 7.9701 Tf 6.587 0 Td [(4 arenon-probes.Again x 1 isthecenterofaninduced K 1 ; 3 formedby x 1 ;x )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 ;x 2 and x 3 .So x 1 mustbeaprobeandeither x )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 and x 2 or x 2 and x 3 arenon-probes. Case1:If x )]TJ/F17 7.9701 Tf 6.587 0 Td [(3 and x 0 arenon-probes,then x )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 mustbeaprobe.So x 2 and x 3 must benon-probesbyLemma4.2.7and4.2.11whichimpliesthattwoadjacentvertices x 0 and x 2 arebothnon-probeswhichisacontradiction.Hence x )]TJ/F17 7.9701 Tf 6.586 0 Td [(3 and x 0 cannotbe bothnon-probes. Case2:If x )]TJ/F17 7.9701 Tf 6.587 0 Td [(3 and x )]TJ/F17 7.9701 Tf 6.586 0 Td [(4 arenon-probesthen x )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 mustbeaprobe.So x 2 and x 3 must benon-probesbyLemmas4.2.7and4.2.11whichimpliesthat x 4 and x 5 areprobes. From G 3whosecenterisat x 6 wecanseethat x 6 ;x 4 ;x 5 and x 8 formaninduced K 1 ; 3 withcenter x 6 ,andsoatleasttwoof x 4 ;x 5 or x 8 mustbenon-probes.But x 4 and x 5 arealreadyprobesandsowegetacontradiction.HenceItisnotpossibleto constructaunitprobeintervalrepresentationof F 9. Lemma4.4.9 The2-path F 10 giveninFigure4.22isnotaunitprobeintervalgraph. 68 PAGE 83 Figure4.22: F10 Proof: Letusassumethat F 10isaUPIG.WecanseefromtheFigure4.22 that x )]TJ/F17 7.9701 Tf 6.587 0 Td [(2 , x 1 , x 7 and x 12 arecentersof4-fans.Itcanalsobeobservedthat x )]TJ/F17 7.9701 Tf 6.587 0 Td [(3 , x 2 , x 8 and x 11 arecentralradialverticesofthefour4-fans,andthusmustbenon-probes. Hence x )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 x 0 , x 9 and x 10 mustbeprobes.Eachoftheseverticesisalsooneofthe endradialverticesofthe4-fans.Sotheotherendradialvertices x )]TJ/F17 7.9701 Tf 6.586 0 Td [(4 , x 3 , x 6 and x 13 ofthe4-fansmustbenon-probes.But x 3 $ x 6 andsowegetacontradiction. Lemma4.4.10 The2-pathF11giveninFigure4.23isnotaunitprobeinterval graph. Proof: Letusassumethat F 11isaUPIG.WecanseefromtheFigure4.23 that x )]TJ/F17 7.9701 Tf 6.587 0 Td [(2 , x 1 , x 7 and x 10 arecentersof4-fanswhere x )]TJ/F17 7.9701 Tf 6.587 0 Td [(3 , x 2 , x 8 and x 12 arecentral radialverticesofthefour4-fans.So x )]TJ/F17 7.9701 Tf 6.587 0 Td [(3 , x 2 , x 8 and x 12 mustbenon-probes.Hence x )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 and x 0 mustbeprobesandtheyaretheendradialverticesof4-fanswithcenters at x 1 and x )]TJ/F17 7.9701 Tf 6.586 0 Td [(2 .Furthermore x 7 and x 10 arealsoendradialverticesofthe4-fanswith centersat x 10 and x 7 respectively.Since x 10 and x 7 arealsocenters,theymustbe probes.Hencetheotherendradialvertices, x )]TJ/F17 7.9701 Tf 6.587 0 Td [(4 , x 3 , x 6 and x 11 ofthe4-fans,must 69 PAGE 84 Figure4.23: F11 benon-probes.But x 3 $ x 6 andsowegetacontradiction. 4.52-pathunitprobeintervalgraphcharacterization Inthefollowingsectionwewillgiveacharacterizationof2-pathsthatareunit probeintervalgraphs.The2-pathcharacterizationturnedouttobequitedicult and,thecompletelistofforbiddensubgraphsforthischaracterizationincludes10 subgraphs.Inthebeginningofthesectionwewillgiveseveraldenitionswhichhave beenusedtoproceedthroughtheproofs.Wewillalsointroducesomeadditionaldefinitionsaswemovetowardsthenalgoal.Whileconstructinga2-pathwestartwith a2-completegraph, K 2 andcallit G .Nextwekeepaddingnewverticesadjacenttoa 2-completesubgraphof G suchthatthenewvertexisadjacenteithertothetwomost recentlyaddedverticesornot.Ifitisadjacenttothemostrecentlyaddedvertices wegeta2-pathwithno4-fanwhichwewillcallastraight2-pathwewillformally deneastraight2-pathlater.Ifnot,thenthenewvertex,afteraddition,either formsan F 1whichisnotallowedsinceitisnota2-pathoritcreatesa4-fan.Soat everystagewehaveexactlythreeplaceswherethenewvertexcanbeaddedprovided noinduced F 2 ::::::F 11isformedandasaresultweeithergetstraight2-paths, F 1s ormergeof4-fans.Henceitcanbeconcludedfromthediscussionsofarthatwith additionofavertextoanexisting2-patheithera4-faniscreatedornot.Thusthe 70 PAGE 85 structuresofa2-pathavoidingtheforbiddensubgraphsfrom F 2 ;::::::F 11,caneither beastraight2-pathormergeof4-fans.Atrstwegureoutthepossibleways4-fans canbemergedtoeachother. Denition4.5.1 Edge-consecutive4-fans:Let A i ;A i +1 betwo4-fans.The4-fans A i ;A i +1 willbecallededge-consecutiveif A i sharesatleastoneedgewith A i +1 , i=1,....n-1. Denition4.5.2 Vertex-consecutive4-fans:Let A i ;A i +1 betwo4-fans.The4-fans A i ;A i +1 willbecalledvertex-consecutiveif A i sharesexactlyonevertexwith A i +1 . Nowwewillprovesomeusefullemmasusingtheabovedenitionstondthe possibleshapesofa2-path.Firstwewilldealwith2-pathswhicharejustmergeof 4-fans.Asstatedearlier4-fansina2-pathcanbeeitheredge-consecutiveorvertexconsecutive.Firstwedeterminethepossiblestructuresofedge-consecutive4-fans. Lemma4.5.3 Twoedge-consecutive4-fanswithoutanF2-fancannotsharemore thantwo K 3 s. Proof: Let t 1 )]TJ/F19 11.9552 Tf 12.405 0 Td [(t 2 )]TJ/F19 11.9552 Tf 12.406 0 Td [(t 3 )]TJ/F19 11.9552 Tf 12.405 0 Td [(t 4 e 0 ;t 1 ;:::::t 4 ;e 4 bea4-fanA.letusaddanother 4-fanBtothissuchthat t 2 , t 3 and t 4 alsobelongstoB.Inotherwords t 2 , t 3 and t 4 aretheshared K 3 .Theonlywaywegeta4-fanfrom t 2 , t 3 and t 4 isbymakinga newvertexadjacentto e 4 asshowninpictureoftheFigure4.25.Itiseasytosee thatwegetanF2herewhichisacontradiction.Hencetwo4-fanscannotsharemore thantwo K 3 s. Lemma4.5.4 Twoedge-consecutive4-fanswithoutanF2-fancansharetwo K 3 s inexactlyonewayas A 4 6 intheFigure4.24. Proof: LetA1andA2betwoedge-consecutive4-fanswithoutanF2-fan suchthattheyshareexactlytwo K 3 s.Letuscallthisgraph G .SinceA1andA2 71 PAGE 86 Figure4.24: Non-isomorphic2-pathsoflength6 shareexactly2 K 3 s,then G mustcontainexactlysix K 3 s.Inotherwords G must bea2-pathoflength6.IthasbeenprovedinPrzuljandCorneilthattherearesix non-isomorphic2-pathsoflength6 A 1 6 ;A 2 6 ;A 3 6 ;A 4 6 ;A 5 6 ;A 6 6 asshowninFigure4.24.It canbeseeninthegurethat A 1 6 containsno4-fan,andthat A 5 6 ;A 6 6 haveexactlyone induced4-fan.Further A 2 6 ;A 3 6 haveaninducedF2inthem.Thus A 1 6 ;A 2 6 ;A 3 6 ;A 5 6 ;A 6 6 cannotbe G .Hence G mustbe A 4 6 Thefollowinglemmawilldeterminethepossiblestructuresanytwoedge-consecutive 4-fanswithoutanF2canhave. Lemma4.5.5 IfG1andG2aretwoedge-consecutive4-fansthatforma2-pathwith no F 2 ,thenG1andG2togetherareoneofthegraphsinFigure4.27. Proof: Let t 1 )]TJ/F19 11.9552 Tf 12.511 0 Td [(t 2 )]TJ/F19 11.9552 Tf 12.511 0 Td [(t 3 )]TJ/F19 11.9552 Tf 12.511 0 Td [(t 4 e 0 ;t 1 ;:::::;t 4 ;e 4 bea4-fan.Callit G 1 .Let G 2 beanother4-fan.Wecanmakethesetwo4-fansedge-consecutivewithoutforming aninduced F 2inthefollowingwayskeepinginmindthattheycannotsharemore thantwo3-cliques: Case1: G 1 and G 2 shareexactlytwo K 3 s: Thiscasehasbeendealtwithinthepreviouslemma.Itsconstructionisillustrated inthepictures2a,2b,2cofFigure4.25.2band2ccontainan F 1whichis nota2-pathandan F 2andsowedonotconsiderthem. Case2: G 1 and G 2 shareexactlyone K 3 : 72 PAGE 87 Figure4.25: Constructionthatshowspossiblemergeoftwo-4-fans 73 PAGE 88 Inthiscasewewillmerge G 1 = t 1 )]TJ/F19 11.9552 Tf 12.777 0 Td [(t 2 )]TJ/F19 11.9552 Tf 12.778 0 Td [(t 3 )]TJ/F19 11.9552 Tf 12.778 0 Td [(t 4 with G 2 suchthatthe3-clique t 4 becomestherst3-cliqueof G 2 .Since t 4 hastwoavailableedgestowhichthevertex from G 2 canbeadjacent,wegetexactly2waystoaddit.Oneofthewaysforman F 2asshowninpicture3cofFigure4.25andsowedonotconsideritanymore. Thusweconstruct t 4 )]TJ/F19 11.9552 Tf 12.333 0 Td [(t 0 3 of G 2 where t 0 3 isthesecond3-cliqueof G 2 .Nowatthis stagewearejustleftwith2optionsforthenextvertexfrom G 2 whichagaininturn hasjustoneoptionineachcaseforthenalvertexof G 2 .Thuswegetthestructures 3aand3boftheFigure4.25.3balsohasaninduced F 2andsowenolonger considerit. Case3: G 1 and G 2 shareexactlyoneedge: Inthiscasewewillmerge G 1 = t 1 )]TJ/F19 11.9552 Tf 11.136 0 Td [(t 2 )]TJ/F19 11.9552 Tf 11.136 0 Td [(t 3 )]TJ/F19 11.9552 Tf 11.136 0 Td [(t 4 with G 2 suchthattheedge e 4 becomes therstedgeof G 2 .Atthisstagewehaveexactlyonewaytoaddanewvertex. Afterthiswehaveexactlytwowaystoaddthenewvertex.Oneleadsto4a,4b andtheotherleadsto4c,4dofFigure4.25.Thisconstructionisillustratedin Figure4.26.Here4band4dhaveaninducedF2andsowedonotconsiderthem. 4cisanextensionof2a. Soournalstructuresaregivenby2a,3aand4aasillustratedinFigure4.25. Note:2aofFigure4.25isformediftwoedge-consecutive4-fansshareexactly two K 3 ,3aofFigure4.25isformediftwoedge-consecutive4-fansshareexactlyone K 3 and4aofFigure4.25isformediftwoedge-consecutive4-fansshareexactlyone edge. Lemma4.5.6 Ifagraphisamergeofthreegraphs G 1 ;G 2 ;G 3 whicharethreeedgeconsecutive4-fansthatforma2-pathwithno F 2 ;F 7 ;F 8 ;F 9 thenitisoneofthe followinggraphsinFigure4.31. 74 PAGE 89 Proof: Weconsider3caseshere: Case1: G 1 and G 2 shareexactlytwo K 3 sandG3shareseithertwo K 3 s,one K 3 oroneedgewith G 2 .Since2a,3aand4aasillustratedinFigure4.25arethe possiblestructureshere.Westartwith G 1 G 2 asthegraph2ainFigure4.25.So nowwehavetolookatthecasewhere G 2 canbeedgeconsecutivewith G 3 withno F 2.WeknowbyLemma4.5.5thatitcanbedoneinexactly3waysandhencewe get3structuresasshowninFigure4.28. Case2: G 1 and G 2 shareexactlyone K 3 and G 3 shareseithertwo K 3 s,one K 3 oroneedgewith G 2 .Since2a,3aand4aasillustratedinFigure4.25arethe possiblestructureshere.Westartwith G 1 G 2 asthegraph3aingure4.25.Sonow wehavetolookatthecasewhere G 2canbeedgeconsecutivewith G 3 withno F 2. Weknowbylemma4.5.5thatitcanbedoneinexactly3waysandhenceweget3 structuresasshownintheFigure4.29. Case3: G 1 and G 2 shareexactlyoneedgeandG3shareseithertwo K 3 s,one K 3 oroneedgewith G 2 .Since2a,3aand4aasillustratedinFigure4.25arethe possiblestructureshere.Westartwith G 1 G 2 asthegraph4aingure4.25.Asin thepreviouscases,nowwelookatthecasethat G 2 canbeedgeconsecutivewith G 3 withno F 2.AgainweknowbyLemma4.5.5thatitcanbedoneinexactly3ways andhenceweget3structuresasshowninFigure4.30. Since,fromFigure4.28areisomorphictofromFigure4.30,and4 fromFigure4.29respectivelyandfromFigure4.29isisomorphictofromgure 4.30,wegetsixnon-isomorphicstructureswhichareillustratedingure4.31three ofwhichareforbiddensubgraphs F 7, F 8, F 9. Wenowlookatthevertex-consecutivecase.Wealreadyknowthatedgeconsecutive4-fansarecapableofassumingexactly3structures.Thefollowingtwo lemmaswillprovethatvertex-consecutive4-fanscanassumeexactlyonestructure 75 PAGE 90 Figure4.26: Constructionoftwoedge-consecutive4-fans Figure4.27: Allpossibletwoedge-consecutive4-fansandtheirrepresentations 76 PAGE 91 Figure4.28: Formationofthreeedge-consecutive-4-fans Figure4.29: Formationofthreeedge-consecutive-4-fans 77 PAGE 92 Figure4.30: Formationofthreeedge-consecutive-4-fans Figure4.31: threeedge-consecutive-4-fans 78 PAGE 93 whichisalsoillustratedbelow. Lemma4.5.7 IfG1andG2aretwovertex-consecutive4-fansthatforma2-path withnoF2thenitisthegraphinFigure4.33. Proof: Let G bethemergeof G 1 and G 2 .Since G formsa2-path,itcannot have F 1asaninducedsubgraph.Itcanbeobservedthat G 1 and G 2 cannotshare anynon-endradialvertexsinceinthatcasethree K 3 sfromoneandone K 3 fromits complementwouldforman F 1.Hence G 1 and G 2 canshareonlytheendvertices. Henceif G 1 = u 1 )]TJ/F19 11.9552 Tf 11.855 0 Td [(u 2 )]TJ/F19 11.9552 Tf 11.856 0 Td [(u 3 )]TJ/F19 11.9552 Tf 11.855 0 Td [(u 4 )]TJ/F19 11.9552 Tf 11.856 0 Td [(u 5 )]TJ/F19 11.9552 Tf 11.856 0 Td [(u 6 withcenterat u 4 and G 2 = u 6 )]TJ/F19 11.9552 Tf 11.856 0 Td [(u 7 )]TJ/F19 11.9552 Tf 11.855 0 Td [(u 8 )]TJ/F19 11.9552 Tf -422.701 -23.98 Td [(u 9 )]TJ/F19 11.9552 Tf 10.816 0 Td [(u 10 )]TJ/F19 11.9552 Tf 10.817 0 Td [(u 11 withcenterat u 8 then u 6 isthesharedvertex.Thuswegetthepossible structureof G whichisillustratedinFigure4.33. Aconstructionof G from G 1 isalsoillustratedingure4.32. Lemma4.5.8 IfG1,G2,G3arevertex-consecutive4-fansthatforma2-pathwith noF2thenitisthegraphinFigure4.34. Proof: G 1 and G 2 shareexactlyonevertexand G 3 sharesonevertexwith G 2 . Sonowwehavetolookattheways G 2 canbevertex-consecutivewith G 3 withno F 2.Fromthepreviouslemmaweknowthatitcanbedoneinexactly1wayand hencewegetonlyonestructureasshowninFigure4.34. Nowwedenesomepossiblestructuresofa2-pathwhichhaveniceunitprobe intervalrepresentations.Therepresentationsarealsogivenbelow.Wewillalsouse theoperation+todenotemergebetween4-fans.Thesignplusisusedmostlyin Figuresforconvenience. Denition4.5.9 Straight2-path:Astraight 2 -pathisa 2 -pathwithno4-fansin thestructure.AnexampleisillustratedinFigure4.37. 79 PAGE 94 Figure4.32: Formationoftwovertex-consecutive-4-fans Figure4.33: Theonlystructurepossiblefortwovertex-consecutive-4-fans 80 PAGE 95 Figure4.34: Representationsofthreevertex-consecutive-4-fans Figure4.35: Anotherrepresentationofthreevertex-consecutive-4-fans 81 PAGE 96 Figure4.36: Threepossiblestructuresoftwoedge-consecutive4-fans Denition4.5.10 Staircase:A 2 -pathisastaircaseifitisamergeof4-fanswhere theconsecutive4-fansshareexactlytwo3-cliques.AnexampleisillustratedinFigure 4.36a. Denition4.5.11 2-snake:A 2 -pathisa 2 -snakeifitisamergeof4-fanswhere theconsecutive4-fansshareexactlytwoorone3-cliquesandthecentersofallthe 4-fansformapath.AnexampleisillustratedinFigure4.36b. Denition4.5.12 Extendedstaircase:A 2 -pathisanextendedstaircaseifitisa mergeof4-fanswheretheconsecutive4-fansshareexactlyoneedge.Thisisillustrated inFigure4.36c. Thefollowinglemmaisaveryusefulresultandhelpsalotinlaterproofswhere wegivetheunitprobeintervalrepresentationsofthe2-paths. Lemma4.5.13 The2-leavesonbothendsofa2-snakeandanextendedstaircase mustalwaysbenon-probes. Proof: Letusrstconsidera2-snakeasshowninFigure4.27.Here u 4 and u 6 arethecentersoftwo4-fans,sotheymustbeprobes.Again u 4 and u 6 arealsoone oftheendradialverticesofthe4-fanswithcenter u 6 and u 4 .Hencetheotherend radialverticesofthe4-fans u 2 and u 8 whicharealsotheend2-leavesofthe2-snake mustbenon-probes. LetusnowconsideranextendedstaircaseasshowninFigure4.27.Here x )]TJ/F17 7.9701 Tf 6.587 0 Td [(2 82 PAGE 97 Figure4.37: Straight2-path and x 1 arethecentersoftwo4-fans.Sotheymustbeprobes.Thecentralradial vertices x )]TJ/F17 7.9701 Tf 6.586 0 Td [(3 and x 2 ofthetwo4-fansmustbenon-probes.Sotheiradjacentvertices x )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 and x 0 mustbeprobes.But x )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 and x 0 arealsooneoftheendradialvertices ofthe4-fanswithcentersat x 1 and x )]TJ/F17 7.9701 Tf 6.587 0 Td [(2 respectively.Hencetheotherendradial vertices, x )]TJ/F17 7.9701 Tf 6.586 0 Td [(4 and x 3 ,whicharealsotheend2-leavesoftheextendedstaircasemust benon-probes. Lemma4.5.14 Astraight2-pathisaunitprobeintervalgraph. Proof: Itcanbeeasilyseenthatastraight2-pathdoesnothaveanyinduced K 1 ; 3 .Henceitisaunitintervalgraph.Thereforeitisaunitprobeintervalgraph. Lemma4.5.15 Astaircaseisaunitprobeintervalgraph. Proof: 83 PAGE 98 Figure4.38: Staircase Figure4.39: 2-snake 84 PAGE 99 Figure4.40: Extended-staircase+staircase Figure4.41: Staircaserepresentation 85 PAGE 100 Figure4.42: 2-snakerepresentation Figure4.43: extended-staircase+staircaserepresentation 86 PAGE 101 Let G beastaircaseasshowninFigure4.38. Let x 2 ;x 3 ;x 6 ;x 7 ;x 10 ;x 11 ;x 14 and x 15 benon-probes.Thusthenon-probesarevertices x i ;x i +1 whereistartsat i =2andiisbeingupdatedbyi:=i+3aftergetting incrementedby1ineveryiteration. ItiseasytoseefromtheFigure4.38thatifwestartcountingthe4-fansandthe edgesfromthebottomthen x 1 x 4 , x 5 x 8 , x 9 x 12 ..aretherstinterioredgesofthe rst4-fan,third4-fan,fth4-fan...respectively.Wewilldrawtheintervalsofthese verticessuchthat: I x 1 I x 4 = suchthattherightendof x 1 overlapswiththeleftendof x 4 . I x 5 I x 8 = suchthattherightendof x 5 overlapswiththeleftendof x 8 . I x 9 I x 12 = suchthattherightendof x 9 overlapswiththeleftendof x 12 . Thus I x i I x i +3 = suchthattherightendof x i overlapswiththeleftendof x i +3 . Startingat i =1,thevalueofigetsupdatedforeveryiterationby i = i +4.letus refertothefanverticesfrom x i to x i +3 for i =1 ; 5 ; 9 ;::: asverticesinboxes.Thus box k , k =1 ; 2 ; 3 ;::: correspondtovertices x i )]TJ/F19 11.9552 Tf 11.955 0 Td [(x i +3 for i =1 ; 5 ; 9 ;::: respectively. box k = f x 1+4 k )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 ;:::;x 4+4 k )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 g for box 1 ,let r I x 1 PAGE 102 Thuswehaveaunitprobeintervalrepresentationof G . Lemma4.5.16 A2-snakeisaunitprobeintervalgraph. Proof: Letusconsiderthe2-snakeinFigure4.39.Thecentralverticesofallthe4-fans involvedareprobes.Alltheverticesoftheedge-consecutive4-fansthatshareexactly one3-cliquearealsomadeprobes.Theunitprobeintervalrepresentationofa2-snake isgiveninFigure4.39. Lemma4.5.17 Anextendedstaircaseisaunitprobeintervalgraph. Proof: TheunitprobeintervalrepresentationofanextendedstaircaseisgiveninFigure 4.43. Itmustbenotedherethatmergeofextendedstaircaseswiththree4-fansdoes nothaveanyunitprobeintervalrepresentationsincetheyformaninduced F 9.It hasaunitprobeintervalrepresentationuntilthemergeoftwo4-fansbutoncethe third4-fanismergedwegetaninduced F 9.Bothanextendedstaircase-staircaseextendedstaircase-staircaseandanextendedstaircase-staircase-extendedstaircasestaircasehaveunitprobeintervalrepresentation,asshowningure4.40 Lemma4.5.18 Threeedge-consecutive4-fansthatforma2-pathhaveunitprobe intervalrepresentationifandonlyiftheydonothaveF2,F7,F8,F9asinduced subgraphs. Proof: Let G 1 , G 2 , G 3 bethreeedge-consecutive4-fansthatforma2-path.If theyhaveaunitprobeintervalrepresentationtheycannotcontain F 2 ;F 7 ;F 8 ;F 9as 88 PAGE 103 inducedsubgraphssincetheseareforbiddensubgraphsforunitprobeintervalgraphs. Fortheotherdirectionlet G 1 , G 2 , G 3 bethreeedge-consecutive4-fansthatform a2-pathwithno F 2 ;F 7 ;F 8 ;F 9asinducedsubgraphs.Bylemma4.5.6theyareone ofthegraphsinFigure4.31.Parts4,5,6ofFigure4.31formaninduced F 9 ;F 7 and F 8respectivelyandhencetheycannotbetakenintoconsideration.Sowehave toprovidetheunitprobeintervalrepresentationofparts1,2,3ofthesameFigure. Parts1and2areastaircaseanda2-snakewhoseunitprobeintervalrepresentation aregiveninFigure4.38andFigure4.39respectively,andtheunitprobeinterval representationofpart3oftheFigure4.31isgiveninFigure4.43. Lemma4.5.19 Anynumberofedge-consecutive4-fansthatforma2-pathhaveunit probeintervalrepresentationiftheydonothaveF2,F3,F4,F5,F6,F7,F8,F9, F10,F11asgeneratedsubgraphs. Proof: Let G 1 , G 2 , G 3 ,..... G n be n n> 2edge-consecutive4-fansthatform a2-pathwithno F 2 ;F 3 ;F 4 ;F 5 ;F 6 ;F 7 ;F 8 ;F 9 ;F 10 ;F 11asinducedsubgraphs. n =3:istruebytheabovelemma. n =4:Let G 1 , G 2 , G 3 , G 4 befouredgeconsecutive4-fans.Weknowthatthereare exactlythreeunitproberepresentablestructuresforthreeedge-consecutive4-fansas showninparts1,2,3oftheFigure4.31.Thusthemergeof G 1 , G 2 , G 3 mustbeone ofthosethreestructures. G 2 , G 3 , G 4 alsoformsoneofthem.Thuscorresponding toeachofthethreestructuresformedby G 1 , G 2 , G 3 wegetthreestructuresfrom G 2 , G 3 , G 4 .Thusintotalwehave10structures,fourofwhicharejustcontinuations of1,2and3ofFigure4.31.Since3isanon-symmetricstructureitscontinuation canbedonein2waysasshowninFigure4.40onebyrepeating3andtheother bydoing3andreverseof3consecutively.Wehaveaunitproberepresentationfor thestructuresthatarejustcontinuationsofthesametypeintheFigures4.38,4.39, 4.40forany n .Soweneedtofocusonstructureswhicharecombinationsofdierent 89 PAGE 104 kindsnamely1,2,3fromFigure4.31. Figures4.41,4.42,4.43givetheunitprobeintervalrepresentationforthree4-fans G 1 , G 2 , G 3 wherevertices u 1 ;u 2 ;u 3 ;u 4 ;u 5 ;u 6 areverticesformingtherst4-fanG1. Ifweaddthefourthedge-consecutive4-fanwegetthestructuresinFigures4.44, 4.45,4.46apartfromthestructuresdiscussedabove.Wewillconsiderthreecases correspondingtoFigures4.44,4.45,4.46. Case1:Figure4.44givesthepossiblestructuresobtainedfromFigure4.41. Case2:Figure4.45givesthepossiblestructuresobtainedfromFigure4.42. Case3:Figure4.46givesthepossiblestructuresobtainedfromFigure4.43. WelookatCase1rst.IfwecomparetherepresentationsinFigures4.41and4.44 itiseasytoseethattheintervalsoftheverticesof G 1 remainunchangedinboththe Figuresimplyingthattheadditionof G 4 doesnotaecttheintervalsofverticesfrom G 1 .Sotheremovalandsubsequentadditionof G 1 fromtherepresentationwillnot aecttheremainingrepresentationof G 2 , G 3 , G 4 .Furthermoreitisalsoeasytosee thattheadditionof G 1 impliesaddingatmost4verticeswhichisthecasewhen G 1 shareanedgewith G 2 andatleast2verticeswhen G 1 sharesexactly2 K 3 swith G 2 . Itcanbeseenfromthewaythesedierentrepresentationshavebeenlaidoutthat intervalsofverticesfrom G 1 G 2 thatgetaddeddonotoverlapwiththeintervalsof verticesfrom G 4 G 3 .Thesamecanbesaidabouttheothertwocases. n =5:Let G 1 , G 2 , G 3 , G 4 , G 5 beveedgeconsecutive4-fans.Wewillnowgeta representationof5veedge-consecutive4-fansinaniterativeway.Wewillrstdo therepresentationof G 3 , G 4 , G 5 .Sinceweknowthat G 2 canbeaddedto G 3 , G 4 and G 5 withoutaectingtheirrepresentationsuchthatthebiggergraph G 2 , G 3 , G 4 , G 5 hasaunitproberepresentation,werstaddtheintervalscorrespondingtothe remainingverticesof G 2 .Nowwejustconsider G 2 , G 3 , G 4 .Again,intervalsfrom G 1 canbeaddedtoitwithoutaectingtherepresentationof G 2 , G 3 , G 4 suchthat G 1 , G 2 , G 3 , G 4 hasaunitprobeintervalrepresentation.Soweaddtheremainingintervals 90 PAGE 105 Figure4.44: Fouredge-consecutive4-fans,structure1 correspondingtotheverticesof G 1 togettheunitprobeintervalrepresentationof G 1 , G 2 , G 3 , G 4 , G 5 .Alsotheintervalsfrom G 1 G 2 doesnotoverlapwiththeintervals from G 5 G 4 .Henceagainwecanconcludethatadditionof G 1 doesnotaectthe representationof G 2 , G 3 , G 4 , G 5 suchthat G 1 , G 2 , G 3 , G 4 , G 5 hasaunitprobe intervalrepresentation. Inthiswaywecankeepadding4-fanstothepresentstructuresandobtainaunit probeintervalrepresentationateverystep.Similarlywecanshowthatthisiterative processisvalidforthetheothertwocasestoo.Hencewecanconcludethatany numberofedge-consecutive4-fanshaveunitprobeintervalrepresentationiftheydo nothave F 2 ;F 7 ;F 8 ;F 9asinducedsubgraphs. Basedonthepreviousdiscussionswecanthinkofa2-pathasastraight2-path orbundlesof4-fansedgeorvertexconsecutiveortheirmerge.Sowewilllook ata2-pathasmergeofvertexoredgeconsecutive4-fansjoinedtogetherbystraight 2-paths.Thusa2-pathcanbeofthreetypes: 91 PAGE 106 Figure4.45: Fouredge-consecutive4-fans,structure2 Figure4.46: Fouredge-consecutive4-fans,structure3 92 PAGE 107 1.Groupsofedge-consecutive4-fansjoinedbystraight2-paths. 2.Groupsofvertex-consecutive4-fansjoinedbystraight2-paths. 3.AGroupofedge-consecutive4-fansjoinedbystraight2-pathwithagroupofedgeconsecutive4-fans. Thuswerstshowthateachofthegraphsobtainedfrom1,2,and3canhaveaunit probeintervalrepresentationiftheydonothave F 2, F 3, F 4, F 5, F 6, F 7, F 8, F 9, F 10, F 11asgeneratedsubgraphs. Theorem4.5.20 Groupsofedge-consecutive4-fansjoinedbystraight2-pathshave unitprobeintervalrepresentationiftheydonothaveF2,F3,F4,F5,F6,F7,F8, F9,F10orF11asgeneratedsubgraphs. Proof: Let B 1 ;B 2 ;B 3 ;:::::B m be m m 2groupsofedge-consecutive4-fans thatforma2-pathwithno F 2 ;F 3 ;F 4 ;F 5 ;F 6 ;F 7 ;F 8 ;F 9 ;F 10 ;F 11asinducedsubgraphsandtheyarejoinedbystraight2-pathsoflength n .Letuscallthisstructure G .WewillnowgiveaunitprobeintervalrepresentationofG. Let B i and B j beanytwogroupsof4-fansjoinedbyastraight2-pathoflength n .Letuscallthis B ij .Sincetherepresentationofverticeslocatedononeendof B i isindependentoftherepresentationofverticesontheotherendof B i forany B i as seenfromFigure4.27and4.34.Sowecanconcludethatifthetheoremholdsfor B ij itshouldholdfortheentire G .Sowegiveaunitprobeintervalrepresentationof B ij fordierentvaluesof n . Case1 n =0:Thisisthecasewheretheintermittentstraight2-pathisoflength0.This impliesthatwehaveamergeof B i and B j suchthatthelastedgeof B i coincides withtherstedgeof B j .Both B i and B j aregroupsofedgeconsecutive4-fans.So theirmergeinthisfashiongivesalengthiersequenceofedge-consecutive4-fanswhose lengthisequaltothesumofthelengthsof B i and B j .Bythepreviouslemma B ij 93 PAGE 108 musthaveaunitprobeintervalrepresentation. Case2 n =1:Thisisthecasewheretheintermittentstraight2-pathisoflength1.Both B i and B j aregroupsofedgeconsecutive4-fans.Soweget2sequencesofedgeconsecutive4-fansjoinedbyastraight2-pathoflengthoneasshownincase n =1 inFigure4.47.Fromrepresentationsofthefouredge-consecutive4-fansasshownin Figures4.44,4.45,4.46itiseasytoseethatthelastaddedverticesofthe2-pathsare non-probesandtheirintervalscanbemadetohavedistinctrightendpoints.Here thelastvertexof B i iseithertherstvertexof B j ortheyareadjacentasshownin Figure4.48. Letusrstconsiderthecasewhenthelastvertexof B i istherstvertexof B j .If v n )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 and v n arethelasttwoaddedverticesof B i thenintherepresentation r I v n )]TJ/F18 5.9776 Tf 5.757 0 Td [(1 PAGE 109 Both B i and B j aregroupsofedgeconsecutive4-fans.Lengthof B ij isequalto 2+length B i +length B j asshownincase n =2inFigure4.47.Weareinterested inthelasttwo4-fansof B i andthersttwo4-fansof B j .FromtherepresentationsinFigure4.27itiseasytoseethattheend2-leavesofextended-staircaseand 2-snakehavenon-proberestrictionsasshowninsecondandthirdpictureofFigure 4.27.Thustheonlystructurewhichhasnonon-proberestrictiononthe2-leafonone endisthestaircaseasshowninFigure4.27.Furthermorethe2-leafonthatendcan bemadetohaveadistinctendpoint.Thusonlywaytherecouldbeproblemsinthe representationif B i =2-snake,extendedstaircaseand B j =2-snake,extendedstaircase. AllpossiblestructuresobtainedinthiscasearegiveninFigures4.51,4.52,eachone ofwhichiseitheraforbiddensubgraphorhasaforbiddensubgraphasaninduced subgraph.Theonlypossiblestructurethatcanbeformedinthissituationisifright end2-leaffrom B i isnon-adjacenttotheleftend2-leafof B j asshownintheFigure 4.53.Sowelookatthecasewhenoneof B i or B j isastaircase.Withoutlossof generalitylet B i endinastaircase.Thedierentwaysinwhich B j canbeaddedtoit viaastraight2-pathoflength2aregiveninFigure4.54.Let v n bethe2-leafinthe rightendof B i and v n )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 isthevertexaddedjustbefore v n . V n canbeeitherprobe ornon-probe.If v n isaprobethenbythesecondrepresentationofthestaircase, I v n hasadistinctrightendpointand r I v n )]TJ/F18 5.9776 Tf 5.756 0 Td [(1 PAGE 110 Figure4.54.Theonlynon-possibilityhereisthesubcaseinpicture1ofthesame gure.Thisisthecasewhen v n isadjacentto u 1 where u 1 istheleftend2-leafof B j and u 1 isapartofa2-snakeorextendedstaircase.Inotherwords u 1 isforcedtobe anon-probesothat v n isforcedtobeaprobeandso r I v n )]TJ/F18 5.9776 Tf 5.756 0 Td [(1 PAGE 111 Figure4.47: Exampleofmergesfordierentvaluesof n Figure4.48: n =1:edge-consecutivemergefor2-paths 97 PAGE 112 Figure4.49: n =1:edge-consecutivemergefor2-paths intervalrepresentationifandonlyiftheydonothaveF2asageneratedsubgraph. Proof: Let G 1 , G 2 , G 3 bethreevertex-consecutive4-fans.Letitbeaunit probeintervalgraph.Thereforeitcannotconatain F 2asgeneratedsubgraph.Let G 1 , G 2 , G 3 bethreevertex-consecutive4-fansthatforma2-pathwithno F 2as inducedsubgraphs.SoitmustbethegraphinFigure4.34.Thesamepicturegives itsunitprobeintervalrepresentation. Note:wejustconsider F 2fortheabovelemmabecauseitistheonlystructure whichcroppedupduringtheconstructionofvertex-consecutive4-fansasseenearlier. Lemma4.5.22 Anynumberofvertex-consecutive4-fansthatforma2-pathwithout F2asageneratedsubgraphhaveaunitprobeintervalrepresentation. Proof: Let G 1 ;G 2 ;G 3 ;:::::G n be n n> 2vertex-consecutive4-fansthatform a2-pathwithno F 2asinducedsubgraphs.Weknowthateverysetof3vertex consecutive4-fans,say, A 1 = G 1 ;G 2 ;G 3 , A 2 = G 4 ;G 5 ;G 6 ,..., A k = G i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 ;G i ;G i +1 ,....has aunitproberepresentationsimilartothatinFigure4.34.Sinceallthe A j 's j = 98 PAGE 113 Figure4.50: n =1:edge-consecutivemergefor2-paths 99 PAGE 114 Figure4.51: n =2:edge-consecutivemergefor2-paths 100 PAGE 115 Figure4.52: n =2:edge-consecutivemergefor2-paths Figure4.53: n =2:edge-consecutivemergefor2-paths 101 PAGE 116 Figure4.54: n =2:edge-consecutivemergefor2-paths 102 PAGE 117 Figure4.55: n =2:edge-consecutivemergefor2-paths Figure4.56: n =3:edge-consecutivemergefor2-paths 103 PAGE 118 Figure4.57: n =3:edge-consecutivemergefor2-paths Figure4.58: n =3:edge-consecutivemergefor2-paths 104 PAGE 119 1 ; 2 ;::::k;::: areagainvertexconsecutive,theyallsharetheendvertices.Thusthe rightend2-leafof A j istheleftend2-leafof A j +1 .Hencethelast2addedvertices of A j mustbeadjacenttotherst K 2 of A j +1 suchthatthelastandrstvertex coincides.Let v i , v i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 , v i )]TJ/F17 7.9701 Tf 6.587 0 Td [(2 bethelast3addedverticesof A j .Thusif v i istheright end2-leaf A j then v i mustalsobetheleftend2-leafof A j +1 .Hence v i and v i +1 are theverticesoftherst K 2 of A j +1 .Let v i +2 bethirdaddedvertexof A j +1 .Itiseasy toseethat v i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 ;v i ;v i +1 formsa K 3 .Accordingtoarepresentation1inFigure4.34, v i )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 and v i +1 areprobesand v i isnon-probe.Moreover r I v i )]TJ/F18 5.9776 Tf 5.756 0 Td [(2 PAGE 120 impliesthatwehaveamergeof B i and B j suchthatthelastedgeof B i coincides withtherstedgeof B j .Both B i and B j aregroupsofvertex-consecutive4-fans. Hencethelast2addedverticesof B i mustbetherst K 2 of B j .Let v n )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 and v n be thelast2addedverticesof B i and u 1 , u 2 betherst K 2 of B j suchthat v n isthe rightend2-leafof B i and u 1 istheleftend2-leafof B j .Given B i thereare4waysin which B j canbeaddedtoitinthiscaseasshownintheFigure4.59.Thersttwo arethesubcaseswhentherightend2-leafof B i isadjacenttotheleftend2-leafof B j andthesecondtwoarethesubcaseswhenboththe2-leavescoincide.Pictures2 and4arenottakenintoconsiderationsincetheyformaninducedF2.Forpicture 1weusetherepresentationusedinthegure4.35.Thisisoksincerightend2-leaf of B i endwithdistinctrightendpoint,leftend2-leafof B j haveadistinctleftend pointandbothofthemareprobes.Forpicture3wemakeboththerightend2-leaf of B i andtheleftend2-leafof B j asnon-probes.Thiscanbedoneeasilysinceboth ofthemaresamehere.Thenweuserepresentation1oftheFigure4.34for B i and representation2oftheFigure4.34for B j . Case2 n =1:Thisisthecasewheretheintermittentstraight2-pathisoflength1.This impliesthatwehave B i and B j suchthatthelastvertexorrightend2-leafof B i coincideswiththeleftend2-leafof B j ortheyareadjacent.Both B i and B j are groupsofvertex-consecutive4-fans.Sointherstcaseweeithergetalengthier sequenceofvertex-consecutive4-fanswhoselengthisequaltothesumofthelengths of B i and B j plusoneoran F 2.Since F 2isavoidedandbythepreviouslemmawe knowthat B ij musthaveaunitprobeintervalrepresentation.Inthesecondcasetoo weeithergetanF2whichisavoidedorastructurethathasaunitprobeinterval representationasshownintheFigure4.60 Case3 n =2:Thisisthecasewheretheintermittentstraight2-pathisoflength2.This 106 PAGE 121 impliesthatwehave B i and B j suchthat B i and B j sharesnothingandtheright end2-leafof B i iseitheradjacenttotheleftend2-leafof B j oritisadjacenttothe othervertexoftherst K 2 of B j .Both B i and B j aregroupsofvertex-consecutive 4-fans.Soweget2sequencesofvertex-consecutive4-fansjoinedbyastraight2-path oflength2.Lengthof B ij isequalto2+length B i +length B j .Let v n betheright end2-leafof B i and u 1 betheleftend2-leafof B j suchthat v n )]TJ/F17 7.9701 Tf 6.587 0 Td [(2 , v n )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 and v n bethe last3addedverticesof B i and u 1 , u 2 , u 3 betherst3addedverticesof B j where u 1 , u 2 istherst K 2 of B j .Given B i ,thetotalpossiblewaysinwhich B j canbe addedto B i isillustratedintheFigure4.61andallofthemhaveunitprobeinterval representationsasshowninthesameFigure. Case4 n =3:Thisisthecasewheretheintermittentstraight2-pathisoflength3.This impliesthatwehave B i and B j suchthat B i and B j sharesnothingandwehave2 sequencesofvertex-consecutive4-fansjoinedbyastraight2-pathoflength3.Let v n bethe2-leafintherightendof B i and v n )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 isthevertexaddedjustbefore v n .let u 1 bethe2-leafintheleftendof B j and u 2 isthevertexaddedjustafter u 1 .The onlynon-possibilityherecouldbethecasewhenboth v n and u 1 ,theboth2-leaves areadjacentwhichturnsouttobeoksince v n canbemadeaprobesuchthatinterval of v n hasarightdistinctendpointand u 1 anon-probesuchthatintervalof u 1 hasa leftdistinctendpointasillustratedintheFigure4.62. Case5 n> 3:Thisisthecasewheretheintermittentstraight2-pathisoflengthmorethan 3.Thisimpliesthatwehave B i and B j suchthat B i and B j sharesnothingand weget2sequencesofvertex-consecutive4-fansjoinedbyastraight2-pathoflength atleast4.Lengthof B ij isgreaterthan3+length B i +length B j .Inthiscasethe twoend2-leaves,infactthetwoend K 2 sarenotadjacentsincethereisatleastone vertexbetweenthem.Moreoveralltheverticesofthestraight2-pathalsohaveno 107 PAGE 122 Figure4.59: n =0:vertex-consecutivemergefor2-paths probe-non-proberestrictiononit.Thuswecaneasilydounitproberepresentation of B ij bydoing B i rstandthencontinuingwiththeintervalsofthestraight2-path followedbytheintervalsofverticesfrom B j . Theorem4.5.24 Agroupofvertex-consecutive4-fansjoinedtoagroupofedgeconsecutive4-fansviaastraight2-pathoflengthnn 0haveaunitprobe intervalrepresentationiftheydonothaveF2,F3,F4,F5,F6F7,F8,F9,F10,F11 asgeneratedsubgraphs. Proof: 108 PAGE 123 Figure4.60: n =1:vertex-consecutivemergefor2-paths 109 PAGE 124 Figure4.61: n =2:vertex-consecutivemergefor2-paths Figure4.62: n =3:vertex-consecutivemergefor2-paths 110 PAGE 125 Let G 1 and G 2 begroupsofvertex-consecutiveandedge-consecutive4-fansrespectively.Weknowthatanynumberofedge-consecutive4-fansthatforma2-path haveunitprobeintervalrepresentationiftheydonothave F 2, F 3, F 4, F 5, F 6, F 7, F 8, F 9, F 10, F 11asinducedsubgraphs.Wealsoknowthatanynumberofgroupsof vertex-consecutive4-fanshaveunitprobeintervalrepresentationiftheydonothave F 2, F 3, F 4, F 5, F 6, F 7, F 8, F 9, F 10, F 11asinducedsubgraphs.Let v n )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 and v n bethelast2addedverticesof G 1 and u 1 , u 2 betherst K 2 of G 2 suchthat v n isthe rightend2-leafof G 1 and u 1 istheleftend2-leafof G 2 . Case1 n =0: Thelast2addedverticesof G 1 mustbetherst K 2 of G 2 . If v n isadjacentto u 1 thenwegetproblemintherepresentationfor G 2 =2-snake orextendedstair,sinceinthesecase v n )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 = u 1 and u 1 isforcedtobeanon-probe from G 2 ,but v n )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 isaprobefrom G 1 .Weget4structureshereallofwhichhave aninducedforbiddensubgraphinitasshowninFigure4.63.Thiscaseisokwith G 2 =staircaseandweavoidtheformationof5-fanssince u 1 canbemadeaprobe tooinastaircaseandweusetherepresentation3forvertexconsecutive4-fansto represent G 1 suchthat v n )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 and v n areprobeand v n hasadistinctrightendpoint asshowninFigure4.64. If v n coincideswith u 1 thenwearegoodasshowninpicture5oftheFigure4.63and intheFigure4.64. Case2 n =1: Thereexistsexactlyone K 3 between G 1 and G 2 .Wehavetwocaseshere.Eitherthe 2-leavesareadjacentortheycoincidewhicharebothokasshowningure4.65. Case3 n =2: Thereexiststwo K 3 'sbetween G 1 and G 2 .ThepossiblestructuresandtheirrepresentationsaregiveninFigure4.66.Theonlynon-possibilityiswhen G 2 =2-snake, extendedstaircasewherethethe2-leavesarealwaysnon-probesandwegetforbidden 111 PAGE 126 Figure4.63: vertex-consecutive-edge-consecutivefor2-path subgraphs F 2 ;F 8 ;F 9asshowninFigure4.67. Case4 n 3: For n 3weusethesameargumentaswehaveusedforthevertexconsecutivecase anditworksne. ThefollowingLemmawillprovethatcertain2-pathsarealwaysunitprobeintervalgraphs.Afterthiswewillgeneralizeitfurtherandcontinuetoprovethatany 2-pathwillhaveaunitprobeintervalrepresentationifandonlyifitdoesnotcontain 112 PAGE 127 Figure4.64: vertex-consecutive-edge-consecutivefor2-path Figure4.65: n =1:vertex-consecutive-edge-consecutivefor2-path 113 PAGE 128 Figure4.66: n =2:vertex-consecutive-edge-consecutivefor2-path Figure4.67: n =2:vertex-consecutive-snake-edge-consecutivefor2-path 114 PAGE 129 F 2 ;F 3 ;F 4 ;F 5 ;F 6 ;F 7 ;F 8 ;F 9 ;F 10 ;F 11asaninducedsubgraph. Lemma4.5.25 Let G bea2-pathand G 0 = G )-394(f end 2 -leavesof G g .If G 0 isa straight2-path,2-snakeorstaircase,thenGisaunitprobeintervalgraph. Proof: Case1:Let G 0 beastraight2-path.Ifweaddbacktheend2-leaves thenwegettwopossible2-paths.Weeithergetacontinuationofthestraight2-path whichhasaunitprobeintervalrepresentationorastructureasshowninFigure 4.68.Theunitprobeintervalrepresentationisalsogiveninthesamegure. Case2:Let G 0 beastaircase.Ifweaddbacktheend2-leavesthenweeithergeta5fanoracontinuationofthestaircasewhichhasaunitprobeintervalrepresentation asshowninFigure4.68.Theunitprobeintervalrepresentationisalsogiveninthe samegure. Case3:Let G 0 bea2-snake.Ifweaddbacktheend2-leavesthenweeithergeta4-fan oracontinuationofthe2-snakeasshowninFigure4.70.Theunitprobeinterval representationofboththestructuresaregiveninthesamegure. Thefollowingtheoremwillgiveacompletecharacterizationof2-pathsthatare unitprobeintervalgraphs.Inthenextsectionswewilltaketheresultonestepfurther andgureoutthecompletelistofforbiddensubgraphsforinterior2-caterpillarswhich arejust2-pathswith2-leavesadjacenttosomeofinterioredges.Sinceinterior2caterpillarsbecomesa2-pathoncethe2-leavesareremoved,sothelistofforbidden subgraphsforinterior2-caterpillarswhichhaveunitprobeintervalrepresentation mustalsoincludethelistofforbiddensubgraphsfor2-pathswhichareunitprobe intervalgraphs. Theorem4.5.26 A2-pathisaunitprobeintervalgraphifandonlyifitdoesnot haveF2,F3,F4,F5,F6,F7,F8,F9,F10,F11asgeneratedsubgraphs. Proof: Let G beany2-path.Firstwewillprovethenecessarypart.Letus assumethat G isaunitprobeintervalgraph.Since F 2, F 3, F 4, F 5, F 6, F 7, F 8, 115 PAGE 130 Figure4.68: Straight-2-path+end-2-leaves 116 PAGE 131 Figure4.69: Staircase+end-2-leaves 117 PAGE 132 Figure4.70: 2-snake+end-2-leaves F 9, F 10, F 11donothaveunitprobeintervalrepresentations,anygraphwhichhasa unitprobeintervalintervalrepresentationcannotcontainthemasinducedsubgraphs. Thusany2-pathwithanunitprobeintervalintervalrepresentationcannotcontain themasinducedsubgraphs.So G doesnothave F 2, F 3, F 4, F 5, F 6, F 7, F 8, F 9, F 10, F 11asgeneratedsubgraphs. Nowwewillprovethesucientpart.Letusassumethat G is2-pathwithout F 2, F 3, F 4, F 5, F 6, F 7, F 8, F 9, F 10, F 11asinducedsubgraphs.Since G isa2-path itcanbeconsideredasgroupsofedgeorvertexconsecutive4-fansjoinedtogether bystraight2-paths.Since G doesnotcontainanyinduced F 2, F 3, F 4, F 5, F 6, F 7, F 8, F 9, F 10, F 11bytheprevioustheoremsitmusthaveaunitprobeinterval representation. Thusitcanbeconcludedthatthecompletelistofforbiddensubgraphsforany 2-pathisgivenby F 2, F 3, F 4, F 5, F 6, F 7, F 8, F 9, F 10, F 11. 118 PAGE 133 4.6forbiddensubgraphsforinterior 2 -caterpillarswhichareunitprobe intervalgraphs Inthissectionwewillprovidealistofinterior2-caterpillarsthatdonothaveany unitprobeintervalrepresentation.Wecallthem E 1, E 2, E 3, E 4, E 5, E 6, E 7, E 8, E 9 and E 10.Wehavealreadydiscussedtheinterior2-caterpillarE1insection2where wehaveprovedthatitdoeshaveanyunitprobeintervalrepresentation.Aswehave discussedearlier,2-pathscanbeconsideredastheskeletonofinterior2-caterpillars. Soifwearelookingatinterior2-caterpillarswhichhaveunitprobeintervalrepresentationwemustrstavoidthose2-pathsthatfailtobeunitprobeintervalgraphs. Fromtheprevioussectionwehavethecompletelistofforbiddensubgraphsof2-path unitprobeintervalgraphswhichare F 2 ;F 3 ;F 4 ;F 5 ;F 6 ;F 7 ;F 8 ;F 9 ;F 10and F 11. Furthermorewealsoknowthatsincewearenowdealingwithstructuresthatcome from2-pathsbyattaching2-leavestojusttheinterioredges,thenwemustavoid F 1 whichisnota2-pathtoo.Hencerightnow,toachieveourgoal,wemustprecisely lookatinterior2-caterpillarswhoseunderlying2-pathswhichitselfisF1-freedoes notcontain F 2 ;F 3 ;F 4 ;F 5 ;F 6 ;F 7 ;F 8 ;F 9 ;F 10 ;F 11asgeneratedsubgraphsandsee whichinterioredgesinthese2-pathsonbeingattachedto2-leavesposeaproblem forthemtocontinuetobeunitprobeintervalgraphs.Tondoutexactlywhich interioredgescannothave2-leavesattached,wewillrstloadthe2-pathunitprobe intervalgraphwith2-leavesoneveryedgeandtrytondthecorrespondingunit probeintervalrepresentations.Themomentwefailtogetonewegetourforbidden subgraphandhencethelistconsistingof Ei 'sisformed.Wealsohavesomeother importantresultsinthissectionmorepreciselythefollowingthreeresultswhich helpstolocatetheverticesinaninterior2-caterpillarwhichhaveprobe,non-probe restrictions. Lemma4.6.1 Ifthereis2-leafontherstorlast K 3 ofa4-fanthenitmustbea non-probealongwiththeendradialvertexthatislocatedonthe K 3 whichhasthe 119 PAGE 134 Figure4.71: Non-proberestrictionin4-fans 2-leaf. Proof: Letusconsiderthe4-fanwitha2-leaf v 1 ontheinterioredge u 3 u 6 of theend K 3 givenby u 3 u 6 u 5 asingure4.71.Thecentralradialvertex u 4 mustbea non-probe.So u 2 and u 6 mustbeprobes.Vertices u 3 ;u 5 ;v 1 ;u 2 formaninduced K 1 ; 3 withthecenterat u 3 .Since u 2 isaprobethen u 5 and v 1 mustbenon-probes. Lemma4.6.2 If G isastraight2-pathoflength n 4 ,denotedby e 0 ;t 1 ;::::::t n ;e n thathasa2leaf v 1 whichisadjacenttoan e i suchthat i 6 =0 ; 1 ;n )]TJ/F15 11.9552 Tf 10.772 0 Td [(1 ;n asinFigure 4.72then v 1 andtheverticeswhichareoppositetotheedge e i mustbenon-probes. Proof: Wewillprovetheresultbycontradiction.Withoutlossofgeneralitywe canassumethatn=4.Let G beastraight2-path e 0 ;t 1 ;::::::t 4 ;e 4 witha2-leafat e 2 asinFigure4.72andassumethat G isalsoaunitprobeintervalgraph.letusassume 120 PAGE 135 Figure4.72: Non-proberestriction thateither u 1 ;v 1 or u 4 isaprobe. Case1:Supposethat v 1 isaprobe.Itcanbeeasilyseenfromthegurethat u 2 ;u 0 ;v 1 ;u 4 formaninduced K 1 ; 3 withthecenterat u 2 .So u 2 mustbeaprobe. Since v 1 isaprobe, u 0 and u 4 mustbenon-probes.Furthermore, u 3 ;u 1 ;v 1 ;u 5 form anotherinduced K 1 ; 3 withcenterat u 3 .So u 3 mustbeaprobe.Similarly,since v 1 isaprobe, u 1 and u 5 mustbenon-probes.Hence u 0 and u 1 botharenon-probesbut u 0 $ u 1 andhencewegetacontradiction.So v 1 mustbeanon-probe. Theproofsforthecasesthateither u 1 or u 4 areprobesissimilar.Henceall3 verticesmustbenon-probes. Itiseasytoseethat G isaunitprobeintervalgraphwithrepresentationinFigure 4.73. Lemma4.6.3 Ifthereis2-leafonthemiddle K 3 ofa3-fanasshowninFigure4.74 then,itmustbeanon-probealongwiththeendradialvertexwhichislocatedonthe K 3 whichsharesthe2-leafwiththemiddle K 3 . Proof: Letusconsiderthe3-fanwitha2-leaf v 1 ontheinterioredge u 2 u 3 ofthemiddle K 3 givenby u 2 u 3 u 4 asshowninFigure4.74.Wewillprovethisby contradiction.Letusrstassumethat v 1 isaprobe.Itisobservablethat u 2 ;u 1 ;v 1 ;u 4 121 PAGE 136 Figure4.73: Unitprobeintervalrepresentation Figure4.74: 3-fanwitha2-leaf formsaninduced K 1 ; 3 .Since v 1 isaprobethen u 1 and u 4 mustbenon-probes. Furthermore, u 3 ;u 1 ;v 1 ;u 5 formsanotherinduced K 1 ; 3 .Since v 1 isaprobeso u 1 and u 5 mustbenon-probes.Henceboth u 4 and u 5 arenon-probes.But u 4 $ u 5 .Hence wegetacontradiction.Thus v 1 mustbeanon-probe. Nowweprovethateither u 1 ;v 1 ;u 5 or u 1 ;v 1 ;u 4 mustbenon-probes.Wealready knowthat v 1 isanon-probe.Letusassumethat u 1 isaprobewhichimplies u 4 ;u 5 mustbenon-probesbythesameargumentusedwhenweshowed v 1 anon-probe. Henceweagaingetthesamecontradiction.So u 1 mustalsobeanon-probe. Thenextseverallemmasestablishthelistofforbiddensubgraphs. Lemma4.6.4 The2-treeprobeintervalgraphwhichwewilldenotebyE2asin Figure4.75isnotaunitprobeintervalgraph. 122 PAGE 137 Figure4.75: E2 Figure4.76: probeintervalrepresentationforE2 Proof: Letusassumethat E 2hasaunitprobeintervalrepresentation.The vertices u 3 and u 6 areprobessincetheyarethecentralverticesof4-fans.Also u 4 and u 7 mustbenon-probessincetheyarethecentralradialverticesofthe4-fanswith centersat u 3 and u 6 .Hence u 2 ;u 5 and u 8 mustbeprobes.Again, u 3 ;u 2 ;v 2 ;u 6 isan induced K 1 ; 3 withthecenterat u 3 .Henceeither u 2 or u 6 mustbeanon-probe.But both u 2 and u 6 areprobeswhichisacontradiction.Hence E 2isnotaUPIG. Note1:FromtheabovetwoLemmasitcanbeconcludedthattwoedgeconnected 4-fanswhichrepresenta2-snakeandhaveunitprobeintervalrepresentationcanhave 2-leavesonlyintherstorlast K 3 ofthe2-pathotherwisewewillgetforbidden 123 PAGE 138 Figure4.77: E3 subgraphs E 1 ;E 2. Lemma4.6.5 The2-treeprobeintervalgraphwhichwewilldenotebyE3asin Figure4.77isnotaunitprobeintervalgraph. Proof: Letusassumethat E 3asinFigure4.77hasaunitprobeinterval representation.Vertices u 4 and u 7 areprobessincetheyarecentersoftwo4-fans. Also u 3 and u 8 mustbenon-probessincetheyarethecentralradialverticesofthe same4-fanswithcentersat u 4 and u 7 respectively.Hence u 1 ;u 5 ;u 6 ;u 10 mustbe probes.Itisobservablethat u 4 ;u 1 ;v 1 and u 6 isaninduced K 1 ; 3 withcenterat u 4 . Henceeither u 1 or u 6 mustbeanon-probe.Butboth u 1 and u 6 areprobeswhichis acontradiction.Hence E 3isnotaUPIG. Lemma4.6.6 The2-treeprobeintervalgraphwhichwewilldenotebyE4asin Figure4.78isnotaunitprobeintervalgraph. Proof: Letusassumethat E 4asinFigure4.78hasaunitprobeinterval representation.Vertices u 4 and u 7 areprobessincetheyarecentersoftwo4-fans. Alsovertices u 3 and u 8 mustbenon-probessincetheyarethecentralradialvertices 124 PAGE 139 Figure4.78: E4 ofthesame4-fanswithcentersat u 4 and u 7 respectively.Also u 5 ;u 4 ;v 1 and u 7 isaninduced K 1 ; 3 withcenterat u 5 .Henceeither u 4 or u 7 mustbeanon-probe. Butboth u 4 and u 7 arecentersof4-fansandhencetheymustbeprobeswhichisa contradiction.Hence E 4isnotaUnitprobeintervalgraph. Note2:Fromtheabovetwolemmasitcanbeconcludedthattwoedgeconnected 4-fanswhichrepresentanextended-staircaseandhaveunitprobeintervalrepresentationcanhave2-leavesonlyintherstorlast K 3 ofthe2-pathotherwisewewill getforbiddensubgraphs E 1, E 3, E 4. Lemma4.6.7 The2-treeprobeintervalgraphwhichwewilldenotebyE5asin Figure4.79isnotaunitprobeintervalgraph. Proof: Letusassumethat E 5hasaunitprobeintervalrepresentation.By Lemma4.6.2, u 1 ;v 1 and u 4 mustbenon-probes.Hence u 3 mustbeaprobe.Also u 5 ;u 3 ;v 2 and u 6 formaninduced K 1 ; 3 with u 5 asthecentervertex.Since u 3 isa probeSo v 2 and u 6 mustbenon-probes.Hence u 6 and u 4 arebothnon-probeseven though u 6 $ u 4 whichisacontradiction.So E 5cannothaveaunitprobeinterval representation. 125 PAGE 140 Figure4.79: E5 TheprobeintervalrepresentationofE5isgiveninFigure4.80. Lemma4.6.8 The2-treewhichwewilldenotebyE6asinFigure4.81isnotaunit probeintervalgraph. Proof: Letusassumethat E 6hasaunitprobeintervalrepresentation.By Lemma4.6.2 u 1 ;v 1 and u 4 arenon-probes.Thus v 2 mustbeaprobe.Since u 2 ;u 5 Figure4.80: ProbeintervalrepresentationofE5 126 PAGE 141 Figure4.81: E6 Figure4.82: ProbeintervalrepresentationofE6 and v 2 arethe3endsofa K 13 withcenterat u 3 ,then u 2 and u 5 mustbenon-probes. Since u 4 and u 5 areadjacentandbotharenon-probes,wegetacontradiction.Hence E 6isnotaUPIG. Lemma4.6.9 The2-treeprobeintervalgraphwhichwewilldenotebyE7asin Figure4.83isnotaunitprobeintervalgraph. Proof: Letusassumethat E 7asinFigure4.83hasaunitprobeinterval representation.Vertices u 4 and u 8 areprobessincetheyarecentersoftwo4-fans. Further u 6 ;u 4 ;v 1 ;u 8 isaninduced K 1 ; 3 withcenterat u 6 .Henceeither u 4 or u 8 or bothmustbeanon-probe.Butboth u 4 and u 8 arecentersof4-fansandhencethey mustbeprobeswhichisacontradiction.Hence E 7isnotaUPIG. 127 PAGE 142 Figure4.83: E7 Note3:FromtheaboveLemmaitcanbeconcludedthatiftwo4-fansarejoined byastraight2-pathoflengthonethenthatstraight2-pathcannothaveany2-leaf onanyofitsinterioredgeotherwisewewillgettheforbiddensubgraph E 7.Inother wordstwovertex-consecutive4-fansFan1andFan2cannothaveany2-leafonthe interioredgesofthe K 3 whichcontainsthecommonvertexsharedbybothFan1and Fan2. Lemma4.6.10 The2-treeprobeintervalgraphwhichwewilldenotebyE8asin Figure4.84isnotaunitprobeintervalgraph. Proof: Letusassumethat E 8asinFigure4.84hasaunitprobeinterval representation.Vertices u 3 and u 8 arecentersoftwo4-fanswith2-leaves v 1 and v 2 ontheirend K 3 's u 3 ;u 6 ;u 5 and u 7 ;u 8 ;u 9 respectively.SobyLemma4.6.1 u 5 and u 7 mustbenon-probes.But u 5 $ u 7 whichisacontradiction.Hence E 8isnotaUPIG. Lemma4.6.11 The2-treeprobeintervalgraphwhichwewilldenotebyE9asin Figure4.85isnotaunitprobeintervalgraph. Proof: Letusassumethat E 9asinFigure4.85hasaunitprobeinterval representation.Thevertices u 4 and u 10 arecentersoftwo4-fanswith2-leaves v 1 and 128 PAGE 143 Figure4.84: E8 Figure4.85: E9 v 2 ontheirend K 3 's u 4 ;u 6 ;u 5 and u 10 ;u 8 ;u 9 respectively.Soby4.6.1 u 6 and u 8 must benon-probes.But u 6 $ u 8 whichisacontradiction.Hence E 9isnotaUPIG. Lemma4.6.12 The2-treeprobeintervalgraphwhichwewilldenotebyE10asin Figure4.86isnotaunitprobeintervalgraph. Proof: Letusassumethat E 10asinFigure4.86hasaunitprobeinterval representation.Thevertices u 2 and u 9 arecentersoftwo4-fanswith2-leaves v 1 and v 2 ontheirend K 3 s u 2 ;u 6 ;u 5 and u 7 ;u 8 ;u 9 respectively.SobyLemma4.6.1 u 6 and u 7 mustbenon-probes.But u 6 $ u 7 whichisacontradiction.Hence E 10isnota UPIG. Lemma4.6.13 The2-treeswhichwewilldenotebyGroupE 11 asinFigure4.87is notaunitprobeintervalgraph. 129 PAGE 144 Figure4.86: E10 Proof: LetusassumethatthegraphsinFigure4.87haveaunitprobeinterval representation.Weknowthat u 1 isanon-probeand u 2 whichistheleftend2leafof2-snakeorextended-staircaseisalsoanon-probe.But u 1 $ u 2 whichisa contradiction. 1 4.7Characterizationofinterior 2 -caterpillarswhichareunitprobe intervalgraphs Thisisthenalsectionofourchapter.Inthissectionwecharacterize2-tree thatareunitprobeintervalgraphs.Insection3weprovedthat2-treeunitprobe intervalgraphsareinterior2-caterpillars.Ourmaingoalwastocharacterize2-tree unitprobeintervalgraphs.Sothisresultfromsection3reducedourrangeofgraphs drasticallyandwenarrowedourconcernstojustinterior2-caterpillarswhicharejust 2-caterpillarswithoutan F 1orinotherwordsa2-pathwith2-leavesonlyonthe interioredges.Firstwejustlookedat2-pathsandthenaddedthe2-leavestonally getthecharacterizationofinterior2-caterpillarwhichareunitprobeintervalgraphs. Usingthisandthestatedresultfromsection3weproveinthissectionthat2-trees areunitprobeintervalgraphsifandonlyiftheyareinterior2-caterpillarswithout Fi 'si=1,2,......11, Ej 'sj=1,2,....10andGroup-E11.Finallywehavetheproofofthe 130 PAGE 145 Figure4.87: Group-E11-u1,u2areend2-leavesof B i and B j 131 PAGE 146 Figure4.88: Possibleplacesof2-leaves characterizationof2-treeunitprobeintervalgraphs. FromNote1,Note2andNote3oftheprevioussectionwecanconcludethattwo edge-consecutiveorvertex-consecutive4-fanswhicharealsounitprobeintervalgraphs canpossiblyhave2-leavesonlyinthefollowingmannerasillustratedinFigure4.88. Theunitprobeintervalrepresentationofpictures1,2,3,4ofthesameFigure4.88 aregiveninFigures4.89,4.93,4.90,4.944.91,4.92.Soa2-snakewithallpossible 2-leaves,astaircasewithallpossible2-leavesandanextendedstaircasewithall possible2-leavesitmustbenotedherethatanextendedstaircasebeyondamerge oftwo4-fansgivesaforbiddensubgraphfora2-pathandsowedonotconsiderit, insteadwelookatitasamergewithastaircaseor2-snakehaveaunitprobeinterval representation. letusdiscusssomeimportantpointsabouta2-path.Wewillconstructa2-path fromthebeginning.Westartwitha2-completegraph, K 2 ,whichisa2-treeandcall it G .Wekeepaddingnewverticesadjacenttoa2-completesubgraphof G suchthat 132 PAGE 147 Figure4.89: Representationof2-snakewithallpossible2-leaves Figure4.90: Representationofextendedstaircasewithall2-leaves 133 PAGE 148 Figure4.91: Representationofstaircasewithall2-leaves Figure4.92: Representationofvertex-consecutive4-fanswithall2-leaves 134 PAGE 149 Figure4.93: Representationof2-snakewithall2-leaves Figure4.94: Representationofextended-staircaseandstaircasewithall2-leaves 135 PAGE 150 Figure4.95: Edge-consecutive4-fanswithall2-leaves Figure4.96: 4-fanwithall2-leaves 136 PAGE 151 thenewvertexiseitheradjacenttothetwomostrecentlyaddedverticesornot.Ifit isadjacenttothetwomostrecentlyaddedverticeswegeta2-treewhichisastraight 2-pathof2and3cliques.Wecallitastraight2-path. Ifnotthenweeithergetan F 1ora4-fan.Afteravoidingan F 1sinceweare buildinga2-pathifanewvertexisaddedanditisadjacenttoexactlyoneofthe2 mostrecentlyaddedvertices,thenitcreatesa4-fan. Henceitcanbeconcludedfromthediscussionsofarthatwiththeadditionof avertextoanexisting2-patheithera4-faniscreatedornot.Ifnotthenwegeta straight2-path.Wealsoknowthatwhena2-pathisamergeofmorethanone4-fan itcanbeeither:anedge-consecutiveoravertex-consecutive.Keepingthese inmind,2-pathscanbecategorizedinto3groupsinageneralizedwayasfollows: 1. Z 1 :2-pathswhichareformedbygroupsofedge-consecutive4-fansjoinedby straight2-paths. 2. Z 2 :2-pathswhichareformedbygroupsofvertex-consecutive4-fansjoinedby straight2-paths. 3. Z 3 :2-pathswhichareformedbyagroupofedge-consecutive4-fansjoinedby straight2-pathstoagroupofvertex-consecutive4-fans. Fromthesedenitionswederivethreecategoriesofinterior2-caterpillarsasfollows: 1 I 1 :Interior2-caterpillarswhichareformedbyattachingtheinterioredgesof Z 1 withallpossible2-leaves. 2 I 2 :Interior2-caterpillarswhichareformedbyattachingtheinterioredgesof Z 2 withallpossible2-leaves. 3 I 3 :Interior2-caterpillarswhichareformedbyattachingtheinterioredgesof Z 3 withallpossible2-leaves. Fromthepreviousresultsonthecharacterizationof2-pathsweknowthatthere exists3possiblestructuresfortwoedge-consecutive4-fansandonepossiblestructure fortwovertex-consecutive4-fans.Inthecaseofedge-consecutivetheyhavespecic 137 PAGE 152 namesasgiveninFigure4.27:astaircase b2-snake cextendedstaircase ThevertexconsecutivestructureisgivenbyFigure4.95.Wealsoknowthat boththe2-leavesofa2-snakeandextended-staircasehaveanon-proberestriction bylemma4.5.13.Furthermoreany2-leafonaninterioredgeoftherstorlast K 3 ofa4-fanmustalsobeanon-probe.Fromtheunitprobeintervalrepresentationofall thethreepossibletwoedge-consecutive4-fansandonepossibletwovertex-consecutive 4-fanswithallthepossible2-leaves,wecanconcludethattheintervalsof2-leaves canbeaddedtothemwithoutdisturbingtheintervallayoutoftheunderlying2-path suchthattheresultantgraphisalsoaUPIG.Furthermoreitisalsoworthnoting herethat E 1 ;E 2 ;E 3 ;E 4 ;E 7 ;E 8,GroupE 11aretheonlyforbiddensubgraphswhose underlying2-pathsareeitheredgeorvertexconsecutive4-fans.Therestarerelated tostraight2-paths.Wewillusethesefactstoprovethefollowinglemmas. Lemma4.7.1 Anynumberofedgeconsecutive4-fanswithallitspossible2-leaves thatformsa2-pathwithoutthe2-leaveshasaunitprobeintervalrepresentationif andonlyifthereisnoinducedF2,F3,F4,F5,F6,F7,F8,F9,F10andF11and E1,E2,E3,E4,E5,E6andE8init. Proof: Firstweprovethenecessarypart.Let G be n edgeconsecutive4-fans f 1 ;f 2 ;:::::::::f n withallpossible2-leaves.If G isunitaprobeinterval graphthen G cannotcontain F 2, F 3, F 4, F 5, F 6, F 7, F 8, F 9, F 10, F 11and E 1 ;E 2 ;E 3 ;E 4 ;E 5 ;E 6and E 8asinducedsubgraphs. Nowweprovethesucientpart.Let G be n edgeconsecutive4-fans f 1 ;f 2 ;:::::::::f n withallpossible2-leavesandnoinduced F 2, F 3, F 4, F 5, F 6, F 7, F 8, F 9, F 10, F 11, E 1, E 2, E 3, E 4, E 5, E 6and E 8init.Wewilltrytogetaunitprobeintervalrepresentationof G .Itcanbeobservedthatoutofalltheforbiddensubgraphs 138 PAGE 153 with2-leavesonly E 1 ;E 2 ;E 3 ;E 4 ;E 5 ;E 6and E 8canoccurinthecaseofedgeconsecutive4-fansandsoweavoidjustthesesubgraphsapartfromallthe Fi 'sto avoidanyproblemtowardstherepresentationof G .LetG'= G --leaves.SinceG' isa2-pathwithout F 2 ;F 3 ;F 4 ;F 5 ;F 6 ;F 7 ;F 8 ;F 9 ;F 10and F 11,soG'hasaunit probeintervalrepresentation.NowwelookatG'asmergeoftwoedge-consecutive 4-fans f 1 f 2 ;f 2 f 3 ;:::::f i f i +1 ;::::: .FromFigures4.89,4.90,4.91whichgivesdierent possiblemergeoftwoedge-consecutive4-fanswithallpossible2-leavessuchthat noEi'sareformedasinducedsubgraphsinit,itcanbeconcludedthattheintervalsof2-leavescanbeaddedtoeachoftheseblockswithoutdisturbingtheinterval layoutoftheunderlying2-pathsuchthattheresultantgraphisalsoaUPIGand the2-leavesdoesnothaveanydistinctendpoint.Sono2-leaf-intervalfromblock f i )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 willoverlapwithintervalsfrom f i +1 .Moreoverallthe2-leavesarenon-probes sothattheiroverlappingwitheachothernevermatters.Wenowstartaddingthe intervalsof2-leavestotherepresentationofG'.Furthermore,since G cannothave E 1 ;E 2 ;E 3 ;E 4 ;E 7 ;E 8therearexedplaceswherethe2-leavesgetattachedtoG'. Henceaddingthe2-leavesof f 1 f 2 rstandinsertingthenewintervalscorresponding tothe2-leavesintherepresentationofG'doesnotgetaectedbythesuccessive additionof2-leafintervalsfor f 2 f 3 no2-leafintervalfrom f 3 overlapswithintervals from f 1 ,2-leafintervaladditionsalsodoesinitiateanychangeintherepresentationof theunderlying2-pathandoverlapping2-leavesdoesnotaecteachothersadjacency sincetheyareallnon-probes.Theadditionofintervalsof2-leavesisdone,keeping inmindthatno E 1 ;E 2 ;E 3 ;E 4 ;E 7 ;E 8isformedinthetransitionofG'to G ,tillthe wholegraphhasbeencovered.Thuswegetaunitprobeintervalrepresentationof G . Wenowlookattwovertexconsecutive4-fanswhichisaunitprobeintervalgraph fromtheprevioussectionwithallpossible2-leavesandgureouttheinterioredges wherewecanadd2-leaveswithoutdisturbingtheunitprobeintervalrepresentation 139 PAGE 154 ofthe2-path. Theorem4.7.2 Twovertex-consecutive4-fanswithallpossible2-leaveswithoutE1, E5,E6,E7hasaunitprobeintervalrepresentationasshowninFigure4.97. Proof: Let G betwovertex-consecutive4-fanswithmaximumpossible2-leavesasin Figure4.97.Wewillgiveaunitprobeintervalrepresentationof G . Weknowthatthemiddleedges u 7 u 8 and u 12 u 13 ofthe4-fanscannothave2-leaves otherwisewewillgetan E 1.Furthermoreonanypartofthebodyof G whichhasat leastsixconsecutive K 3 s,ifedge e k hasa2-leafthenitsnextnearest2-leafmustbeon theedge e k +3 otherwisewewillgettheforbiddensubgraphs E 5 ;E 6.Alsoitcannot haveany2-leafontheinterioredgeofthe K 3 thatmergesthetwo4-fansotherwise wewillgetaninduced E 7. Unitprobeintervalrepresentationof G : Letallthe2-leavesbenon-probes.Ifthe2-leaf v i isadjacenttotheedge e i then theverticesoppositetotheedge e i inthe K 0 3 s t i and t i +1 arealsonon-probes.We willconsidertheverticesfrom u 5 )]TJ/F19 11.9552 Tf 12.278 0 Td [(u 10 in G .Letuscallthis4-fan f i .Thus f i has u 5 ;u 6 ;u 7 ;u 8 ;u 9 ;u 10 ;v 3 and v 4 init.Wewillgivetheunitproberepresentationofthe verticesof f i andusingthethesamemethodwecangettheunitproberepresentations ofthenext4-fan u 10 )]TJ/F19 11.9552 Tf 10.18 0 Td [(u 15 called f j andnallywewillmergethesetworepresentations togettherepresentationof G .Wewillrstdrawtheintervalscorrespondingtothe non-2-leaveswhicharedenotedby u i sasinFigure4.97. In f i : r I u 5 PAGE 155 AlltheseareillustratedintheFigure4.97 Inthe f j : r I u 8 PAGE 156 Figure4.97: Vertexconsecutive4-fanswithall2-leaves 142 PAGE 157 Proof: Let G be n vertexconsecutive4-fans f 1 ;f 2 ;:::::::::f n withallpossible2-leaves.If G hasunitprobeintervalrepresentationthen G mustnotcontain F 2 ;E 1 ;E 5 ;E 6 ;E 7asinducedsubgraphsinit. Nowweprovetheotherdirection.Let G be n vertexconsecutive4-fans f 1 ;f 2 ;:::::::::f n withallpossible2-leaves. G doesnotcontainany F 2, E 1, E 5, E 6, E 7asinducedsubgraphsinit.Wewillprovethat G isaunitprobeintervalgraph. LetG'= G --leaves.G'isa2-pathmadeofvertex-consecutive4-fanswithout F 2 andsoG'hasaunitprobeintervalrepresentation.NowwelookatG'asmergeof twovertex-consecutive4-fans f 1 f 2 ;f 2 f 3 ;:::::f i f i +1 ;::::: .FromFigure4.97,itcanbe concludedthattheintervalsof2-leavescanbeaddedtoeachoftheseblockswithout disturbingtheintervallayoutoftheunderlying2-pathsuchthattheresultantgraph isalsoaUPIG.Itisalsoeasytoseethatoutofalltheforbiddensubgraphswith 2-leavesonly E 1 ;E 5 ;E 6 ;E 7canoccurinthecaseofvertex-consecutive4-fansandso weavoidjustthemapartfromthe F 2intheunderlyingstructure.Furthermore,itis alsoeasytoseefromthesamegurethatno2-leaffromanyinterioredgehasdistinct leftorrightendpointandsoitcanbeconcludedthattheinterior2-leaves,when addedtotheseblocks,doesnotoverlapwithanyintervaloutsidetheblock.Henceno 2-leafintervalfrom f j f j +1 overlapswithanyintervalfrom f j )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 and f j +1 .Also,wecan concludefromthesamegure,thattheremovalofintervalscorrespondingtothe2leavesfrominterioredgessuchthatweobtain2-pathswhicharevertex-consecutive 4-fansofanytwovertex-consecutive4-fans f i f i +1 doesnotaecttheunitprobe intervalrepresentationoftheunderlying2-pathoftheblock.Soafterthe2-leaves areaddedtoG',itcannotaecttherepresentationofany f i f i +1 .Sinceanynumber ofvertexconsecutive4-fanswhichforma2-pathisaunitprobeintervalgraph,we rstdotheunitproberepresentationofG'.Sincetheadditionof2-leavesonany twovertex-consecutive4-fans f i f i +1 isindependentoftheunitproberepresentation oftheunderlying2-pathandtherestoftheblocks,wecaneasilyaddtheintervals 143 PAGE 158 correspondingtotheinterior2-leavestotherepresentationofG'andnallygeta unitprobeintervalrepresentationof G . Wewillnowtakeeachof I 1 , I 2 , I 3 intoconsiderationsuchthatnowherethe forbiddensubgraphs E 1, E 2, E 3, E 4, E 5, E 6, E 7, E 8, E 9, E 9, E 10 ; GroupE 11, F 2, F 3, F 4, F 5, F 6, F 7, F 8, F 9, F 10, F 11areformedasinducedsubgraphsand giveaunitprobeintervalrepresentationforeachofthem. Theorem4.7.4 Interior 2 -caterpillarsgivenbystructuresisomorphictomergeof I 1 haveunitprobeintervalrepresentationifandonlyiftheydonothaveE1,E2,E3, E4,E5,E6,E7,E8,E9,E9,E10,F2,F3,F4,F5,F6,F7,F3,F8,F9,F10,F11as inducedsubgraphs. Proof: Let B 1 ;B 2 ;B 3 ;:::::B m be m m 2groupsofedge-consecutive4fanswithallpossible2-leavesandtheyarejoinedbystraight2-pathsoflength n n =0 ; 1 ; 2 :::: withallpossible2-leaves.Thisstructureisisomorphictomergeof I 1 andwewillcallit G .If G hasaunitprobeintervalrepresentationthenitmustnot contain E 1, E 2, E 3, E 4, E 5, E 6, E 7, E 8, E 9, E 10, F 2, F 3, F 4, F 5, F 6, F 7, F 8, F 9, F 10, F 11asinducedsubgraphs. Nowweprovetheotherdirection.Let B 1 ;B 2 ;B 3 ;:::::B m be m m 2groupsof edge-consecutive4-fanswithallpossible2-leavesthatarejoinedbystraight2-pathsof length n n =0 ; 1 ; 2 :::: withallpossible2-leavessuchthatithasno E 1, E 2, E 3, E 4, E 5, E 6, E 7, E 8, E 9, E 10, F 2, F 3, F 4, F 5, F 6, F 7, F 8, F 9, F 10, F 11asinduced subgraphs.Letusagaincallthisstructure G .Thus G isamergeof I 1 withoutthe forbiddensubgraphs.Wewillnowgiveaunitprobeintervalrepresentationof G for dierentvaluesof n . Let B i and B j beanytwogroupsofsuch4-fansjoinedbysuchastraight2-pathof length n .Letuscallthis B ij anditisisomorphicto I 1 .FromFigures4.96,4.89,4.91, 4.90itcanbeobservedthattherepresentationoftheverticesononeendofa4-fan 144 PAGE 159 oredge-consecutive4-fanswithall2-leavesdoesnotaectthevertexrepresentation ontheotherend.Sowecanusethesamestrategyforrepresentationonbothends andhenceifthetheoremholdsfor B ij itshouldholdfortheentire G .Henceitis sucienttogiveaunitprobeintervalrepresentationof B ij fordierentvaluesof n . Furthermore,since B i and B j haveallpossible2-leavesandtheyaremergeofedge consecutive4-fanssothelastandrst K 3 softheunderlying2-pathofboth B i and B j musthavea2-leafinitsinterioredge.Hencethelastaddedvertexontheright endof B i if B i isassumedtobeconstructedfromtheleftandtherstaddedvertex ontheleftendof B j mustallbenon-probes. Case1 n =0:Thisisthecasewheretheintermittentstraight2-pathisoflength0.This impliesthatwehaveamergeof B i and B j suchthatthelastedgeof B i coincides withtherstedgeof B j .Both B i and B j aregroupsofedgeconsecutive4-fanswith everypossible2-leave.Sowegetalengthiersequenceofsuchedge-consecutive4-fans whoselengthisequaltothesumofthelengthsof B i and B j .Bylemma4.7.1 B ij musthaveaunitprobeintervalrepresentation. Case2 n =1:Thisisthecasewheretheintermittentstraight2-pathisoflength1.This impliesthatwehaveamergeof B i and B j suchthat B i and B j sharesexactlyone vertex.Both B i and B j aregroupsofedgeconsecutive4-fanswithallpossible2leaves.Sowegettwosequencesofedge-consecutive4-fanssharingacommonvertex whoselengthisequalto1+length B i +length B j .Wehave2caseshere.Thelast addedvertexof B i iseithertherstaddedvertexof B j orthelastaddedvertexof B i isadjacenttotherstaddedvertexof B j . Letusrstconsiderthecasewhenthelastvertexof B i istherstvertexof B j .If u n )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 and u n arethelasttwoaddedverticesof B i inorderand u n )]TJ/F17 7.9701 Tf 6.586 0 Td [(2 isthecenterofthelast 4-fanof B i thenbytherepresentationintheFigure4.96, r I u n )]TJ/F18 5.9776 Tf 5.756 0 Td [(2 PAGE 160 or r I u n )]TJ/F18 5.9776 Tf 5.756 0 Td [(2 PAGE 161 Case4 n =3:Thisisthecasewheretheintermittentstraight2-pathisoflength3.Both B i and B j aregroupsofedgeconsecutive4-fanswithallpossible2-leaves.Soweget 2sequencesofsuchedge-consecutive4-fans B i and B j joinedbyastraight2-pathof length3withallpossible2-leaves.Lengthof B ij isequalto3+length B i +length B j . Wewilllookatthelast4-fanof B i andtherst4-fanof B j withallpossible2-leaves init.Asdiscussedinthepreviouscase,since B i and B j haveallpossible2-leaves, thenthelastandrst K 3 softheunderlying2-pathofboth B i and B j musthavea 2-leafonitsinterioredge.Hencethelastaddedvertexontherightendof B i andthe rstaddedvertexontheleftendof B j mustallbenon-probes.Theonlypossible structuresthatcanformhereareillustratedinFigure4.101.Inothercasesweget adjacenciesbetweennon-probeverticeswhichgivesustheforbiddensubgraph E 9. TheunitproberepresentationsofthestructuresintheFigure4.101isgiveninthe samegure.Thesestructuresarepossiblebecausetherightend2-leaffrom B i or u n isnon-adjacenttotheleftend2-leafof B j or w 1 asshowninthesamegure. Furthermoreitcanbeeasilyseenfromthesestructuresthatwecannothaveany 2-leafontheinterioredgesoftheintermittent2-pathinpicture1ofthesamegure sincethatwillformeitheran E 1oran E 2,andwealsocanhaveexactlyone2-leaf ononeinterioredgeoftheintermittent2-patheitheron u n a or w 2 a asshownin picture2otherwisewewillgettheforbiddensubgraph E 6ifboththe2-leaveswere present,andwealsowillgeteitheran E 7or E 2ifthereisa2-leafon u n u n )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 or w 1 w 2 respectively. Case5 n =4:Thisisthecasewheretheintermittentstraight2-pathisoflength4.Both B i and B j aregroupsofedgeconsecutive4-fanswithallpossible2-leaves.Soweget 2sequencesofsuchedge-consecutive4-fansjoinedbyastraight2-pathoflength4 withallpossible2-leaves.Thelengthof B ij isequalto4+length B i +length B j . 147 PAGE 162 Asbefore,wewilllookatthethelast4-fanof B i andtherst4-fanof B j withall possible2-leavesinit.Since B i and B j haveallpossible2-leaves,thenthelastand rst K 3 softheunderlying2-pathofboth B i and B j musthavea2-leafinitsinterior edge.Hencethelastaddedvertexontherightendof B i B i , B j areassumedto beconstructedfromtheleftandtheintervalsofverticesof B i , B j areplacedfrom theleftandtherstaddedvertexontheleftendof B j mustallbenon-probes. TheonlypossiblestructuresthatcanformhereareillustratedinFigure4.102.In othercasesweeithergetadjacenciesbetweennon-probeverticeswhichgivesusthe forbiddensubgraphs E 2 ;E 3 ;E 4 ;E 5 ;E 10orgetan F 2intheunderlying2-path.The unitproberepresentationsofthestructuresinFigure4.102isgiveninthesame gure.Therepresentationofthesestructuresarepossiblebecausetherightend2leaffrom B i isnon-adjacenttotheleftend2-leafof B j asshowninthesamegure. Furthermoreitcaneasilybeseenfromthesestructuresthatwecannothaveany2-leaf ontheinterioredgesoftheintermittent2-pathinpicture1ofthesameguresince thatwillformeitheran E 3oran E 4andwealsocanhaveexactlyone2-leafonone interioredgeoftheintermittent2-pathasshowninpicture2otherwisewewillgetthe forbiddensubgraph E 2 ;E 5 ;E 6 ;E 10.Theunitprobeintervalrepresentationof1and 2canbedonebyrepresenting B i rstasinrepresentationsofgure4.89,4.90,4.91 followedbytherepresentationofthestraight2-pathasinFigure4.103andnally representing B j againinthesamemanner.Picture3isisomorphicto2.Theunit probeintervalrepresentationofpicture4isgiveninthesamegure.Thisispossible sincetheend2-leavesofa2-snake,extended-staircaseandstaircasecanbemadeto havedistinctendpointswhichalsocanbeseenfromsamegures4.89,4.90,4.91.It canbenotedherethatPicture4istheonlydierentcaseherewhoserepresentation isgiveninthesamegure.Thiscaseisthestructurecontainingastraight2-pathof length10and3fromtheend4-fansand4fromtheintermittentstraight2-path oflength4. 148 PAGE 163 Furthermoreonanypartofthestructurewhichhasatleastsixconsecutive K 3 s,if edge e k hasa2-leafthenitsnearest2-leafmustbeontheedge e k +3 , e k )]TJ/F17 7.9701 Tf 6.587 0 Td [(3 otherwise wewillgettheforbiddensubgraphsasshowninthepicture4ofthesameFigure. Case6 n> 4:Thisisthecasewheretheintermittentstraight2-pathisoflengthgreaterthan 4.Both B i and B j aregroupsofedgeconsecutive4-fanswithallpossible2-leaves. Soweget2sequencesofsuchedge-consecutive4-fansjoinedbyastraight2-pathof lengthgreaterthan4withallpossible2-leaves.Itcanbeconcludedfromtheprevious casestudythatifweconstructallthepossiblestructureswecangettwotypesof structuresasgivenbytheFigure4.102. Type1:Thesestructurescanberepresentedbydoing B i rstasintherepresentations ofthegure4.89,4.90,4.91followedbytherepresentationofthestraight2-pathas intheFigure4.103andnallyrepresenting B j againinthesamemanner. Type2:Structuresjoinedbystraight2-pathsoflengthsatleast11withallpossible 2-leavesatleast5fromtheintermittentstraight2-pathsand3eachfromthe4-fans ontwoends.The2-leavesontheinterioredgesofthestraight2-pathsarepresent sothatnoforbiddensubgraphsisformed.Soasstatedbefore,ifedge e k hasa2leafthenitsnearest2-leafmustbeontheedge e k +3 , e k )]TJ/F17 7.9701 Tf 6.587 0 Td [(3 .Theunitprobeinterval representationofsuchstructuresarepossiblebecausetheend2-leavesofthe4-fans ontwoendswhicharepartsofthestraight2-pathcanbemadetohavedistinctend pointsandthentheintermittentstraight2-pathcanberepresentedasintheFigure 4.103. Furthermoreonanypartofthestructurewhichhasatleastsixconsecutive K 3 s,if edge e k hasa2-leafthenitsnearest2-leafmustbeontheedge e k +3 , e k )]TJ/F17 7.9701 Tf 6.587 0 Td [(3 otherwise wewillgetforbiddensubgraphs. 149 PAGE 164 Figure4.98: n =1: I 1 Nowwelookatinterior2-caterpillarsisomorphicto I 2 whicharederivedfrom vertexconsecutive4-fansjoinedbystraight2-paths.Inthefollowingtheoremwegive aunitprobeintervalrepresentationofsuchinterior2-caterpillarswhentheydonot containanyoftheforbiddensubgraphsasinducedsubgraphsinit. Theorem4.7.5 Interior 2 -caterpillarsgivenbystructuresisomorphictomergeof I 2 haveunitprobeintervalrepresentationifandonlyiftheydonothaveE1,E2,E3, E4,E5,E6,E7,E8,E9,E9,E10,F2,F3,F4,F5,F6,F7,F3,F8,F9,F10,F11as inducedsubgraphs. Proof: Let B 1 ;B 2 ;B 3 ;:::::B m be m m 2groupsofvertex-consecutive4fanswithallpossible2-leavesthatarejoinedbystraight2-pathsoflength n withall possible2-leaves.Thisstructureisisomorphictomergeof I 2 andwewillcallit G .If G hasaunitprobeintervalrepresentationthenitmustnotcontain E 1, E 2, E 3, E 4, E 5, E 6, E 7, E 8, E 9, E 10, F 2, F 3, F 4, F 5, F 6, F 7, F 8, F 9, F 10, F 11asinduced subgraphsbypreviousresults. Nowfortheotherdirectionlet B 1 ;B 2 ;B 3 ;:::::B m be m m 2groupsofvertex150 PAGE 165 Figure4.99: n =1: I 1 151 PAGE 166 Figure4.100: n =2: I 1 152 PAGE 167 Figure4.101: n =3: I 1 153 PAGE 168 Figure4.102: n =4: I 1 Figure4.103: Representationofstraight2-pathwithall2-leaves 154 PAGE 169 consecutive4-fanswithallpossible2-leavesthatarejoinedbystraight2-pathsof length n againwithallpossible2-leavessuchthatthereareno E 1, E 2, E 3, E 4, E 5, E 6, E 7, E 8, E 9, E 10, F 2, F 3, F 4, F 5, F 6, F 7, F 8, F 9, F 10or F 11asinduced subgraphs.Letusagaincallthisstructure G .Wewillnowgiveaunitprobeinterval representationof G fordierentvaluesof n . Let B i and B j beanytwogroupsofsuch4-fansjoinedbyasuchastraight2-path oflength n .Letuscallthis B ij ,anditisisomorphicto I 2 .Itiseasytoseethatif thetheoremholdsfor B ij itshouldholdfortheentire G sincerepresentationofthe verticesofoneendofany B i isnotdependentontherepresentationofverticesofthe otherendof B i forany i aswehaveseenearlier.Sowegiveaunitprobeinterval representationof B ij fordierentvaluesof n .Furthermore,since B i and B j haveall possible2-leavesandtheyaremergeofvertexconsecutive4-fanssothelastandrst K 3 softheunderlying2-pathofboth B i and B j musthavea2-leafonitsinterior edge.Hence,asintheprevioustheorem,thelastaddedvertexontherightendof B i andtherstaddedvertexontheleftendof B j mustallbenon-probes. Case1 n =0:Thisisthecasewheretheintermittentstraight2-pathisoflength0.This impliesthatwehave B i and B j suchthatthelastedgeof B i coincideswiththerst edgeof B j .Both B i and B j aregroupsofedgeconsecutive4-fanswithallpossible2leaves.Sowegettwopossiblecaseshere.Eithertherightend2-leafof B i isadjacent totheleftend2-leafof B j orthe2-leavescoincide.Ifthe2-leavesareadjacentthen wegettheforbiddensubgraph E 3asshownintheFigure4.104.Iftheycoincidethen weeithergetan F 2oraunitproberepresentationasshowninthesamegure. Case2 n =1:Thisisthecasewheretheintermittentstraight2-pathisoflength1.This impliesthatwehave B i and B j suchthat B i and B j sharesexactlyonevertex.Both B i and B j aregroupsofvertexconsecutive4-fanswithallpossible2-leaves.Sowe 155 PAGE 170 get2sequencesofvertex-consecutive4-fanssharingacommonvertexwhoselength isequalto1+length B i +length B j .Wehave2caseshere.Thelastaddedvertex of B i B i , B j isassumedtobeconstructedfromtheleftwithoutlossofgenerality iseithertherstaddedvertexof B j ortheyareadjacent. Letusrstconsiderthecasewhentherightendvertexof B i istheleftendvertexof B j .Thisisjustanothercaseofvertexconsecutive4-fanssince B i isvertexconsecutive to B j asseeninFigure4.105andsowehaveaunitproberepresentationofthis. Nowletusconsidertheothercasewheretheverticesareadjacent.Inthiscasewe gettheforbiddensubgraph F 2intheunderlying2-pathsoran E 2asshowninFigure 4.105. Case3 n =2:Thisisthecasewheretheintermittentstraight2-pathisoflength2.This impliesthatwehave B i and B j suchthat B i and B j sharesnothing.Both B i and B j aregroupsofvertex-consecutive4-fanswithallpossible2-leaves.Thelengthof B ij isequalto2+length B i +length B j .Wewilllookatthethelast4-fanof B i and therst4-fanof B j withallpossible2-leavesonit.Since B i and B j haveallpossible 2-leaves,thenthelastandrst K 3 softheunderlying2-pathofboth B i and B j must havea2-leafonitsinterioredge.Hencethelastaddedvertexontherightendof B i B i , B j isassumedtobeconstructedfromtheleftandtherstaddedvertexon theleftendof B j mustallbenon-probes.Thestructuresthatcanbeformedhere areillustratedintheFigure4.106.Iftherightend2-leafof B i isadjacenttotheleft end2-leafof B j thenwegetforbiddensubgraphs E 10or E 8asshowninthesame Figure.Intheothercasewhentherightend2-leaffrom B i or u n isnon-adjacent totheleftend2-leafof B j or w 1 wegetastructureasshowninFigure4.106.We dotheunitproberepresentationofthisstructureasillustratedinthesameFigure. Case4 n =3:Thisisthecasewheretheintermittentstraight2-pathisoflength3.This 156 PAGE 171 impliesthatwehave B i and B j suchthat B i and B j sharesnothing.Both B i and B j aregroupsofvertex-consecutive4-fanswithallpossible2-leaves.Thelengthof B ij is equalto3+length B i +length B j .Wewilllookatthethelast4-fanof B i andthe rst4-fanof B j withallpossible2-leaves.Since B i and B j haveallpossible2-leaves sothelastandrst K 3 softheunderlying2-pathofboth B i and B j musthavea2-leaf onitsinterioredge.Hencethelastaddedvertexontherightendof B i andtherst addedvertexontheleftendof B j mustallbenon-probeslikethepreviouscases.The onlypossiblestructuresthatcanhaveaunitprobeintervalrepresentationhereare illustratedinPictures1and2ofFigure4.101.Furthermorepicture1cannoteven haveany2-leafontheinterioredgesoftheintermittentstraight2-pathotherwise forbiddensubgraphs E 1or E 2areformedwhereaspicture2canhavejustone2-leaf inthestraight2-pathasshowninthesameFigure.Otherwiseforbiddensubgraph E 7 isformedifmorethanone2-leafisattachedtothestraight2-path.Intheothercase wegetadjacenciesbetweennon-probeverticeswhichgivesustheforbiddensubgraph E 9or F 2intheunderlying2-path. Case5 n =4:Thisisthecasewheretheintermittentstraight2-pathisoflengthequalto 4.Both B i and B j aregroupsofvertex-consecutive4-fanswithallpossible2-leaves. Soweget2sequencesofsuchvertex-consecutive4-fansjoinedbyastraight2-pathof lengthequalto4withallpossible2-leaves.The2-leavesontheinterioredgesofthe straight2-pathsarepresentsothatnoforbiddensubgraphisformed.Soasstated before,ifedge e k hasa2-leafthenitsnearest2-leafmustbeontheedge e k +3 , e k )]TJ/F17 7.9701 Tf 6.587 0 Td [(3 .Let u n )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 ;u n bethelasttwoaddedverticesof B i suchthat u n istherightend2-leafof B i . Weknowthat u n mustbenon-probeand u n )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 mustbeaprobe.Furthermoreeither u n or u n )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 canbemadetohaveadistinctrightendpointasrequired.Thesamecan beconcludedabouttheleftend2-leafof B j .Let w 1 ;w 2 bethersttwoaddedvertices of B j suchthat w 1 istheleftend2-leafof B j .Weknowthat w 1 mustbenon-probe 157 PAGE 172 and w 2 mustbeaprobe.Furthermoreeither w 1 or w 2 canbemadetohaveadistinct leftendpointasrequired.Also,sincetheintermittentstraight2-pathisoflength atleast4,thereexistsatleastonevertexfromthe2-pathbetween u n )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 ;u n and w 1 ;w 2 suchthattheend2-leavesfrom B i and B j areneveradjacent.Welookathowthelast 4-fanfrom B i connectstotherst4-fanfrom B j viathestraight2-pathoflength4. ThedierentpossiblestructuresareshowninFigure4.102.Furthermoreonanypart ofthestructurewhichhasatleastsixconsecutive K 3 s,ifedge e k hasa2-leafthen itsnearest2-leafmustbeontheedge e k +3 , e k )]TJ/F17 7.9701 Tf 6.586 0 Td [(3 otherwisewewillgettheforbidden subgraphs.Theunitprobeintervalrepresentationsof1and2aredonebydoing B i rstasingure4.97followedbytherepresentationofthestraight2-pathasinFigure 4.103andnallyrepresenting B j againasingure4.97.ThegraphinPicture3is isomorphictothegraphinpicture2.Theunitprobeintervalrepresentationofthe graphinpicture4isgiveninthesamegure.Inall3representationsweuseoneof the2representationsfromFigure4.97for B i and B j . Case6 n> 4:Thisisthecasewheretheintermittentstraight2-pathisoflengthgreaterthan 4.Thisimpliesthatwehave B i and B j suchthat B i and B j sharesnovertex.Both B i and B j aregroupsofvertex-consecutive4-fanswithallpossible2-leaves.Sowe get2sequencesofsuchvertex-consecutive4-fansjoinedbyastraight2-pathoflength greaterthan4withallpossible2-leaves.Itcanbeconcludedfromthepreviouscase studythatifweconstructallthepossiblestructureswewillnevergetadjacencies betweentheend2-leavesof B i and B j andtheywouldhaveatleast2intermittent verticesbetweenthem.The2-leavesontheinterioredgesofthestraight2-pathsare presentsothatnoforbiddensubgraphisformed.Soasstatedbefore,ifedge e k hasa 2-leafthenitsnearest2-leafmustbeontheedge e k +3 , e k )]TJ/F17 7.9701 Tf 6.587 0 Td [(3 .Let u n )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 ;u n bethelast twoaddedverticesof B i suchthat u n istherightend2-leafof B i .Weknowthat u n mustbeanon-probeand u n )]TJ/F17 7.9701 Tf 6.587 0 Td [(1 mustbeaprobe.Furthermoreeither u n or u n )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 can 158 PAGE 173 Figure4.104: n =0: I 2 bemadetohaveadistinctrightendpointasrequired.Thesamecanbeconcluded abouttheleftend2-leafof B j .Let w 1 ;w 2 bethersttwoaddedverticesof B j such that w 1 istheleftend2-leafof B j .Weknowthat w 1 mustbenon-probeand w 2 must beaprobe.Furthermoreeither w 1 or w 2 canbemadetohaveadistinctleftendpoint asrequired.Also,sincetheintermittentstraight2-pathisoflengthatleast4there existsatleasttwoverticesfromthe2-pathbetween u n )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 ;u n and w 1 ;w 2 suchthat theend2-leavesfrom B i and B j areneveradjacent.Likethepreviouscase,theunit probeintervalrepresentationofsuchstructuresaredonebyrepresenting B i rstas ingure4.97thentheintermittentstraight2-pathcanberepresentedasinFigure 4.103followedby B j asingure4.97. Nowwelookatinterior2-caterpillarsisomorphicto I 3 whicharederivedfrom vertexconsecutive4-fansjoinedbystraight2-pathswithedge-consecutive4-fans. Inthefollowingtheoremwegiveunitprobeintervalrepresentationsofsuchinterior2-caterpillarswhentheydonotcontaincertainforbiddensubgraphsasinduced subgraphs. Theorem4.7.6 Interior 2 -caterpillarsgivenbystructuresisomorphictomergeof I 3 haveunitprobeintervalrepresentationifandonlyiftheydonothaveE1,E2,E3, 159 PAGE 174 Figure4.105: n =1: I 2 Figure4.106: n =2: I 2 160 PAGE 175 Figure4.107: n =3: I 2 161 PAGE 176 E4,E5,E6,E7,E8,E9,E9,E10,F2,F3,F4,F5,F6,F7,F3,F8,F9,F10,F11as inducedsubgraphs. Proof: Let G 1 and G 2 begroupsofvertex-consecutiveandedge-consecutive4-fansrespectivelyjoinedbyastraight2-pathoflength n ,withallpossible2-leaves.Letus callthisgraph G .Thisstructureisisomorphicto I 3 .If G hasaunitprobeinterval representationthenitmustnotcontain E 1, E 2, E 3, E 4, E 5, E 6, E 7, E 8, E 9, E 10, F 2, F 3, F 4, F 5, F 6, F 7, F 8, F 9, F 10, F 11asinducedsubgraphs. Nowfortheotherdirectionlet G 1 and G 2 begroupsofvertex-consecutiveand edge-consecutive4-fansrespectivelyjoinedbyastraight2-pathoflength n ,withall possible2-leaves.Letuscallthisgraph G .Hence G isisomorphicto I 3 . G doesnot contain E 1, E 2, E 3, E 4, E 5, E 6, E 7, E 8, E 9, E 10, F 2, F 3, F 4, F 5, F 6, F 7, F 8, F 9, F 10, F 11asinducedsubgraphs.Wewillgiveaunitprobeintervalrepresentation of G .Weknowthatanynumberofedge-consecutive4-fanswithallpossible2-leaves thatforma2-pathwithoutthe2-leaveshaveunitprobeintervalrepresentation iftheydonothave E 1, E 2, E 3, E 4, E 5, E 6, E 8, F 2, F 3, F 4, F 5, F 6, F 7, F 8, F 9, F 10, F 11asinducedsubgraphs.Wealsoknowthatanynumberofgroupsof vertex-consecutive4-fanswithallpossible2-leavesthatformsa2-pathwithoutthe 2-leaveshaveunitprobeintervalrepresentationiftheydonothaveF2,E1,E5,E6, E7asinducedsubgraphs.Let v n )]TJ/F17 7.9701 Tf 6.586 0 Td [(1 and v n bethelast2addedverticesof G 1and u 1 , u 2 betherst K 2 of G 2.Thus v n istherightend2-leafoftheunderlying2-pathof G 1and u 1 istheleftend2-leafoftheunderlyingpathof G 2 Case1 n =0:Thelast2addedverticesof G 1 mustbetherst K 2 of G 2. Sinceweconsider G 1 and G 2 withallpossible2-leavesinthem,thelastandrst K 3 of G 1and G 2respectivelymusthave2-leavesonitsinterioredges.Henceboth v n and u 1 mustbenon-probes.Henceif v n isadjacentto u 1 thenwegetaprobleminthe representationof G aswegettheforbiddensubgraph E 3asaninducedsubgraphinit 162 PAGE 177 asshowninFigure4.108.Otherwise v n = u 1 andwegetaunitproberepresentation asshowninFigure4.108 Case2 n =1:Ifthereexistsexactlyone K 3 between G 1 and G 2 thenwehaveto considertwosubcases.Eitherthe2-leavescoincidewhichisokasshowninthegure 4.98ortheyareadjacentwhichformsaninduced E 2asshowninFigure4.109. Case3 n =2:Ifthereexiststwo K 3 between G 1 and G 2 thenwegetthefollowing subcases.Thepossiblerepresentablestructuresandtheirrepresentationsaregiven intheFigure4.100.Thenon-possiblityoccurswhenthenon-probe2-leavesof G 1 and G 2areadjacentandwegetforbiddensubgraphs F 2 ;E 8 ;E 10asshowninFigure 4.110. Case4 n =3:Ifthereexiststhree K 3 between G 1 and G 2 thenwegetthefollowing subcases.Thepossiblerepresentablestructuresandtheirrepresentationsaregiven inFigure4.101Since G 1 isvertex-consecutiveand G 2 isedge-consecutive,weuse representation2ofFigure4.97for G 1 forpicture1andrepresentation1ofFigure 4.97for G 1 forthepicture2.FurthermoreweuserepresentationsforFigures4.89, 4.90,4.91for G 2 inbothpictures1and2dependingonthekindof G 2 thatispresent there.Similartothepreviouscasesthenon-possibilityoccurswhenthenon-probe 2-leavesof G 1 and G 2 areadjacentandwegetforbiddensubgraphs F 2or E 9. Case5 n =4:Ifthereexists4 K 3 between G 1 and G 2 thenwegetthefollowing subcases.Since G 1 and G 2 haveallpossible2-leavessothelastandrst K 3 softhe underlying2-pathofboth G 1 and G 2 musthavea2-leafinitsinterioredge.Hencethe lastaddedvertexontherightendof G 1 if G 1 isassumedtobeconstructedfromthe leftandtherstaddedvertexontheleftendof G 2 if G 2 isassumedtobeconstructed fromtheleftmustallbenon-probes.Theonlypossiblestructuresthatcanformhere areillustratedintheFigure4.102.Inothercasesweeithergetadjacenciesbetween non-probeverticeswhichgivesustheforbiddensubgraph E 2 ;E 3 ;E 4 ;E 5 ;E 10orget an F 2intheunderlying2-path.Theunitproberepresentationsofthestructuresin 163 PAGE 178 Figure4.102aregiveninthesamegure.Thesestructuresarepossibletorepresent becausetherightend2-leaffrom G 1 isnon-adjacenttotheleftend2-leafof G 2 as showninthesamegure.Furthermoreitcanbeeasilyseenfromthesestructuresthat wecannothaveany2-leafontheinterioredgesoftheintermittent2-pathinpicture 1ofthesameguresincethatwillformeitheran E 3oran E 4andwealsocanhave exactlyone2-leafononeinterioredgeoftheintermittent2-pathasshowninpicture 2otherwisewewillgettheforbiddensubgraph E 2 ;E 5 ;E 6 ;E 10.Pictures1and2are representedbydoingtherepresentationof G 1 rstasintheFigure4.97followedby thestraight2-pathasintheFigure4.103andthennallydoingtherepresentationof G 2 asintheFigures4.89,4.90,4.91.Picture4istheonlydierentcaseherewhose representationisgiveninthesamegure.Thisstructurecontainsastraight2-path oflength10and3fromtheend4-fansand4fromtheintermittentstraight2-path oflength4.Heretoowedotherepresentationof G 1 rstasinpicture1ofthe Figure4.97followedbythestraight2-pathasintheFigure4.103andthennally doingtherepresentationof G 2 asintheFigures4.89,4.90,4.91sothattheleftend 2-leavesof G 2 havedistinctendpointsinalloftheserepresentationswecanmake theend2-leavesoftheunderlying2-pathhavedistinctendpoints.Furthermoreon anypartofthestructurewhichhasatleastsixconsecutive K 3 s,ifedge e k hasa 2-leafthenitsnearest2-leafmustbeontheedge e k +3 , e k )]TJ/F17 7.9701 Tf 6.587 0 Td [(3 otherwisewewillget theforbiddensubgraphs.Soavoidingsuch2-leaveswecaneasilygettheunitprobe intervalrepresentationofthislastsubcase. Case6 n> 4:Ifthereexistsmorethanfour K 3 'sbetween G 1 and G 2 thenasbeforewegetthreesubcases.Thisisthecasewheretheintermittentstraight2-path isoflengthgreaterthan4.Itcanbeconcludedfromthepreviouscasestudythat ifweconstructallthepossiblestructuresaswedidforcase5wecaneithergetany structurewhoserepresentationcanbedonebyrepresenting G 1 rstasinFigure4.97 followedbythestraight2-pathasinFigure4.103andthennallydoingtherepresen164 PAGE 179 Figure4.108: n =0: I 3 tationof G 2 asinFigures4.89,4.90,4.91orstructuresjoinedbystraight2-pathsof lengthsatleast11atleast5fromtheintermittentstraight2-pathsand3eachfrom the4-fansontwoends.The2-leavesontheinterioredgesofthestraight2-pathsare presentsothatnoforbiddensubgraphsisformed.Soasstatedbefore,ifedge e k has a2-leafthenitsnearest2-leafmustbeontheedge e k +3 , e k )]TJ/F17 7.9701 Tf 6.586 0 Td [(3 .Theunitprobeinterval representationofsuchstructuresarepossiblebecausetheend2-leavesofthe4-fans ontwoendswhicharepartsofthestraight2-pathcanbemadetohavedistinctend pointsbythesecondpicturesofFigures4.89,4.90andeasytoseein4.91andby representationinFigure4.97andtheintermittentstraight2-pathcanberepresented asinFigure4.103. Bythesameargumentusedintheproofsofndinganunitprobeintervalrepresentationof I 1 and I 2 ,itcanbeconcludedthattheresultsalsoholdsformergeof I 3 . Note:Thisnoteisvalidforalltheabove3theorems.Letusconsidersome B ij where B i and B j arejoinedbysomestraight2-pathoflength p .Supposethatthis B ij failstohavearepresentationatthemergeduetoadjacencyofnon-probes.Itis 165 PAGE 180 Figure4.109: n =1: I 3 Figure4.110: n =2: I 3 166 PAGE 181 Figure4.111: Interior2-caterpillarswithfewer2-leaves easytoseethatthissamegraphwillbeunitprobeintervalrepresentableif,atthe merge,one2-leafistakenofromeither B i or B j sometimesfromboth B i and B j as inpicture4oftheFigure4.111,andthelasttwo4-fansofthat B i or B j orboth B i and B j areisomorphictoeitherastaircaseoravertex-consecutivestructuresothat thenon-proberestrictionfromitsend2-leafisremovedandtheirintervalscanbe madetohavedistinctendpoints.Intheothercaseswegettheforbiddensubgraphs asseeninFigure4.87. Thesestructurescanbelookedasmergeofinterior2-caterpillarswithfewer2leavesor I i , i =1 ; 2 ; 3withfewer2-leaves.Theirrepresentationsaregiveninthe Figure4.111.Itisworthmentioningherethatwecanalsogetotherkindsofinterior 2-caterpillarslikeinterior2-caterpillarswhicharejustsubgraphsof I 1 ;I 2 ;I 3 .Allthese structureswillalsohaveunitprobeintervalrepresentationsincefromalltheprevious representationsweknowthatallthe2-leavesarenon-probesandtheirremovalfrom therepresentationwillnotaecttheintervallayoutoftheunderlying2-path. 167 PAGE 182 Wenowhaveacharacterizationforinterior2-caterpillarsisomorphicto I 1 ;I 2 ;I 3 whichareunitprobeintervalgraphs.Sinceaninterior2-caterpillariseitherisomorphictooneoftheabove I i where i =1 ; 2 ; 3,theirsubgraphsor I i 'swithfewer 2-leaves,wecannoweasilycharacterizeinterior2-caterpillarswhichareunitprobeintervalgraphs.Thefollowingtheoremgivesacharacterizationofinterior2-caterpillars whichareunitprobeintervalgraphs. Theorem4.7.7 Aninterior 2 -caterpillarisaunitprobeintervalgraphifandonly ifitdoesnotcontainE1,E2,E3,E4,E5,E6,E7,E8,E9,E9,E10,Group-E11,F2, F3,F4,F5,F6,F7,F8,F9,F10,F11asgeneratedsubgraphs. Proof: Let G beaninterior2-caterpillarwhichisaunitprobeintervalgraph. Since E 1, E 2, E 3, E 4, E 5, E 6, E 7, E 8, E 9, E 10,GroupE 11, F 2, F 3, F 4, F 5, F 6, F 7, F 8, F 9, F 10, F 11donothaveunitprobeintervalrepresentation, G cannothave themasinducedsubgraphs. Fortheotherdirection,let G beanyinterior2-caterpillarwithout E 1, E 2, E 3, E 4, E 5, E 6, E 7, E 8, E 9, E 10,GroupE 11, F 2, F 3, F 4, F 5, F 6, F 7, F 8, F 9, F 10, F 11asgeneratedsubgraphs.Anyinterior2-caterpillarcanbeconsideredasgroupsof edgeorvertexconsecutive4-fansjoinedtogetherbystraight2-pathswithallpossible 2-leavesorfewer2-leaves.So G canbeassumedtobegroupsofedgeorvertex consecutive4-fansjoinedtogetherbystraight2-pathswithallpossibleorfewer2leavessuchthatnowhere E 1, E 2, E 3, E 4, E 5, E 6, E 7, E 8, E 9, E 10,GroupE 11, F 2, F 3, F 4, F 5, F 6, F 7, F 8, F 9, F 10, F 11areformedasinducedsubgraphs.Thus G iseither I 1 ;I 2 ;I 3 ; theirsubgraphsor I i 'si=1,2,3withfewer2-leaveswithout E 1, E 2, E 3, E 4, E 5, E 6, E 7, E 8, E 9, E 10,GroupE 11, F 2, F 3, F 4, F 5, F 6, F 7, F 8, F 9, F 10, F 11.Thereforebythepreviousthreetheoremsandtheabovenoteitmust haveaunitprobeintervalrepresentation. 168 PAGE 183 Thenexttheoremderivesarelationshipbetween2-treeunitprobeintervalgraphs andinterior2-caterpillars. Theorem4.7.8 A2-treeisaunitprobeintervalgraphifandonlyifitisaninterior 2-caterpillarwithoutE1,E2,E3,E4,E5,E6,E7,E8,E9,E9,E10,Group-E11,F1, F2,F3,F4,F5,F6,F7,F8,F9,F10,F11asgeneratedsubgraphs. Proof: Thisproofisanextensionofpreviousresults.Werstprovethenecessarypartrst.Let G be2-treeUPIG.ByTheorem4.3.3wehavethat G mustbean interior2-caterpillar.Since E 1, E 2, E 3, E 4, E 5, E 6, E 7, E 8, E 9, E 10,GroupE 11, F 1, F 2, F 3, F 4, F 5, F 6, F 7, F 8, F 9, F 10, F 11arenotUPIG, G cannotcontain anyofthemasinducedsubgraphs.So G mustbeaninterior2-caterpillarwithout E 1, E 2, E 3, E 4, E 5, E 6, E 7, E 8, E 9, E 10,GroupE 11, F 1, F 2, F 3, F 4, F 5, F 6, F 7, F 8, F 9, F 10, F 11. Fortheotherdirectionletusnowassumethat G isa2-treeinterior2-caterpillar without E 1, E 2, E 3, E 4, E 5, E 6, E 7, E 8, E 9, E 10,GroupE 11, F 1, F 2, F 3, F 4, F 5, F 6, F 7, F 8, F 9, F 10, F 11asinducedsubgraphs.Bytheprevioustheorem,an interior2-caterpillarisaunitprobeintervalgraphifandonlyifitdoesnotcontain E 1, E 2, E 3, E 4, E 5, E 6, E 7, E 8, E 9, E 10,GroupE 11, F 2, F 3, F 4, F 5, F 6, F 7, F 8, F 9, F 10, F 11asgeneratedsubgraphs.Since G isaninterior2-caterpillarwithout E 1, E 2, E 3, E 4, E 5, E 6, E 7, E 8, E 9, E 10,GroupE 11, F 1, F 2, F 3, F 4, F 5, F 6, F 7, F 8, F 9, F 10, F 11itmustbeaunitprobeintervalgraph. Finallythenexttheoremgivesacompletecharacterizationof2-treeswhichare unitprobeintervalgraphs.Thetotalnumberofforbiddensubgraphsis27. Theorem4.7.9 A2-treeisaunitprobeintervalgraphifandonlyifitdoesnot containE1,E2,E3,E4,E5,E6,E7,E8,E9,E9,E10,Group-E11,F1,F2,F3,F4, F5,F6,F7,F8,F9,F10,F11asgeneratedsubgraphs. 169 PAGE 184 Proof: Let G bea2-tree.letusrstassumethatitisaunitprobeinterval graph.Since E 1, E 2, E 3, E 4, E 5, E 6, E 7, E 8, E 9, E 10,GroupE 11, F 1, F 2, F 3, F 4, F 5, F 6, F 7, F 8, F 9, F 10, F 11donothaveunitprobeintervalinterval representation, G cannotcontainthemasinducedsubgraphs. Fortheotherdirectionletusnowassumethat G isa2-treewithout E 1, E 2, E 3, E 4, E 5, E 6, E 7, E 8, E 9, E 10,GroupE 11, F 1, F 2, F 3, F 4, F 5, F 6, F 7, F 8, F 9, F 10, F 11asinducedsubgraphsandthat G isnotaunitprobeintervalgraph.Then bytheprevioustheorem G isnotaninterior2-caterpillarwithout E 1, E 2, E 3, E 4, E 5, E 6, E 7, E 8, E 9, E 10,GroupE 11, F 1, F 2, F 3, F 4, F 5, F 6, F 7, F 8, F 9, F 10, F 11asgeneratedsubgraphs.Butitisgiventhat G doesnotcontainanyinduced E 1, E 2, E 3, E 4, E 5, E 6, E 7, E 8, E 9, E 10,GroupE 11, F 1, F 2, F 3, F 4, F 5, F 6, F 7, F 8, F 9, F 10, F 11.So G mustnotbeaninterior2-caterpillar.Soiteitheris anon-interior2-caterpillarornota2-caterpillaratall.Thus G eitherhasan F 1 or G has B 1 ;B 1 0 ;B 2 ;B 3asinducedsubgraphs.But G cannothavean F 1asan inducedsubgraphsoitmusthave B 1 ;B 1 0 ;B 2 ;B 3asinducedsubgraphs.Itiseasy toseefromFigure4.9that B 1 ;B 1 0 have E 1and B 2 ;B 3have F 1initrespectivelyas inducedsubgraphs.Thisimpliesthat G has F 1or E 1asinducedsubgraphswhichis acontradiction.Hence G mustbeaunitprobeintervalgraph. Conclusion:Theprecedingresultscomplimenttheexistingcharacterizationsofsubclassesof probeintervalgraphswhichincludecycle-free[41],unitcycle-free[15]andbipartite unit[10].TheseresultsalsoaddtothespiritoftheresultsofCorneilandPrzulj[34] inshowingthatthecompletecharacterizationofevenrestrictedsubclassesofprobe intervalgraphswillbeachallengingproblem. Someprogress,however,hasbeenmadeinfndingclassesofprobeintervalgraphs whichwilladmittoanalbeitcomplicatecharacterizationviaforbiddeninduced subgraphs.SeeforexampletherecentworkofBrown,Busch,andIsaak[5],andof 170 PAGE 185 Brown,Flesch,andLundgren[7]. 171 PAGE 186 REFERENCES [1]S.Benzer,"Onthetopologyofthegeneticnestructure", Proceedingsofthe NationalAcademyofSciencesoftheUnitedStatesofAmerica 45 1959, 1607-1620 [2]L.W.BeinekeandR.E.Pippert,Propertiesandcharacterizationofk-trees, Mathematika 18 ,141-151. [3]J.J.Beyerl,R.E.Jamison,IntervalGraphswithContainmentRestrictions CongressusNumberantium 191 ,117-128. [4]K.P.Bogart,D.B.West,Ashortproofthatproper=unit, DiscreteMathematics 201,,21-23. [5]D.E.Brown,A.H.Busch,andG.Isaak,Lineartimerecognitionalgorithmsand structuretheoremsforbipartitetolerancegraphsandbipartiteprobeinterval graphs, DiscreteMath.andTheoreticalComp.Sci. , 12:5 63-82. [6]D.E.Brown,A.H.Busch,andJ.R.Lundgren,Intervaltournaments, JGraph Theory 56 ,72-81. [7]D.E.Brown,B.Flesch,J.R.Lundgren,Characterizationof2-treeprobeinterval graphs,Manuscripts,toappear. [8]D.E.Brown,S.C.Flink,andJ.R.Lundgren,Intervalk-graphs, Congressus Numerantium 156 ,5-16. [9]D.E.Brown,S.C.Flink,andJ.R.Lundgren,Characterizationsofinterval bigraphsandunitintervalbigraphs. CongressusNumerantium 157 ,7993. [10]D.E.Brown,L.Langley,Forbiddensubgraphcharacterizationofbipartiteunit probeintervalgraphs,toappear. [11]D.E.Brown,J.R.Lundgren,Bipartiteprobeintervalgraphs,circulararcgraphs, andintervalpointbigraphs, AustralasJCombin 35 ,221-236. [12]D.E.Brown,J.R.Lundgren,Severalcharacterizationofunitintervalbigraphs, toappear. [13]D.E.Brown,J.R.Lundgren,RelationshipsAmongClassesofIntervalBigraphs, ,1-Matrices,andCircularArcGraphs. CongressusNumerantium , 166 , 97-123. 172 PAGE 187 [14]D.E.Brown,J.R.Lundgren,andC.Miller,Variationsonintervalgraphs CongressusNumerantium , 149 ,77-95. [15]D.E.Brown,J.R.LundgrenandL.Sheng,Acharacterizationofcycle-freeunit probeintervalgraphs, DiscreteAppliedMathematics 157 ,762-767. [16]E.Drust,S.Dasgupta,J.R.Lundgren,AClassofintervaldigraphs, Congressus Numerantium 192 ,97-113. [17]D.R.FulkersonandO.A.Gross,Incidencematricesandintervalgraphs, Pacic J.Math.15 ,835855. [18]F.Gardi,TheRobertscharacterizationofproperandunitintervalgraphs. DiscreteMathematics , 307 ,2906-2908 [19]P.C.GilmoreandA.J.Homan,Acharacterizationofcomparabilitygraphs andofintervalgraphs, Canad.J.Math. 16 ,539548. [20]M.C.Golumbic,Algorithmicgraphtheoryandperfectgraphs, annalsofdiscrete mathenatics 57 [21]M.C.GolumbicandM.Lipshteyn,Onthehierarchyofinterval,probe,and tolerancegraphs, CongressusNumerantium 153 ,97106. [22]G.Hajos,UbereineArtvonGraphen, Internat.Math.Nachr , 11 ,Problem65. [23]F.Harary,J.A.Kabell,andF.R.McMorris, Comment.Math.Univ.Carolina , 23 ,739-745. [24]P.HellandJ.Huang,IntervalBigraphsandCircularArcGraphs.Journalof GraphTheory46313-327. [25]L.Langley,J.R.Lundgren,SarahK.Merz,TheCompetitionGraphsofInterval Digraphs Congr.Numer [26]C.G.LekkerkerkerandJ.C.Boland,Representationsofnitegraphsbyasetof intervalsontherealline, Fund.Math. 51 ,45-64. [27]I.Lin,M.Sen,D.West,Classesofintervaldigraphsand0 ; 1-matrices. Congressus Numberantium 125 ,201-209. [28]J.R.Lundgren,B.Tonnsen,2-treesthatareintervalk-graphs AustralasJCombin ,. [29]T.McKee,F.R.McMorris,Topicsinintersectiongraphtheory, SIAMmongraphs onDioscreteMathematicsandapplication , SocietyforIndustrialandApplied Mathematics ,publ.,Philadelphia,. 173 PAGE 188 [30]F.R.McMorris,C.Wang,andP.Zhang,Onprobeintervalgraphs, Discrete AppliedMathematics 88 ,315324. [31]H.Muller,RecognizingIntervalDigraphsandIntervalBigraphsinPolynomial Time.DiscreteAppliedMathematics78189-205. [32]A.Proskurowski,Separatingsubgraphsink-trees, DiscreteMath. 49 275285. [33]A.ProskurowskiandJanArneTelle,Classesofgraphswithrestrictedinterval model.DiscreteMathematicsandTheoreticalCom-puterScience,3,167176. [34]N.PrzuljandD.G.Corneil,2-Treeprobeintervalgraphshavealargeobstruction set, DiscreteAppliedMathematics 150 216-231. [35]F.S.Roberts:Indierencegraphs,InHarary,F.,editor, ProofTech-niquesin GraphTheory pp.139146.AcademicPress,NewYork [36]F.S.Roberts,ProofTechniquesinGraphTheory. AcademicPress,NewYork, NY ,139-146. [37]F.S.Roberts,Discretemathematicalmodels,Prentice-Hall,UpperSaddleRiver, NJ,1976. [38]F.S.Roberts,GraphTheoryanditsapplicationstoproblemsofSociety, CBMS NSFRegionalconferenceseriesinAppliedMathematics . [39]M.Sen,S.Das,A.Roy,andD.West,Intervaldigraphs:Ananalogueofinterval graphs, J.GraphTheory 13 ,189-202. [40]M.Sen,S.DasandD.B.West,Circular-arcdigraphs:Acharacterization, J GraphTheory 13 ,581-592. [41]L.Sheng,Cyclefreeprobeintervalgraphs, CongressusNumerantium 140 , ,33-42. [42]D.B.West,Shortproofsforintervaldigraphs, DiscreteMath 178 ,287292. [43]P.Zhang,ProbeintervalgraphanditsapplicationstophysicalmappingofDNA, Manuscript,1994. [44]P.Zhang,E.A.Schon,S.G.Fischer,E.Cayanis,J.Weiss,S.Kistler,andP.E. Bourne,Analgorithmbasedongraphtheoryfortheassemblyofcontigsin physicalmappingofDNA, CABIOS 10 ,no.3,309317. [45]MethodsofmappingDNAfragments,UnitedStatesPatent. http://www.cc.columbia.edu/cu/cie/techlists/patents/5667970.htm,1997. 174 |