Open math1um opened 3 years ago
binding_number = min(|N(U)|/|U|, over all non-empty subsets U of the vertex set V, where N(U) is not all of V)
N(U) = neighbors of U
as described it is clearly exponential - considering all subsets is exponential.
ADD to intractable_invariants list
defined in:
Woodall, D. R. "The binding number of a graph and its Anderson number." Journal of Combinatorial Theory, Series B 15, no. 3 (1973): 225-255.
binding_number = min(|N(U)|/|U|, over all non-empty subsets U of the vertex set V, where N(U) is not all of V)
N(U) = neighbors of U
as described it is clearly exponential - considering all subsets is exponential.
ADD to intractable_invariants list
defined in:
Woodall, D. R. "The binding number of a graph and its Anderson number." Journal of Combinatorial Theory, Series B 15, no. 3 (1973): 225-255.