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!
:-)