*****************************************************************************
*       www.FindStat.org - The Combinatorial Statistic Finder               *
*                                                                           *
*       Copyright (C) 2019 The FindStatCrew <info@findstat.org>             *
*                                                                           *
*    This information is distributed in the hope that it will be useful,    *
*    but WITHOUT ANY WARRANTY; without even the implied warranty of         *
*    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.                   *
*****************************************************************************

-----------------------------------------------------------------------------
Statistic identifier: St001545

-----------------------------------------------------------------------------
Collection: Graphs

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


-----------------------------------------------------------------------------
Statistic 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

-----------------------------------------------------------------------------
Created: May 13, 2020 at 20:11 by Martin Rubey

-----------------------------------------------------------------------------
Last Updated: May 13, 2020 at 20:11 by Martin Rubey