A182531 Extremal graph numbers for a triangle with an edge off it.

0, 1, 3, 4, 6, 9, 12, 16, 20, 25, 30, 36, 42, 49, 56, 64, 72, 81, 90, 100, 110, 121, 132, 144, 156, 169, 182, 196, 210, 225, 240, 256, 272

Offset

1,3

Comments

The largest possible number of edges in a graph on n nodes that does not contain a triangle with an edge off it as a subgraph.

Assuming Colin Barker's conjectures this is A002378 and the positive terms of A000290 interleaved, except for a(3) = 3. - Omar E. Pol, Jan 25 2018

Links

Table of n, a(n) for n=1..33.

Paul Tabatabai, Python script (Gurobi), updated version on Jul 28 2020

Formula

Conjectures from Colin Barker, Jul 04 2016: (Start)

a(n) = (-1+(-1)^n+2*n^2)/8 for n>3.

a(n) = n^2/4 for n>3 and even.

a(n) = (n^2-1)/4 for n>3 and odd.

a(n) = 2*a(n-1)-2*a(n-3)+a(n-4) for n>4.

G.f.: x^2*(1+x-x^2)*(1-x^2+x^3) / ((1-x)^3*(1+x)).

(End)

Example

For n=4 the 4-cycle is a graph on 4 nodes that avoids the triangle with an edge off it.

Crossrefs

Sequence in context: A260109 A283777 A202171 * A097922 A103109 A241639

Adjacent sequences: A182528 A182529 A182530 * A182532 A182533 A182534

Keyword

nonn,more

Author

John Y. Kim, May 03 2012

Extensions

a(8)-a(23) from Paul Tabatabai, Jul 04 2016

a(24)-a(33) from Manfred Scheucher, Jan 25 2018

Status

approved