O'Reilly logo

Fibonacci and Catalan Numbers: An Introduction by Ralph P. Grimaldi

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Chapter 24

Some Examples from Graph Theory

As the title suggests, this chapter will introduce some examples where the Catalan numbers arise in graph theory.

In Chapter 12, we were introduced to the structure called an undirected graph. In our first example, we shall investigate a special collection of undirected graphs, which have no loops and are defined using closed intervals of unit length.

Example 24.1 (Unit-Interval Graphs): For n ≥ 1, we start with n closed intervals of unit length and draw the corresponding unit-interval graphs on n vertices, as shown in Fig. 24.1 (for the cases where n = 1 and n = 2). In Fig 24.1 (a) we find one unit interval. This corresponds to the single (isolated) vertex u1. Here we can represent both the closed interval and the unit-interval graph by the binary string 01. When we consider two closed unit intervals, we can draw them so that they do not overlap, as in Fig. 24.1 (b), or overlapping, as in part (c) of the figure. When two closed unit intervals overlap, we draw an edge in the graph joining the vertices that correspond to the two closed unit intervals. Consequently, the unit-interval graph in Fig. 24.1 (b) consists of the two isolated vertices img and img, which correspond respectively with the first and second closed unit intervals that do not ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required