|
| |
|
|
A008406
|
|
Triangle T(n,k) read by rows, giving number of graphs with n nodes (n >= 1) and k edges (0 <= k <= n(n-1)/2).
|
|
24
| |
|
|
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, 402, 663, 980, 1312, 1557, 1646, 1557
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,10
|
|
|
COMMENTS
| 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.
J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 519.
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.
|
|
|
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.
Triangle begins:
1,
1,1,
1,1,1,1,
1,1,2,3,2,1,1, [graphs with 4 nodes and from 0 to 6 edges]
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,
...
|
|
|
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
(*First do*) Needs["Combinatorica`"] (*then*) f[vertices_, edges_] := Plus @@ ConnectedQ /@ NumberOfGraphs[vertices, edges] /. {True -> 1, False -> 0}; Table[ f[v, e], {v, 1, 8}, {e, 0, v*(v - 1)/2}] [From Robert G. Wilson v (rgwv(AT)rgwv.com), Dec 09 2009]
|
|
|
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: A122402 A179008 A174985 * A039735 A171457 A129385
Adjacent sequences: A008403 A008404 A008405 * A008407 A008408 A008409
|
|
|
KEYWORD
| nonn,tabf,nice
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
EXTENSIONS
| Additional comments from Arne Ring (arne.ring(AT)epost.de), Oct 03 2002
|
| |
|
|
