edit this statistic or download as text // json
Identifier
Values
=>
Cc0020;cc-rep
([(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.
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