PaperlayerView exact revision on arXiv

Source-linked AI summary

Complexity, Bounds, and Exact Algorithms for Rainbow $k$-Domination in Regular Graphs

Piotr Lange

arXiv:2610.06906v1cs.DMcs.CC

TL;DR

Rainbow k-domination in regular graphs requires each uncolored vertex to have all k colors nearby, while each selected vertex carries only one color. The paper develops bounds, complexity results, exact formulas, and a dynamic program for P(6t, t). It establishes exact results for Möbius ladders and prisms and reports that the k = 3 computations for P(6t, t) used an ILP solver because the dynamic program was impractical.

  • Problem

    The paper studies rainbow k-domination in regular graphs, including the open problem of proving conjectures about modular behavior in P(6t, t).

    Source: §1 · p. 2, §7 · p. 22

  • Method

    The authors derive regular-graph bounds and structural results, prove NP-completeness, obtain exact formulas for standard graph families, and develop a dynamic program for P(6t, t).

    Source: §1 · p. 2

  • Results

    The paper determines eγ3(Mn) by n modulo 12 and determines eγk(Pr(m)) for all k, while computational evidence suggests more complicated modular behavior for P(6t, t).

    Source: §7 · p. 22

  • Takeaways & Limitations

    The exact formulas cover cycles, Möbius ladders, and prisms, while the P(6t, t) computational patterns remain conjectural and may motivate periodic constructions and lower bounds.

    Source: §1 · p. 2, §7 · p. 22

    The dynamic program is effective for k = 2 but impractical for k = 3, so the reported k = 3 data were obtained with a Python script using Gurobi ILP.

    Source: §6.2 · p. 20

Abstract

from arXiv · show

A rainbow $k$-dominating function assigns the empty set or exactly one of the colors $\{1\},\{2\},\ldots,\{k\}$ to each vertex of a simple graph in such a way that every vertex receiving $\emptyset$ sees all $k$ colors in its neighborhood. This model has several facility-location interpretations where colored vertices represent sites hosting different types of services, and uncolored vertices represent the beneficiaries of those services who must have access to all of them. In this paper we study this domination variant in regular graphs. First, we develop lower and upper bounds for this class of graphs, and explore their structural consequences. Then, we use those results to prove NP-completeness of a decision formulation of this problem. Additionally, we derive exact formulas for the rainbow $k$-domination number of cycles, M\"obius ladders and prisms. Lastly, we develop a dynamic-programming algorithm for generalized Petersen graphs of the form $P(6t, t)$ and state two conjectures based on the output of its implementation and related integer linear programming computations.

1 Introduction

Rainbow domination requires uncolored vertices to access all required colors nearby, with the singleton version limiting each selected vertex to one color. This paper studies that model in regular graphs, developing bounds, complexity results, exact formulas, and an algorithm for a generalized Petersen graph family.

1 Introduction

  • Domination models have applications in facility location, system control and monitoring, network design, and resource distribution.These applications have motivated a broader family of domination-type graph parameters.Source: §1 · p. 1
  • Unlike the classical k-rainbow model, which permits any subset of colors at a vertex, singleton rainbow domination assigns at most one color per selected vertex.The classical model was introduced by Brešar, Henning, and Rall.Source: §1 · p. 1
  • In singleton rainbow k-domination, each selected vertex receives exactly one color, and every uncolored vertex must see all k colors in its open neighborhood.The minimum weight is denoted eγk(G); for k = 2, the model has also been called rainbow 2-domination and dual-server domination.Source: §1 · p. 1
  • The singleton restriction fits settings where each selected location can provide only one resource type, including a model of post-disaster shelter camps.In that model, uncolored vertices are accommodation units and colored vertices are service-providing facilities.Source: §1 · pp. 1–2
  • The paper develops bounds for regular graphs, proves NP-completeness, derives exact formulas for several graph families, and presents a specialized dynamic program.The algorithm targets generalized Petersen graphs P(6t, t), with computational evidence motivating further conjectures.Source: §1 · p. 2

2 Preliminaries

The preliminaries define the singleton rainbow domination parameter and the graph notation used throughout. They also specify its decision problem and basic restrictions for regular graphs.

