Unit-Interval Graphs. For n ‰¥ 1, we start with n closed intervals of unit length and draw the corresponding unit-interval graph on n vertices, as shown in Fig. 11.13. In part (a) of the figure we have one unit interval. This corresponds to the single vertex u; both the interval and the unit-interval graph can be represented by the binary sequence 01. In parts (b), (c) of the figure we have the two unit-interval graphs determined by two unit intervals. When two unit intervals overlap [as in part (c)] an edge is drawn in the unit-interval graph joining the vertices corresponding to these unit intervals. Hence the unit-interval graph in part (b) consists of the two isolated vertices v1, v2 that correspond with the nonoverlapping unit intervals. In part (c) the unit intervals overlap so the corresponding unit-interval graph consists of a single edge joining the vertices v1,v2 (that correspond to the given unit intervals). A closer look at the unit intervals in part (c) reveals how we can represent the positioning of these intervals and the corresponding unit-interval graph by the binary sequence 0011. In parts (d)-(f) of the figure we have three of the unit-interval graphs for three unit intervals - together with their corresponding binary sequences.
(a) How many other unit-interval graphs are there for three unit intervals? What are the corresponding binary sequences for these graphs?
(b) How many unit-interval graphs are there for four unit intervals?
(c) For n ‰¥ 1, how many unit-interval graphs are there for n unit intervals?

Transcribed Image Text:

01 0101 (c) 0011 0 0 W2 W3 W3 (d) 000111 (e 01101 (f) 010011 Figure 11.13