Graph theory in Sage

Even though there are already fine guides in the web to start using the Sage software for graph theory, such as this, a video, and this, I wanted to write a simple one for my students. We have been studying the cubic graphs with eight vertices. And we already know the answer, but we want to ask the computer which of those graphs are vertex transitive.

cubic graphs on 8 vertices

We obtain the first graph putting together two copies of K_4:

sage: k4=graphs.CompleteGraph(4)
sage: g1=k4+k4
sage: g1.is_vertex_transitive()
True

We can get a picture of the graph g1:

sage: g1.show()

gives:

k4+k4

Now, the cube graph is easy, it is already defined in the Sage library of graphs:

sage: g2=graphs.CubeGraph(3)
sage: g2.is_vertex_transitive()
True

In this case it is nicer to draw the graph in 3d!

sage: g2.show3d()

which should result in something like:

cube in jmol

Now for the third graph, we use “LCF notation”. Basically, we note that from vertex 0, we have a cord to the second vertex, then from 1 again to the second vertex. Then the cord from the next vertex (number 2) goes two steps backward, and also the next. This recipe repeats for the next four vertices, hence:

sage: g3=graphs.LCFGraph(8, [2,2,-2,-2], 2)
sage: g3.is_vertex_transitive()
False

For the fourth, we use again the LCF notation:

sage: g4=graphs.LCFGraph(8, [4,-2,4,2], 2)  
sage: g4.is_vertex_transitive()           
False

For the fifth, we use another strategy. We will add edges to a cycle of length 8:

sage: g5=graphs.CycleGraph(8)
sage: g5.add_edges(((0,4),(1,7),(2,5),(3,6)))
sage: g5.is_vertex_transitive()
False

The last graph is an example of a “circulant graph”: 8 vertices with “steps” of 1 and 4 vertices:

sage: g6=graphs.CirculantGraph(8,[1,4])
sage: g6.is_vertex_transitive()
True

Advertisements
This entry was posted in Math and tagged , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s