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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A076263 Triangle read by rows: T(n,k) = number of nonisomorphic connected graphs with n vertices and k edges (n >= 1, n-1 <= k <= n(n-1)/2). 3

%I

%S 1,1,1,1,2,2,1,1,3,5,5,4,2,1,1,6,13,19,22,20,14,9,5,2,1,1,11,33,67,

%T 107,132,138,126,95,64,40,21,10,5,2,1,1,23,89,236,486,814,1169,1454,

%U 1579,1515,1290,970,658,400,220,114,56,24,11,5,2,1,1,47,240,797,2075,4495

%N Triangle read by rows: T(n,k) = number of nonisomorphic connected graphs with n vertices and k edges (n >= 1, n-1 <= k <= n(n-1)/2).

%C The index of the 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 {1,1} separates sublists for given numbers of vertices (n > 2)).

%H T. D. Noe, <a href="/A076263/b076263.txt">Rows 1 to 16 of triangle, flattened</a> (from Gordon Royle's website)

%H Keith M. Briggs, <a href="http://keithbriggs.info/cgt.html">Combinatorial Graph Theory.</a>

%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>, Math StackExchange.

%H Marko Riedel, <a href="/A076263/a076263_1.maple.txt">Maple code for sequences A008406 and A076263 including cycle indices.</a>

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

%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;

%e 1, 1;

%e 2, 2, 1, 1;

%e 3, 5, 5, 4, 2, 1, 1;

%e 6, 13, 19, 22, 20, 14, 9, 5, 2, 1, 1;

%e 11, 33, 67, 107, 132, 138, 126, 95, 64, 40, 21, 10, 5, 2, 1, 1;

%t NumberOfConnectedGraphs[vertices_, edges_] := Plus @@ ConnectedQ /@ ListGraphs[vertices, edges] /. {True->1, False ->0}

%t (* first do *) Needs["DiscreteMath`Combinatorica`"] (* then *) Table[Plus @@ ConnectedQ /@ ListGraphs[Vert, i] /. {True -> 1, False -> 0}, {Vert, 8}, {i, Vert - 1, Vert*(Vert - 1)/2}]

%Y 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: A002905.

%Y Number of entries in the n-th row is A152947. Row sums give A001349.

%Y Transpose of A054924, which is the main entry for this triangle.

%K nonn,tabf

%O 1,5

%A Arne Ring (arne.ring(AT)epost.de), Oct 03 2002

%E Corrected by Keith Briggs and _Robert G. Wilson v_, May 01 2005

%E Rows 5, 6 & 7 from _Robert G. Wilson v_, Jun 21 2005

%E More terms from Keith Briggs (Keith.Briggs(AT)bt.com), Jun 28 2005

%E Name corrected by _Andrey Zabolotskiy_, Nov 20 2017

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 November 18 01:14 EST 2018. Contains 317279 sequences. (Running on oeis4.)