2 Preliminaries

  • Graphs are finite, simple, and undirected; r-regular means every vertex has degree r, and 3-regular graphs are cubic.The order of G is n = |V(G)|.Source: §2 · p. 2
  • A rainbow k-dominating function assigns each vertex either no color or one color, and every uncolored vertex must see all k colors in its neighborhood.Its minimum weight over such functions is eγk(G).Source: §2 · p. 2
  • The decision problem asks whether a graph G has a rainbow k-dominating function of weight at most B.A proposed function's weight and domination condition can be checked in polynomial time.Source: §2 · p. 3
  • When k exceeds the regular degree r, every vertex must be colored, so the minimum weight is n; the paper usually considers 1 ≤ k ≤ r.An uncolored vertex cannot see more colors than its r neighbors can carry under singleton assignments.Source: §2 · p. 3
  • The sparse induced-subgraph parameter αs(G) is the maximum order of an induced subgraph with maximum degree at most s.For s = 0, it is the independence number α(G).Source: §2 · p. 3

3 Bounds and extremal regular graphs

The section establishes lower and probabilistic upper bounds for rainbow k-domination in regular graphs, then characterizes the equality case when k = r. It also derives a sharper cubic-graph bound and identifies structural consequences of equality.

3 Bounds and extremal regular graphs

  • The lower-bound and equality-case results use regularity to constrain colored and uncolored vertices, with the equality case forcing a bipartition.For k = r, every uncolored vertex has r colored neighbors of pairwise distinct colors.Source: §3 · pp. 4, 6, 7
  • In the equality characterization, n = q(k + r) + s with 0 ≤ s < k + r, and 2r divides n.The equal-sized bipartition sides and edge counts between each color class and the uncolored side yield the divisibility condition.Source: §3 · pp. 4, 7
  • For cubic graphs of order n, the bound is n/2 when n ≡ 0 (mod 6), and n/2 + 1 when n ≡ 2 or 4 (mod 6).The section also notes a structural bound that can be stronger when αr−k(G) is small.Source: §3 · p. 4
  • The section presents a lower bound for r-regular graphs and a complementary lower bound expressed through sparse induced subgraphs.The latter can be stronger when αr−k(G) is small.Source: §3 · p. 4
  • Two probabilistic upper bounds complement the lower bounds, including a regular-graph-specific bound that is stronger for some r and k values.One approach colors an independent set's complement and uses the probability that each independent-set vertex sees all k colors.Source: §3 · pp. 4–5
  • The combined normalized upper bound favors the regular-graph-specific bound at smaller r and the logarithmic bound at larger r.Its numerical values for different r and k are shown in Figure 2.Source: §3 · p. 5, Figure 2 · p. 6
  • For r-regular graphs with k = r, attaining eγk(G) = n/2 is characterized by a bipartition and a partition of one side into color classes.Every vertex on the uncolored side must have exactly one neighbor in each color class; the characterization is a singleton reformulation of an equality case from [15].Source: §3 · p. 5
  • For cubic graphs, equality forces 6 | n and bipartiteness, with three equally large colored classes giving each opposite-side vertex exactly one neighbor in each class.This makes the extremal case structurally restrictive.Source: §3 · p. 7

4 NP-completeness for regular graphs

For every fixed r ≥3, deciding whether a bipartite r-regular graph has rainbow r-domination number |V(G)|/2 is NP-complete. The proof reduces strong r-coloring of uniform regular hypergraphs to this equality test using a forcing gadget.

4 NP-completeness for regular graphs

  • The forcing gadget admits a coloring making every W-vertex see all r colors, but no coloring of W makes every vertex of F \ {E0} see them.In the modified gadget, any coloring making every W-vertex see all r colors forces c(x) = c(E0).Source: §4 · p. 8
  • For every fixed r ≥3, deciding whether eγr(G) = |V(G)|/2 is NP-complete, even for bipartite r-regular graphs.Consequently, computing eγr(G) is NP-hard on this graph class.Source: §4 · pp. 9–10
  • Each incidence component is switched with a constant-size gadget to form a connected bipartite r-regular graph, and the construction runs in polynomial time for fixed r ≥3.The constructed graph has N = 2|X| + 4rs vertices.Source: §4 · p. 9
  • The reduction makes the equality eγr(G) = N/2 equivalent to whether the input hypergraph admits a strong r-coloring.It starts from Strong r-Coloring of Uniform Regular Hypergraphs, stated for simple linear r-uniform r-regular hypergraphs.Source: §4 · pp. 7, 9, 10
  • A strong hypergraph coloring yields a rainbow r-dominating function of weight N/2, while a minimum function of that weight yields a strong coloring.The reverse direction uses the equality structure and the gadget constraint to transfer colors back to the hypergraph.Source: §4 · pp. 9–10

