## Cubic Graphs

General discussion about Mathematica features and functionality...
Forum Rules
By using the Wolfram Faculty Program Forum, you agree not to post any abusive, obscene, vulgar, slanderous, hateful, threatening, or sexually oriented material. Wolfram Faculty Program Forum administrators have the right to remove, edit, move or close any topic at any time should we see fit.

Personal Information: Posts in this forum may be viewed by non-members; however, the forum prohibits non-members from viewing your profile. Although your email address is hidden from both non-members and members, your account is initially configured to allow members to contact you via email through the forum. If you wish to hide your profile, or prohibit others from contacting you directly, you may change these settings by updating your profile through the User Control Panel.

Attachments: Attachments are not currently enabled on this forum. To share a file with others on this site, simply upload your file to the online storage service of your choice and include a link to the file within your post. If your school does not offer an online file storage and sharing service, the following sites provide free basic online file storage and sharing: Mozy, FilesAnywhere, Adrive, and KeepandShare.

### Cubic Graphs

By using 6 vertices (say a, b, c, d, e, f) how many different cubic graphs can be constructed? A graph (or a multi-graph) is called cubic if each of its vertex is shared by exactly three edges. Two graphs are called different if one cannot be obtained from the other by relabeling of the vertices i.e. they are non-isomorphic. The answer to this problem is 6, but the question is can Mathematica compute this thing? and draw all six possibilities?

Keerti_Vardhan

Posts: 5
Joined: Thu Apr 22, 2010 1:37 pm
Organization: Panjab University
Department: Mathematics

### Re: Cubic Graphs

You can use Mathematica's built-in function GraphData to look for graphs that meet certain characteristics. For example, GraphData["Cubic", 6] will return all cubic graphs on 6 vertices. However, it only returns two results (the same as pictured in the second row on this MathWorld entry: http://mathworld.wolfram.com/CubicGraph.html).

Michael_Morrison

Posts: 42
Joined: Fri Sep 11, 2009 9:50 pm
Organization: Wolfram Research, Inc.

### Re: Cubic Graphs

The poster is not really asking about classic cubic graphs. These are
are given in GraphData up to a reasonable size, and are enumerated at
http://www.research.att.com/~njas/sequences/A002851

Instead, the question is about connected nondirected trivalent multigraphs
without self-loops.
http://www.research.att.com/~njas/sequences/A005966

Cubic multigraphs are less popular. Apparently, no-one in the world
has yet programmed their enumeration.

Without the connected requirement, there are 9 such graphs on 6 nodes.
If self-loops are allowed, the counts go higher.

Directed graphs and directed multigraphs also lack many
enumerations. Connectedness and self-loops change the enumeration.

Nine edges are needed. One programming method would be to start with

Select[GraphData["Connected", 6], Max[GraphData[#, "Degrees"]] < 4 &]

Graphs containing edges having degree 1-3 or 1-2 can be eliminated. Similarly,
graphs with degree 2 vertices surrounded by degree 3 vertices can be
eliminated.

For each remaining graph, add edge multiples to reach nine in all possible ways,
and select the cubic cases.
--Ed Pegg Jr
edpeggjr

Posts: 1
Joined: Fri Jul 02, 2010 5:00 pm
Organization: WRI
Department: Scientific Information Group

### Re: Cubic Graphs

With reference to your suggestion "Select[GraphData["Connected", 6], Max[GraphData[#, "Degrees"]] < 4 &]" I wish to tell you that my computer hangs when I try to run this command. Is there anything wrong with my computer or software? I am using Mathematica7. Please help.
Keerti Vardhan

Keerti_Vardhan

Posts: 5
Joined: Thu Apr 22, 2010 1:37 pm
Organization: Panjab University
Department: Mathematics