login
A244742
Dimension of the vector space of 4-invariants on simple unlabeled graphs on n vertices.
1
1, 2, 3, 6, 10, 19, 32, 57, 94
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} (cf. A362740).
CROSSREFS
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
a(9) from Max Alekseyev, May 08 2023
STATUS
approved