Cubic Graphs
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.
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.
4 posts • Page 1 of 1
Cubic Graphs
by Keerti_Vardhan » Sat Jun 26, 2010 8:38 am
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
by Michael_Morrison » Fri Jul 02, 2010 4:19 pm
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.
- Department: Academic Initiatives
Re: Cubic Graphs
by edpeggjr » Fri Jul 02, 2010 5:45 pm
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
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
by Keerti_Vardhan » Thu Jul 15, 2010 4:02 pm
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
-
Keerti_Vardhan - Posts: 5
- Joined: Thu Apr 22, 2010 1:37 pm
- Organization: Panjab University
- Department: Mathematics
4 posts • Page 1 of 1
Return to General Mathematica Discussion
Who is online
Users browsing this forum: No registered users and 1 guest