NUK - logo
E-viri
Celotno besedilo
Recenzirano
  • Proof of a conjecture on do...
    Yang, Wei; Wu, Baoyindureng

    Discrete mathematics, October 2024, 2024-10-00, Letnik: 347, Številka: 10
    Journal Article

    The k-component domination number γk(G) of G is the minimum cardinality of a dominating set S of G such that each component of GS has order at least k. Clearly, γ1(G) is the domination number of G and γ2(G) is the total domination number of G. With a finite set of exceptional graphs, McCuaig and Shepherd (1989) 13 proved that γ1(G)≤25n and Henning (2000) 11 proved that γ2(G)≤47n respectively. As an extension, Alvarado et al. (2016) 1 posed a conjecture which says that if G is a connected graph of order n≥k+1 and δ(G)≥2, then γk(G)≤2kn2k+3 unless G belongs to a set of exceptional graphs. In this paper, we confirm the validity of the above conjecture. Moreover, we characterize those graphs of order n which are edge-minimal with respect to satisfying G connected, δ(G)≥2 and γk(G)≥2kn2k+3. This strengthens a result of Alvarado, Dantas, and Rautenbach in the same paper.