login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A244742 Dimension of the vector space of 4-invariants on simple unlabeled graphs on n vertices. 0
1, 2, 3, 6, 10, 19, 32, 57 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

An invariant on graphs is a function that takes the same values on isomorphic graphs.

A 4-invariant f is an invariant such that for any graph G and any pair of vertices A,B connected by an edge in G,

f(G) - f(r(G,A,B)) = f(t(G,A,B)) - f(r(t(G,A,B),A,B)),

where:

r(G,A,B)=r(G,B,A) is a graph obtained from G by removal of edge (A,B);

t(G,A,B) is a graph H obtained from G by modifying the neighborhood of vertex A: N_H(A) is the symmetric difference of N_G(A) and N_G(B). (Note that t(G,A,B) and t(G,B,A) may differ.)

The 4-invariants on graphs with n vertices form a vector space, whose dimension is given by this sequence.

Similar 4-invariants can be defined on graphs with each vertex A having a label l(A) from the set {0,1}. In this case, the definition of r(G,A,B) and t(G,A,B) is the same when l(B)=0, but if l(B)=1 then in t(G,A,B) the value of l(A) is inverted and the edge (A,B) is removed, while in r(t(G,A,B),A,B) this edge is added back. The dimensions of the vector space of such 4-invariants on graphs with n<=5 vertices are 2,5,11,26,58. These values match A026787 but do they really represent this sequence?

LINKS

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

S. K. Lando, Graph invariants related to knot invatiants. Moscow Mathematical Conference for School Students, 2008. (in Russian)

S. K. Lando, J-invariants of plane curves and framed chord diagrams. Functional Analysis and Its Applications, 40:1 (2006), 1-13. doi:10.1007/s10688-006-0001-8

CROSSREFS

Cf. A000088

Sequence in context: A089985 A191518 A217382 * A007473 A014595 A079959

Adjacent sequences:  A244739 A244740 A244741 * A244743 A244744 A244745

KEYWORD

nonn,hard,more

AUTHOR

Max Alekseyev, Jul 05 2014

EXTENSIONS

a(1)-a(7) are given by S.K. Lando.

a(8) from Max Alekseyev, Jul 11 2014

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 26 05:10 EST 2020. Contains 331273 sequences. (Running on oeis4.)