Graph enumeration

<h2 id="labeled-vs-unlabeled-problems">Labeled vs unlabeled problems</h2>
In some graphical enumeration problems, the vertices of the graph are considered to be labeled in such a way as to be distinguishable from each other, while in other problems any permutation of the vertices is considered to form the same graph, so the vertices are considered identical or unlabeled. In general, labeled problems tend to be easier.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a> As with combinatorial enumeration more generally, the <a href="/facts/P%25C3%25B3lya_enumeration_theorem/EBbxaxkz">Pólya enumeration theorem</a> is an important tool for reducing unlabeled problems to labeled ones: each unlabeled class is considered as a symmetry class of labeled objects. 
The number of unlabelled graphs with 
 
 
 
 n
 
 
 {\displaystyle n}
 
 vertices is still not known in a <a href="/facts/Closed-form_solution/y0xCXlSk">closed-form solution</a>,<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a> but as almost all graphs are <a href="/facts/Asymmetric_graph/J2mB5shE">asymmetric</a> this number is <a href="/facts/Asymptotic_analysis/kt87qLpu">asymptotic to</a><a class="footnote-ref" id="fnref:7" href="#fn:7">7</a>

2
              
                
                  
                    
                      (
                    
                    
                      n
                      2
                    
                    
                      )
                    
                  
                
              
            
            
              n
              !
            
          
        
        .
      
    
    {\displaystyle {\frac {2^{\tbinom {n}{2}}}{n!}}.}

<h2 id="exact-enumeration-formulas">Exact enumeration formulas</h2>
Some important results in this area include the following.

<ul><li>The number of labeled n-vertex <a href="/facts/Simple_graph/kw3eIBUe">simple undirected graphs</a> is 2n(n−1)/2.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a></li>
<li>The number of labeled n-vertex <a href="/facts/Simple_directed_graph/YBdfQ0um">simple directed graphs</a> is 2n(n−1).<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a></li>
<li>The number Cn of <a href="/facts/Connected_graph/FSNjsYhz">connected</a> labeled n-vertex undirected graphs satisfies the <a href="/facts/Recurrence_relation/JolXC71M">recurrence relation</a><a class="footnote-ref" id="fnref:10" href="#fn:10">10</a></li></ul>

C
          
            n
          
        
        =
        
          2
          
            
              
                (
              
              
                n
                2
              
              
                )
              
            
          
        
        −
        
          
            1
            n
          
        
        
          ∑
          
            k
            =
            1
          
          
            n
            −
            1
          
        
        k
        
          
            
              (
            
            
              n
              k
            
            
              )
            
          
        
        
          2
          
            
              
                (
              
              
                
                  n
                  −
                  k
                
                2
              
              
                )
              
            
          
        
        
          C
          
            k
          
        
        .
      
    
    {\displaystyle C_{n}=2^{n \choose 2}-{\frac {1}{n}}\sum _{k=1}^{n-1}k{n \choose k}2^{n-k \choose 2}C_{k}.}

from which one may easily calculate, for n = 1, 2, 3, ..., that the values for Cn are
1, 1, 4, 38, 728, 26704, 1866256, ...(sequence A001187 in the <a href="/facts/On-Line_Encyclopedia_of_Integer_Sequences/yow6cVsU">OEIS</a>)
<ul><li>The number of labeled n-vertex <a href="/facts/Tree_(graph_theory)/TCWk4Joy">free trees</a> is nn−2 (<a href="/facts/Cayley%2527s_formula/fwjWPJTf">Cayley's formula</a>).</li>
<li>The number of unlabeled n-vertex <a href="/facts/Caterpillar_tree/bPYdGwms">caterpillars</a> is<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a></li></ul>

2
          
            n
            −
            4
          
        
        +
        
          2
          
            ⌊
            (
            n
            −
            4
            )
            
              /
            
            2
            ⌋
          
        
        .
      
    
    {\displaystyle 2^{n-4}+2^{\lfloor (n-4)/2\rfloor }.}

<h2 id="graph-database">Graph database</h2>
Various research groups have provided searchable database that lists graphs with certain properties of a small sizes. For example

<ul><li><a href="https://houseofgraphs.org">The House of Graphs</a></li>
<li><a href="https://github.com/jasongrout/graph_database">Small Graph Database</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Harary, Frank; Palmer, Edgar M. (1973). Graphical Enumeration. Academic Press. ISBN 0-12-324245-2. <a href="0-12-324245-2" target="_blank">0-12-324245-2</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen. Acta Math. 68 (1937), 145-254 <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">"Cayley, Arthur (CLY838A)". A Cambridge Alumni Database. University of Cambridge. <a href="http://venn.lib.cam.ac.uk/cgi-bin/search-2018.pl?sur=&suro=w&fir=&firo=c&cit=&cito=c&c=all&z=all&tex=CLY838A&sye=&eye=&col=all&maxcount=50" target="_blank">http://venn.lib.cam.ac.uk/cgi-bin/search-2018.pl?sur=&suro=w&fir=&firo=c&cit=&cito=c&c=all&z=all&tex=CLY838A&sye=&eye=&col=all&maxcount=50</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">The theory of group-reduced distributions. American J. Math. 49 (1927), 433-455. <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Harary and Palmer, p. 1. <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Sloane, N. J. A. (ed.). "Sequence A000088 (Number of graphs on n unlabeled nodes)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation. <a href="/wiki/Neil_Sloane" target="_blank">/wiki/Neil_Sloane</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Cameron, Peter J. (2004), "Automorphisms of graphs", in Beineke, Lowell W.; Wilson, Robin J. (eds.), Topics in Algebraic Graph Theory, Encyclopedia of Mathematics and its Applications, vol. 102, Cambridge University Press, pp. 137–155, ISBN 0-521-80197-4 <a href="0-521-80197-4" target="_blank">0-521-80197-4</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Harary and Palmer, p. 3. <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Harary and Palmer, p. 5. <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Harary and Palmer, p. 7. <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Harary, Frank; Schwenk, Allen J. (1973), "The number of caterpillars" (PDF), Discrete Mathematics, 6 (4): 359–365, doi:10.1016/0012-365x(73)90067-8, hdl:2027.42/33977. <a href="/wiki/Frank_Harary" target="_blank">/wiki/Frank_Harary</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
</ol>

Graph enumeration open-in-new

Graph enumeration