grinpy.invariants.dsi.slater

grinpy.invariants.dsi.slater(G)

Return the Slater invariant for the graph.

The Slater invariant of a graph G is a lower bound for the domination number of a graph defined by:

\[sl(G) = \min{t : t + \sum_{i=0}^t d_i \geq n}\]

where

\[{d_1 \geq d_2 \geq \cdots \geq \d_n}\]

is the degree sequence of the graph ordered in non-increasing order and n is the order of G.

Amos et al. rediscovered this invariant and generalized it into what is now known as the sub-domination number.

G : graph
A Networkx graph.
slater : int
The Slater invariant for the graph.

sub_k_domination_number

D. Amos, J. Asplund, B. Brimkov and R. Davila, The sub-k-domination number of a graph with applications to k-domination, arXiv preprint arXiv:1611.02379, (2016)

P.J. Slater, Locating dominating sets and locating-dominating set, Graph Theory, Combinatorics and Applications: Proceedings of the 7th Quadrennial International Conference on the Theory and Applications of Graphs, 2: 2073-1079 (1995)