I Spy With My Little Eye.....A Caterpillar!

In my last post I talked a little bit about what graph theory is and some of the different terms and names that pop up when you read about it. From the assortment of names and pictures you might have gotten the impression that graph theory can get pretty diverse. Not only is it varied in the kinds of graphs that you see, but also in the different things that people are interested in studying. A case in point comes when you talk about caterpillar graphs. As with the last post, a few definitions are in order to understand what is to be said.

The degree of a vertex in a graph (here I am using graph to refer to the simple graphs introduced in post 1) is simply the number of edges incident to it. This does not come up in simple graphs but to be complete I will say that in the case that a vertex is inside of its own loop you count the loop edge's contribution to the vertex twice (i.e. the degree of a vertex that only has a loop incident to it has a degree of 2).

Now for a couple of graphs:

The first one below is an example of a path graph. It's appearance matches the description quite well. All it's really made of is a sequence of vertices and edges which when followed from left to right account for the entire graph. (Pretty informal definition for the time being but it will do) It has two endpoints of degree one and the remaining internal vertices all have degree two. Apart from the tree that just consists of a single isolated node it is the simplest type of tree that you can have.

And as for trees....

A cycle in graph theory is what you would visualize a cycle as being in regular life. You have a series of vertices connected to each other in a circular fashion as seen below. The smallest cycle is the loop, followed by a cycle of length two made up of two vertices connected via parallel edges. The smallest simple cycle is the triangle which is made up of three vertices connected by three edges. Similarly there are four cycles, five cycles,...etc.

How does this relate to trees? Well, a tree is a connected (i.e. if there are at least two vertices you must be able to reach one from the other by following a sequence of vertices and edges in the graph) simple graph that has no cycles (i.e. it is acyclic). The simplest tree that has a vertex is the one consisting of a single isolated vertex. After that we of course have the path graphs which can be built on to make more complex looking graphs, an example of which is finally (drum roll...) a caterpillar graph! :-D  Below from left to right are pictures of trees with a caterpillar graph at the very bottom. Well okay technically they're all caterpillars (if you orient them a certain way you can get them to appear more like the bottom graph), but visually at least it's easy to recognize the bottom as a caterpillar.

Many interesting properties can be derived about trees in general. The following are a few basic ones:
1. A tree with at least two nodes must have at least two leaves (vertices in a tree of degree one).
2. A tree consisting of n nodes has exactly n-1 edges.
3. There exists a unique path between any two vertices/nodes of a tree.

(And if you're familiar with computer science you will know that binary trees come up a lot when discussing things like binary search trees, heaps, balanced trees, and the implementation of data structures like sets and maps. )

In addition to the general properties listed above, caterpillar trees have their own interesting  properties specific to their structure. One way to think of a caterpillar tree is as the result of a sequence of operations where the operation consists of two parts:
1. Add an isolated vertex to the graph.
2. Connect the isolated vertex to an internal node of the original path.
*And of course if none of these operations are performed on the path we can still say that we have a caterpillar!

What are these properties of caterpillar graphs you say? Well here are a couple of them below. Why are they true? That will be the subject of upcoming posts! To derive the first one I will first have to tell you what Hamiltonian graphs and paths are, and I will also have to explain what the square a graph is as well as its corresponding line graph. (Turns out that you can also just talk about the kth power of a graph in general. You can even talk about the square root of a graph!). Until then, see if you can come up with your own proofs. Draw out your own examples and see if you can notice any patterns. And as always, keep on graphing! :-)

Caterpillar properties:
1. The square of a caterpillar graph with at least two vertices contains a Hamiltonian path.
2. Similarly, they are trees whose line graphs contain a Hamiltonian path.

Graphs, Graphs and More Graphs!