5 Exact values for selected regular families

The section derives exact rainbow k-domination values for cycles, Möbius ladders, and prism graphs by applying bounds and extremal characterizations to these regular families.

5.1 Cycles

  • For k=2, the cited cycle constructions have weights n/2, n/2+1, and (n+1)/2; for k≥3, every vertex of Cn must be colored because its degree is 2.Every connected 2-regular graph is a cycle.Source: §5.1 · pp. 11–12

5.2 Möbius ladders

  • For Möbius ladders M_n, the rainbow 3-domination number is n/2 when n ≡6 (mod 12), n/2+1 for residues 0, 4, or 8, and n/2+2 for residues 2 or 10.The result applies to even n≥4.Source: §5.2 · p. 12

5.3 Prism graphs

  • For prism graphs, the rainbow 3-domination number is m, m+1, or m+2 according to m modulo 6, while k≥4 gives 2m.The section obtains these exact values using lemmas and known results for related domination parameters.Source: §5.3 · pp. 13–14

6 Dynamic programming for generalized Petersen graphs

This section develops an exact finite-state dynamic program for rainbow domination on generalized Petersen graphs P(6t, t), with linear-in-t complexity for fixed k in {1, 2, 3}. Computations and ILP results motivate a conjecture for the previously unresolved t ≡ 3 (mod 6) case of eγ3(P(6t, t)), while the dynamic program is reported to be impractical for k = 3.

6 Dynamic programming for generalized Petersen graphs

  • The algorithm partitions P(6t, t) into blocks whose rainbow-domination constraints depend only on neighboring blocks, enabling a constant-width dynamic program.The authors also note that the graph has a path decomposition of width at most 35, allowing a bounded-treewidth approach; their algorithm was developed independently to exploit the graph's structure and rainbow-domination constraints.Source: §6 · p. 15, §6.1 · p. 17

6.1 A linear-time algorithm

  • For every t ≥ 2 and 1 ≤ k ≤ 3, Algorithm 2 returns the exact rainbow k-domination number of P(6t, t) in time linear in t for fixed k.Its running time is O(tS^5), where S depends only on k, and its memory use is constant for fixed k.Source: §6 · p. 15, §6.1 · pp. 17, 19

6.2 Computational evidence and conjectures

  • For k = 2, the implementation computed exact values for 2 ≤ t ≤ 20, with runtimes from 0.022 seconds at t = 2 to 52124.481 seconds at t = 20.The observed runtimes closely followed a linear trend as t increased, providing empirical support for the theoretical O(t) complexity.Source: §6.2 · p. 20
  • The dynamic program was impractical for k = 3, so the reported k = 3 data were obtained with a Python script using Gurobi ILP.The authors attribute the limitation to the growth in the number of states and the substantial runtimes observed even for their specialized k = 2 implementation.Source: §6.2 · p. 20
  • The gathered data motivate an exact-formula conjecture for k = 2; prior work established 3-rainbow domination results for several infinite subfamilies and conjectured a stronger bound when t ≡ 3 (mod 6).The supplied passage introducing the k = 2 formula is incomplete, so its expression is not reported here.Source: §6.2 · p. 20
  • Computations cover all tested instances in the remaining class and suggest eγ3(P(6t, t)) = 6t + 6 for every t ≡ 3 (mod 6) with t ≥ 9.The conjecture is paired with the exceptional value eγ3(P(18, 3)) = 22.Source: §6.2 · pp. 20–21
  • eγ3(P(18, 3)) = 22.This value is reported separately from the conjectured formula for t ≥ 9.Source: §6.2 · p. 20
  • ILP instances with t ≡ 1, 5 (mod 6) solve relatively quickly, even t requires moderately more time, and t ≡ 3 (mod 6) becomes substantially harder as t increases.The latter instances take one or more orders of magnitude longer than neighboring instances; this matches the distinction that exact values were known for t ≡ 0, 1, 2, 4, 5 (mod 6), while only bounds were known for t ≡ 3 (mod 6).Source: §6.2 · p. 21, Figure 9 · p. 21

7 Conclusion

The paper combines structural bounds for regular graphs with hardness results, exact formulas for selected graph families, and an exact algorithm for generalized Petersen graphs. Its computations motivate two conjectures, while several proof and extension questions remain open.

