|
Search: id:A008406
|
|
|
| A008406 |
|
Triangle T(n,k) giving number of graphs with n >= 1 nodes and k edges, (0 <= k <= n(n-1)/2). |
|
+0
17
|
|
| 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 2, 1, 1, 1, 1, 2, 4, 6, 6, 6, 4, 2, 1, 1, 1, 1, 2, 5, 9, 15, 21, 24, 24, 21, 15, 9, 5, 2, 1, 1, 1, 1, 2, 5, 10, 21, 41, 65, 97, 131, 148, 148, 131, 97, 65, 41, 21, 10, 5, 2, 1, 1, 1, 1, 2, 5, 11, 24, 56, 115, 221
(list; graph; listen)
|
|
|
OFFSET
|
1,10
|
|
|
COMMENT
|
The index of T(n,k) in the sequence is ((n-2)^3-n +6*k+8)/6).
T(n,k)=1 for k=n*(n-1)/2-1 and k=n*(n-1)/2 (therefore the pair {1,1} separates sublists for a given number of vertices (n>2).
|
|
REFERENCES
|
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 264.
F. Harary, Graph Theory. Addison-Wesley, Reading, MA, 1969, p. 214.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 240.
J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 146.
R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.
J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 519.
|
|
LINKS
|
R. W. Robinson, Rows 1 to 20 of triangle, flattened
Sriram V. Pemmaraju, Combinatorica 2.0
Gordon Royle, Small graphs
S. S. Skiena, Generating graphs
Eric Weisstein's World of Mathematics, Simple Graph
Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.
|
|
EXAMPLE
|
There are 2 connected graphs with 4 vertices and 3 edges up to isomorphy (first graph: ((1,2),(2,3),(3,4)); second graph: (1,2),(1,3),(1,4)) ). Index within the sequence is ((4-2)^3-4 +6*3+8)/6))=6.
1; 1,1; 1,1,1,1; 1,1,2,3,2,1,1 [ the last batch giving the numbers of graphs with 4 nodes and from 0 to 6 edges ].
|
|
MATHEMATICA
|
NumberOfConnectedGraphs[vertices_, edges_] := Apply[Plus, Map[ConnectedQ, ListGraphs[vertices, edges]]/.{True->1}/.{False ->0}] The sequence up to MAX vertices: Table[Table[Apply[Plus, Map[ConnectedQ, ListGraphs[Vert, i]]] /.{True->1}/.{False->0}, {i, Vert-1, Vert*(Vert-1)/2}], {Vert, 1, MAX}]] Requires Combinatorica 2.0
|
|
CROSSREFS
|
Row sums give A000088.
Cf. A046742, A046751, A000664, A000717, A001432, A001431, A001430, A001433, A001434, A048179, A048180 etc.
Cf. also A039735.
Index calculation for the current sequence: A000124, number of connected graphs for given number of vertices: A001349, number of connected graphs for given number of edges: A076265, number of disconnected graphs for given number of vertices and edges: A076264.
Sequence in context: A110540 A083475 A122402 this_sequence A039735 A129385 A096626
Adjacent sequences: A008403 A008404 A008405 this_sequence A008407 A008408 A008409
|
|
KEYWORD
|
nonn,tabf,nice
|
|
AUTHOR
|
njas
|
|
EXTENSIONS
|
Additional comments from Arne Ring (arne.ring(AT)epost.de), Oct 03 2002
|
|
|
Search completed in 0.002 seconds
|