For this first post I thought that I'd talk about my favorite of all of the mathematical subjects: graph theory. Appropriate for this blog not just because I like it but also because it has considerable overlap with computer science. Many algorithms studied in the typical undergraduate CS curriculum involve graphs (e.g. tree building algorithms, shortest path problems,...., and if you get more advanced, problems in network analysis). Graph theory also has a lot of overlap with other fields as well simply because it makes visualizing problems a lot easier. It's not unusual for scientists in certain areas of biology to be looking at similar problems (in graph theory terms) as a computer scientist. Graph theoretic problems have also been found to pop up in chemistry, archaeology, and sociology. This is a trend that I expect will continue to grow as data becomes bigger and more complex in the information age.

So now that I've whetted your appetite for graphs (maybe..hopefully) I thought I'd get into a little introduction about what exactly graph theory is and acquaint you with a few of the many many graphs that are floating around out there.

A graph is  a structure that consist of a set of vertices (also called nodes) connected to each other via edges. The vertices together form the so-called vertex set of the graph and the edges the edge set. The best way to think of a graph is as a collection of dots connected to each other by lines. The dots are the vertices and the lines the edges. Below is a picture of a very basic graph that I have drawn. As you can see, not all of the vertices have to be connected to each other, and it is possible that a vertex is connected to itself. When this happens the vertex is contained in its own loop. It is also possible that there is more than one edge between any two vertices. Two edges that have the same endpoints are called parallel or multiple edges. One last thing. I didn't indicate it in this picture, but it is also possible for a vertex to be all by its lonesome withouth any edges connecting it to other vertices in the graph. Such a vertex is said to be isolated.

Many variations of the concept of a graph can be studied. Direction can be assigned to the edges in the graph creating a digraph, and weights can also be assigned to vertices or edges to give some indication of additional characteristics of the graph. For example, one can easily model the network of streets in a city or town with a graph. The vertices represent the intersections of streets, weights can indicate their respective lengths, and arrows the directions of the streets. The graphs that I will show you now are in a sense the simplest of the type of graphs. They are called, not surprisingly, simple graphs.

Simple graphs are ones that have no loops nor multiple edges. The ones that I will focus on in this post have the added restriction that the edges have no assigned direction, nor weight, and all of them have a finite number of vertices. It is possible for you to have simple graphs that are weighted and have direction, but like I said I'm going to be keeping things "simple" for this post. :-)

Now on to the graphs! Whenever anyone starts studying graph theory they're bound to come across what would seem an endless number of definitions. Even as you become more used to the definitions you'll still end up seeing lots of different graphs with cute names. Why so many? My guess is because graph theory is combinatorial in nature. As you increase the number of vertices in a graph the possibilities increase rapidly to the point where you might feel lost in a sea of dots and lines. To make sense out of this and to remember ones that have important or peculiar properties it is helpful to come up with descriptive names as sort of a memory aid. So if you look at the first graph in the top left below, we have what looks like a bow or a couple of triangles merged together. This is commonly known as a butterfly graph. The name makes sense right? To the right we have a bull graph (if I was drawing this for a group of students I would probably use a red marker to make the bottom most vertex red and call it rudolph ;D ), below which is an example of a caterpillar graph. I have also seen the fourth graph in the upper right corner being quoted as a claw graph (it's a simple case of a complete bipartite graph).

If you start to think about it I'm sure that you can imagine your own graphs with descriptive names attached. The list of different graphs out there goes on and on:
theta graphs, cactus graphs, diamonds, snarks (I actually didn't even know there were snarks until a couple of hours ago), cages, wheels, stars,..etc. Besides these graphs there are also many named after people. Examples include the Petersen graph, Moore graphs, Hamiltonian graphs, and Eulerian graphs.

So I think that up to this point we can agree that graphs can have some interesting names, but what makes them special? Well....a lot of things actually. Depending on the area of graph theory, people may be interested in studying symmetries, degree sequences, existence or lack of cycles, paths, roots, spanning trees, and so on. In my next series of posts I will delve into more detail on the graphs just mentioned and the kinds of things that people like to study about them. Till then, keep on graphing!
:-)