A Construction that Preserves the Number of k-Kernels
Hortensia Galeana‐Sánchez, Ciudad Universitaria · 2011
Let D be a digraph. Let k be a natural number with k 2. A set J ⊆ V (D) will be called a k-kernel of the digraph D iff: 1) For each x, x′ ∈ J , x = x′ we have dD(x, x′) k and 2) For each y ∈ V (D) − J , there exists x ∈ J such that dD(y, x) ≤ k − 1. In [4], for any digraph D we constructed a digraph s(S) such that D has a k-kernel iff s(S) has a k-kernel. In this paper we prove that the number of k-kernels in s(S) is equal to the number of k-kernels in D. Mathematics Subject Classification: 05C20