cp's OEIS Frontend

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