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)