Conclusion

  • For arbitrary regular graphs, the paper establishes two lower and two upper bounds; at equality eγr(G) = |V(G)|/2, the graph must be bipartite with one side partitioned into r color classes, each seen once by every vertex on the other side.The authors identify these structural results as a basis for further study.Source: §7 · p. 21
  • Deciding whether eγr(G) = |V(G)|/2 is NP-complete even for regular bipartite graphs, using the extremal equality characterization and hypergraph coloring results.The paper describes this as computational hardness under strong structural constraints.Source: §7 · p. 21
  • For cycles, the paper relates dual-server domination to rainbow 2-domination and gives a self-contained proof using previously established lower bounds.Source: §7 · p. 21
  • For Möbius ladders, eγ3(Mn) depends on n modulo 12; for prisms, the paper determines eγk(Pr(m)) for all k using known results, counting arguments, and constructions.Source: §7 · p. 22
  • For P(6t, t), a finite-state dynamic program computes eγk exactly in linear time for each fixed k ∈ {1, 2, 3}, and computations motivate closed-form conjectures for k = 2 and 3.The conjectures still require proof.Source: §7 · p. 22
  • Open directions include proving the P(6t, t) conjectures, extending the algorithm to broader generalized Petersen families, and studying complexity in other graph classes and parameter ranges.Source: §7 · p. 22

A Proofs for Möbius ladders

The Möbius-ladder proofs combine lower-bound arguments with explicit colorings to establish rainbow 3-domination weights in several cases. They also rule out a proposed weight for two residue classes by counting edges between uncolored vertices and color classes.

Proofs for Möbius ladders

  • For n = 12q + 6, an explicit coloring gives a rainbow 3-dominating function of weight n/2 + 1.The construction colors selected odd-indexed vertices on one cycle and selected even-indexed vertices on the other, then checks that each uncolored vertex sees all three colors.Source: A Proofs for Möbius ladders · pp. 24, 26
  • The proof also gives a rainbow 3-dominating function of weight n/2 in a further case.Source: A Proofs for Möbius ladders · p. 24
  • For n ≡ 2 or 10 (mod 12), assuming eγ3(Mn) = L + 1 leads to a contradiction, although Corollary 3 gives eγ3(Mn) ≥ L + 1.The proof uses congruence conditions on each ti: they are all 2 when n ≡ 10 (mod 12), and each is 0 or 3 when n ≡ 2 (mod 12).Source: A Proofs for Möbius ladders · pp. 24–25
  • A separate construction gives a rainbow 3-dominating function of weight n/2 + 2 in another case treated by the proofs.The construction assigns a sequence of colors to odd-indexed vertices and verifies distinct neighbor colors for every uncolored vertex.Source: A Proofs for Möbius ladders · p. 26

B Proofs for prism graphs

The prism proofs use explicit colorings for upper bounds and structural counting arguments to exclude a candidate weight for rainbow 3-domination. The arguments exploit the graph’s paired vertices and, when m is even, its bipartition.

Proofs for prism graphs

  • For rainbow 2-domination, an explicit coloring of Pr(m) has weight m and gives every uncolored vertex both colors in its neighborhood.Source: B Proofs for prism graphs · p. 28
  • For m ≡ 2 (mod 6), the proof rules out a rainbow 3-dominating function of weight m + 1 by counting edges from uncolored vertices to each color class.The count forces two neighbors of a selected vertex into each color class, contradicting the assumed coloring.Source: B Proofs for prism graphs · p. 28
  • Under that assumed weight, the uncolored vertices form an independent set of size m − 1 and alternate between the two cycles, leaving one vertex from a bipartition class deleted.Source: B Proofs for prism graphs · p. 28

C Gathered data

The gathered data report exact rainbow 2-domination values and computation times for P(6t, t) using Algorithm 2, and exact rainbow 3-domination values and Gurobi ILP computation times for 2 ≤ t ≤ 51.

C Gathered data

  • Table 1 reports exact rainbow 2-domination numbers for P(6t, t) and computation times gathered using Algorithm 2.Source: Table 1 · p. 29
  • Table 2 reports exact rainbow 3-domination numbers for P(6t, t) and Gurobi ILP computation times for 2 ≤ t ≤ 51.Source: Table 2 · p. 30
Loading 2610.06906v1…