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-k-domination number.
Parameters: G (NetworkX graph) – An undirected graph. Returns: The Slater invariant for the graph. Return type: int See also
References
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)