Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

I'd like to use GraphData to get a list of graphs with vertex connectivity at least 3. I know GraphData["Nonplanar", 6] gives all the nonplanar graphs on 6 vertices, but I can't figure out how to get GraphData to do a selection based on the "VertexConnectivity" property.

share|improve this question
    
Select[GraphData[], (GraphData[#, "VertexConnectivity"] >= 3) &] –  J. M. Apr 21 '13 at 1:58
    
What J.M. said, with the caveat that that command will initiate a loooong download. It's good to be aware of this too: mathematica.stackexchange.com/q/22261/12 –  Szabolcs Apr 21 '13 at 2:03
    
@J.M: Thanks. If I'd also like to restrict by, say, "EdgeChromaticNumber" being 3, what's the best way? (I incorrectly assumed that it would be obvious to me how to generalize to more conditions.) –  Kundor Apr 21 '13 at 2:17
    
@Szabolcs: Thanks a lot for the pointer, that's good to know. I'm actually looking at 6-vertex graphs to start with (by putting GraphData[6] in the first part of J.M.'s command) so the download's not so bad. –  Kundor Apr 21 '13 at 2:19
    
@J.M.: I believe I answered my previous question (on adding more conditions), with the form e.g. Select[GraphData[{"Nonhamiltonian", "Nonplanar", "Connected"}, 7], (GraphData[#, "EdgeChromaticNumber"] == 3 && GraphData[#, "VertexConnectivity"] >= 3) &]. Is this correct? Would it be more efficient to somehow combine the two calls to GraphData in the condition, and is this even possible? –  Kundor Apr 21 '13 at 12:10
show 2 more comments

1 Answer

up vote 1 down vote accepted

It's been suggested that I combine the helpful information given in comments into an answer. To deal with the original question (restricting the list of graphs based on "VertexConnectivity"), use Select:

Select[GraphData[], (GraphData[#, "VertexConnectivity"] >= 3) &]

However, this particular property apparently has some bugs, detailed at "Is there something wrong with VertexConnectivity". To be safe, we can use the function from Combinatorica, like so.

Block[{$ContextPath},
 Needs["Combinatorica`"];
 Needs["GraphUtilities`"]
 ]

Select[GraphData[],
 (Combinatorica`VertexConnectivity[
     GraphUtilities`ToCombinatoricaGraph[GraphData[#]]] >= 3) &]

This issue did not arise for me.

To combine multiple such conditions, use && between separate calls to GraphData, for instance:

Select[GraphData[], (GraphData[#, "EdgeChromaticNumber"] == 3 && GraphData[#, "VertexConnectivity"] >= 3) &]

All of these commands will take a very long time. It helps somewhat to preload all the information, getting all the downloads over with, which you can accomplish with GraphData[All, "Preload"]. But it still takes a long time to run. Restricting to graphs of a certain size makes it much quicker. To restrict to graphs on 7 vertices:

Select[GraphData[7], (GraphData[#, "EdgeChromaticNumber"] == 3 && GraphData[#, "VertexConnectivity"] >= 3) &]

You can also restrict this way based on the boolean properties, which GraphData can already do itself, as with "Nonplanar" in the question. Multiple ones may be combined like this:

Select[GraphData[{"Nonhamiltonian", "Nonplanar", "Connected"}, 7], (GraphData[#, "ChromaticNumber"] == 3) &]
share|improve this answer
    
Nicely done.$\phantom{}$ –  J. M. Apr 21 '13 at 14:04
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.