Non-isomorphic graphs of given order. - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-26T03:51:59Z http://mathoverflow.net/feeds/question/29593 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/29593/non-isomorphic-graphs-of-given-order Non-isomorphic graphs of given order. To be cont'd 2010-06-26T09:14:27Z 2010-09-26T15:37:01Z <p>It is well discussed in many graph theory texts that it is somewhat hard to distinguish non-isomorphic graphs with large order. But as to the construction of all the non-isomorphic graphs of any given order not as much is said. So, it follows logically to look for an algorithm or method that finds all these graphs. </p> <p>A Google search shows that a paper by <a href="http://www.moreheadstate.edu/files/colleges/science/mcs/mejam/dewet.pdf" rel="nofollow">P. O. de Wet</a> gives a simple construction that yields approximately $\sqrt{T_n}$ non-isomorphic graphs of order n.</p> <p>( ${T_n}$ being the number of labeled graphs of order n.)</p> <p>So, I have the followings to ponder over: </p> <p>(1) Are there such algorithms or has there been an improvement on the aforementioned algorithm?</p> <p>(2) Where can I find a collection of non-isomorphic graphs of a given order? </p> <p>If you allow me, I would also like to extend my question to connected graphs. </p> <p>Many thanks. </p> <p>(I am a beginner in Graph theory, so please give answers in not-very-specialized terms.)</p> http://mathoverflow.net/questions/29593/non-isomorphic-graphs-of-given-order/29596#29596 Answer by Falk Hüffner for Non-isomorphic graphs of given order. Falk Hüffner 2010-06-26T10:23:18Z 2010-06-26T10:23:18Z <p>The <a href="http://cs.anu.edu.au/~bdm/nauty/" rel="nofollow">nauty software</a> contains the "geng" program, which enumerates all nonisomorphic graphs of a given order, or only connected ones, or selected on a wide range of other criteria. The method is tuned for practical speed rather than simplicity or theoretical bounds. The author Brendan McKay also has a page where you can download <a href="http://cs.anu.edu.au/~bdm/data/graphs.html" rel="nofollow">nonisomorphic (connected) graphs up to 10 vertices</a>.</p> http://mathoverflow.net/questions/29593/non-isomorphic-graphs-of-given-order/29694#29694 Answer by Douglas S. Stones for Non-isomorphic graphs of given order. Douglas S. Stones 2010-06-27T09:49:22Z 2010-06-27T09:49:22Z <p>Sage also has graph theory tools <a href="http://sporadic.stanford.edu/bump/sage/reference/sage/graphs/graph.html" rel="nofollow">here</a>. For example:</p> <pre><code>for g in graphs(4): print g.spectrum() </code></pre> http://mathoverflow.net/questions/29593/non-isomorphic-graphs-of-given-order/29875#29875 Answer by Unknown for Non-isomorphic graphs of given order. Unknown 2010-06-29T07:54:21Z 2010-06-29T07:54:21Z <p>Acknowledging Timothy’s comment, let me answer the question.</p> <p>For a diagrammatic list of the non-isomorphic graphs (all in pdfs):</p> <ol> <li><p><a href="http://keithbriggs.info/images/g4.pdf" rel="nofollow">http://keithbriggs.info/images/g4.pdf</a></p></li> <li><p><a href="http://keithbriggs.info/images/g5.pdf" rel="nofollow">http://keithbriggs.info/images/g5.pdf</a></p></li> <li><p><a href="http://keithbriggs.info/images/g6.pdf" rel="nofollow">http://keithbriggs.info/images/g6.pdf</a></p></li> <li><p><a href="http://keithbriggs.info/images/g7.pdf" rel="nofollow">http://keithbriggs.info/images/g7.pdf</a></p></li> <li><p><a href="http://keithbriggs.info/images/n8m9.pdf" rel="nofollow">http://keithbriggs.info/images/n8m9.pdf</a></p></li> <li><p><a href="http://keithbriggs.info/images/g10-8.pdf" rel="nofollow">http://keithbriggs.info/images/g10-8.pdf</a></p></li> <li><p><a href="http://www.research.att.com/~njas/sequences/a000088a.gif" rel="nofollow">Small graphs</a></p></li> </ol> <p>I <a href="http://keithbriggs.info/cgt.html" rel="nofollow">quote</a> “The topologies were computed using the <a href="http://cs.anu.edu.au/%257Ebdm/nauty" rel="nofollow">nauty</a> program by Brendan McKay and the layouts created with <a href="http://www.research.att.com/sw/tools/graphviz/" rel="nofollow">graphviz</a>. I wrote python programs to interface these and produce the pdfs.”</p> http://mathoverflow.net/questions/29593/non-isomorphic-graphs-of-given-order/32581#32581 Answer by Mitch Harris for Non-isomorphic graphs of given order. Mitch Harris 2010-07-20T02:57:40Z 2010-07-20T02:57:40Z <p>See:</p> <p>Combinatorial algorithms: an update, Herbert S. Wilf, Albert Nijenhuis SIAM, 1989. Chapter 8: Generating Random Graphs.</p> <p>The chapter gives an algorithm for producing an undirected graph uniformly over all graphs of size $n$. It is based on Polya counting. Computing the enumerating polynomial depends on some group theory that is time consuming (I don't know the complexity class, but I'll just conjecture it is most likely exponential space on $n$). But it is a guarantee of uniform distribution. Unfortunately I don't know of a way (I haven't heard of a way) to derandomize this to create an unranking algorithm (to give a mapping from the naturals to the set of unlabeled graphs). </p> <p>The algorithm presented in your link (by de Wet) is cute (I mean that in the sense that it is cleverly simple, does not lie, but doesn't really give the meat of it, what it means to have a list of non-isomorphic graphs). The graphs created there have a very particular structure (two paths with an arbitrary subset of edges between the paths, plus some small widgets on one end of each path to break symmetry. All subsets is a good trick but having two paths is pretty uncommon and $\sqrt{T_n}\over T_n$ goes to 0 as $n$ grows.</p> <p>As to practicality, in addition to the suggestions of nauty and Sage, there's also Mathematica (commercial) which has a list (that you can manipulate) of graphs up to size 11. </p> http://mathoverflow.net/questions/29593/non-isomorphic-graphs-of-given-order/40032#40032 Answer by Jiaojun Zhang for Non-isomorphic graphs of given order. Jiaojun Zhang 2010-09-26T15:37:01Z 2010-09-26T15:37:01Z <p>Thank you for your answers. I also want to compute the number of all the non-isomorphism graphs with given vertices, non-isomorphism connected graph and the all the non-isomorphism maximum planar graph. I want to compute the number and draw the graphs with the matlab language. Could I have the program code? I think the pdf documents are very good. However, the web sites cannot be opened.</p>