login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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). 70

%I

%S 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,

%T 24,21,15,9,5,2,1,1,1,1,2,5,10,21,41,65,97,131,148,148,131,97,65,41,

%U 21,10,5,2,1,1,1,1,2,5,11,24,56,115,221,402,663,980,1312,1557,1646,1557

%N 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).

%C The index of T(n,k) in the sequence is ((n-2)^3-n+6*k+8)/6.

%C 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)).

%D L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 264.

%D J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 519.

%D F. Harary, Graph Theory. Addison-Wesley, Reading, MA, 1969, p. 214.

%D F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 240.

%D J. Riordan, An Introduction to Combinatorial Analysis, Wiley, 1958, p. 146.

%D R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1976.

%H R. W. Robinson, <a href="/A008406/b008406.txt">Rows 1 to 20 of triangle, flattened</a>

%H Leonid Bedratyuk, <a href="http://arxiv.org/abs/1512.06355">A new formula for the generating function of the numbers of simple graphs</a>, arXiv:1512.06355 [math.CO], 2015.

%H FindStat - Combinatorial Statistic Finder, <a href="http://www.findstat.org/StatisticsDatabase/St000081">The number of edges of a graph.</a>

%H R. J. Mathar, <a href="http://arxiv.org/abs/1709.09000">Statistics on Small Graphs</a>, arXiv:1709.09000 (2017) Table 65.

%H Sriram V. Pemmaraju, <a href="http://www.cs.uiowa.edu/~sriram/Combinatorica/index.html">Combinatorica 2.0</a>

%H Marko R. Riedel, <a href="http://math.stackexchange.com/questions/2187019/">Number of distinct connected digraphs</a>

%H Gordon Royle, <a href="http://staffhome.ecm.uwa.edu.au/~00013890/remote/graphs/">Small graphs</a>

%H S. S. Skiena, <a href="http://www.cs.sunysb.edu/~algorith/files/generating-graphs.shtml">Generating graphs</a>

%H Peter Steinbach, <a href="/A008406/a008406.txt">Field Guide to Simple Graphs, Volume 2</a>, Overview of the 12 Parts (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)

%H Peter Steinbach, <a href="/A008406/a008406_1.pdf">Field Guide to Simple Graphs, Volume 2</a>, Part 1

%H Peter Steinbach, <a href="/A008406/a008406_2.pdf">Field Guide to Simple Graphs, Volume 2</a>, Part 2

%H Peter Steinbach, <a href="/A008406/a008406_3.pdf">Field Guide to Simple Graphs, Volume 2</a>, Part 3

%H Peter Steinbach, <a href="/A008406/a008406_4.pdf">Field Guide to Simple Graphs, Volume 2</a>, Part 4

%H Peter Steinbach, <a href="/A008406/a008406_5.pdf">Field Guide to Simple Graphs, Volume 2</a>, Part 5

%H Peter Steinbach, <a href="/A008406/a008406_6.pdf">Field Guide to Simple Graphs, Volume 2</a>, Part 6

%H Peter Steinbach, <a href="/A008406/a008406_7.pdf">Field Guide to Simple Graphs, Volume 2</a>, Part 7

%H Peter Steinbach, <a href="/A008406/a008406_8.pdf">Field Guide to Simple Graphs, Volume 2</a>, Part 8

%H Peter Steinbach, <a href="/A008406/a008406_9.pdf">Field Guide to Simple Graphs, Volume 2</a>, Part 9

%H Peter Steinbach, <a href="/A008406/a008406_10.pdf">Field Guide to Simple Graphs, Volume 2</a>, Part 10

%H Peter Steinbach, <a href="/A008406/a008406_11.pdf">Field Guide to Simple Graphs, Volume 2</a>, Part 11

%H Peter Steinbach, <a href="/A008406/a008406_12.pdf">Field Guide to Simple Graphs, Volume 2</a>, Part 12

%H James Turner, William H. Kautz, <a href="http://dx.doi.org/10.1137/1012125">A survey of progress in graph theory in the Soviet Union</a> SIAM Rev. 12 1970 suppl. iv+68 pp. MR0268074 (42 #2973). See p. 19.

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/ConnectedGraph.html">Connected Graph</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/SimpleGraph.html">Simple Graph</a>

%H A. E. Yurtsun, <a href="http://dx.doi.org/10.1007/BF01085184">Principles of enumeration of the number of graphs</a>, Ukrainian Mathematical Journal, January-February, 1967, Volume 19, Issue 1, pp 123-125, DOI 10.1007/BF01085184.

%F O.g.f. for n-th row: 1/n! Sum_g det(1-g z^2)/det(1-g z) where g runs through the natural matrix representation of the pair group A^2_n (for A^2_n see F. Harary and E. M. Palmer, Graphical Enumeration, page 83). - _Leonid Bedratyuk_, Sep 23 2014

%e 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.

%e Triangle begins:

%e 1,

%e 1,1,

%e 1,1,1,1,

%e 1,1,2,3,2,1,1, [graphs with 4 nodes and from 0 to 6 edges]

%e 1,1,2,4,6,6,6,4,2,1,1,

%e 1,1,2,5,9,15,21,24,24,21,15,9,5,2,1,1,

%e 1,1,2,5,10,21,41,65,97,131,148,148,131,97,65,41,21,10,5,2,1,1,

%e ...

%p seq(seq(GraphTheory:-NonIsomorphicGraphs(v,e),e=0..v*(v-1)/2),v=1..9); # _Robert Israel_, Dec 22 2015

%t << Combinatorica`; Table[CoefficientList[GraphPolynomial[n, x], x], {n, 8}] // Flatten (* _Eric W. Weisstein_, Mar 20 2013 *)

%t << Combinatorica`; Table[NumberOfGraphs[v, e], {v, 8}, {e, 0, Binomial[v, 2]}] // Flatten (* _Eric W. Weisstein_, May 17 2017 *)

%o (Sage)

%o def T(n,k):

%o return len(list(graphs(n, size=k)))

%o # _Ralf Stephan_, May 30 2014

%Y Row sums give A000088.

%Y Cf. A046742, A046751, A000717, A001432, A001431, A001430, A001433, A001434, A048179, A048180 etc.

%Y Cf. also A039735, A002905, A054924 (connected), A084546 (labeled graphs).

%Y Index calculation for the current sequence: A000124; number of connected graphs for given number of vertices: A001349; number of graphs for given number of edges: A000664.

%Y Cf. also A000055.

%K nonn,tabf,nice,look

%O 1,10

%A _N. J. A. Sloane_, Mar 15 1996

%E Additional comments from Arne Ring (arne.ring(AT)epost.de), Oct 03 2002

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 22 18:55 EDT 2018. Contains 316500 sequences. (Running on oeis4.)