Values
([(0,1)],2) => 2
([(0,2),(1,2)],3) => 2
([(0,1),(0,2),(1,2)],3) => 6
([(0,3),(1,3),(2,3)],4) => 0
([(0,3),(1,2),(2,3)],4) => 2
([(0,3),(1,2),(1,3),(2,3)],4) => 4
([(0,2),(0,3),(1,2),(1,3)],4) => 12
([(0,2),(0,3),(1,2),(1,3),(2,3)],4) => 14
([(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)],4) => 24
([(0,4),(1,4),(2,4),(3,4)],5) => 0
([(0,4),(1,4),(2,3),(3,4)],5) => 0
([(0,4),(1,4),(2,3),(2,4),(3,4)],5) => 0
([(0,4),(1,2),(1,3),(2,4),(3,4)],5) => 6
([(0,4),(1,3),(2,3),(2,4),(3,4)],5) => 2
([(0,4),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 6
([(0,3),(0,4),(1,3),(1,4),(2,3),(2,4)],5) => 26
([(0,3),(0,4),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 26
([(0,4),(1,3),(2,3),(2,4)],5) => 2
([(0,3),(1,2),(1,4),(2,4),(3,4)],5) => 4
([(0,3),(0,4),(1,2),(1,4),(2,4),(3,4)],5) => 8
([(0,3),(0,4),(1,2),(1,4),(2,3)],5) => 20
([(0,1),(0,4),(1,3),(2,3),(2,4),(3,4)],5) => 24
([(0,3),(0,4),(1,2),(1,4),(2,3),(2,4),(3,4)],5) => 28
([(0,4),(1,2),(1,3),(2,3),(2,4),(3,4)],5) => 8
([(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 12
([(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 48
([(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4)],5) => 44
([(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,4),(3,4)],5) => 64
([(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 84
([(0,1),(0,2),(0,3),(0,4),(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)],5) => 120
search for individual values
searching the database for the individual values of this statistic
Description
The second Elser number of a connected graph.
For a connected graph $G$ the $k$-th Elser number is
$$ els_k(G) = (-1)^{|V(G)|+1} \sum_N (-1)^{|E(N)|} |V(N)|^k $$
where the sum is over all nuclei of $G$, that is, the connected subgraphs of $G$ whose vertex set is a vertex cover of $G$.
It is clear that this number is even. It was shown in [1] that it is non-negative.
For a connected graph $G$ the $k$-th Elser number is
$$ els_k(G) = (-1)^{|V(G)|+1} \sum_N (-1)^{|E(N)|} |V(N)|^k $$
where the sum is over all nuclei of $G$, that is, the connected subgraphs of $G$ whose vertex set is a vertex cover of $G$.
It is clear that this number is even. It was shown in [1] that it is non-negative.
References
[1] Dorpalen-Barry, G., Hettle, C., Livingston, D. C., Martin, J. L., Nasr, G., Vega, J., Whitlatch, H. A positivity phenomenon in Elser's Gaussian-cluster percolation model arXiv:1905.11330
Code
def nuclei(G):
V = set(G.vertices())
for H in G.connected_subgraph_iterator():
for E in subsets(H.edges()):
J = G.subgraph(vertices=H.vertices(), edges=E)
if not J.is_connected():
continue
if G.is_independent_set(V.difference(J.vertices())):
yield J
def elser(G, k):
"""
sage: set([elser(G, 0) for n in range(2, 6) for G in graphs(n) if G.is_connected()])
{-6, -4, -3, -2, -1, 0}
sage: set([elser(G, 1) for n in range(2, 6) for G in graphs(n) if G.is_connected()])
{0}
sage: set([elser(G, 2) for n in range(2, 6) for G in graphs(n) if G.is_connected()])
{0, 2, 4, 6, 8, 12, 14, 20, 24, 26, 28, 44, 48, 64, 84, 120}
"""
n = G.num_verts()
return (-1)^(n+1)*sum((-1)^N.num_edges()*N.num_verts()^k for N in nuclei(G))
def statistic(G):
return elser(G, 2)
Created
May 13, 2020 at 20:11 by Martin Rubey
Updated
May 13, 2020 at 20:11 by Martin Rubey
searching the database
Sorry, this statistic was not found in the database
or
add this statistic to the database – it's very simple and we need your support!