Changing and Unchanging 2-Rainbow Independent Domination

Xiaolong Shi, Pu Wu, Zehui Shao, Vladimir Samodivkin, Seyed Mahmoud Sheikholeslami, Marzieh Soroudi, Shaohui WangIEEE Access 2019 · DOI

TL;DR

This paper introduces and studies the concept of "2-rainbow independent domination" in graphs, a specific type of vertex covering. The authors characterize trees that are "stable" under vertex removal (meaning their domination number doesn't change), and investigate how edge removal affects this number in trees.

What Problem Does This Paper Address?

The paper delves into graph domination theory, a field concerned with finding minimum sets of vertices that "dominate" all other vertices in a graph. Domination is typically defined by a vertex and its neighbors. The authors focus on a more complex variant: "2-rainbow independent domination." This requires a set of vertices to be independent (no two vertices are adjacent) and to collectively dominate all other vertices, with specific colorings (0, 1, or 2) assigned to vertices. The core problem is to understand the "2-rainbow independent domination number" (the minimum size of such a set) and to identify graph structures, specifically trees, that exhibit stability with respect to this number. Stability here means that removing a vertex from the graph does not change the domination number. The paper also explores the impact of edge removal on this number.

Methods

The authors build upon existing definitions of graph domination and introduce the "2-rainbow independent dominating function" (2RiDF). A 2RiDF assigns values 0, 1, or 2 to vertices such that vertices assigned 1 or 2 form independent sets, and every vertex assigned 0 is adjacent to at least one vertex assigned 1 and at least one vertex assigned 2. The "2-rainbow independent domination number" is the minimum weight (sum of vertices assigned 1 or 2) of such a function. The paper then defines "2-rainbow independent domination stable" graphs as those where removing any vertex does not change this number. The core methodology involves:

  • Characterization of Stable Trees: The authors define a specific family of trees, denoted by $\mathcal{T}$, constructed through a sequence of operations (adding paths and spiders). They then prove that a tree is 2-rainbow independent domination stable if and only if it belongs to this family $\mathcal{T}$.
  • Edge Removal Analysis: They analyze the effect of removing an edge from a tree on the 2-rainbow independent domination number, establishing bounds and identifying conditions for when the number increases by exactly one.
  • Proof Techniques: The proofs heavily rely on constructing specific 2RiDFs, using induction, and applying properties of graph structures like paths and spiders. They also leverage existing results and definitions from graph theory literature.

Datasets

Not discussed in the paper. The paper deals with theoretical graph properties and does not use empirical datasets.

Key Insights and Ideas

  • Structural Characterization of Stability: The most significant insight is the precise characterization of 2-rainbow independent domination stable trees. The fact that this stability can be achieved through a specific constructive process (operations O1, O2, O3) provides a clear structural understanding of these graphs.
  • Impact of Vertex Removal: The paper establishes that for a tree to be stable, removing any vertex must not change its 2-rainbow independent domination number. This is a strong condition that significantly restricts the possible structures of stable trees.
  • Edge Removal Bounds: The paper provides tight bounds on how the 2-rainbow independent domination number changes when an edge is removed from a tree, showing it can increase by at most 1. This offers a nuanced understanding of how local changes affect this global graph invariant.
  • Connection to Specific Tree Structures: The characterization of stable trees relies on specific constructions involving paths and spiders, highlighting the importance of these basic building blocks in achieving domination stability.

Key Results

  • Theorem 16: A tree $T$ of order $n \geq 3$ is 2-rainbow independent domination stable if and only if $T$ belongs to a specific family of trees $\mathcal{T}$ constructed through three defined operations.
  • Theorem 21: A tree $T$ of order $n > 3$ is 2-rainbow independent domination stable if and only if $T \in \mathcal{T}$.
  • Proposition 23: For an edge $e=xy$ in a tree $T$, the 2-rainbow independent domination number of $T-e$ is either equal to or one greater than that of $T$. Specifically, $\gamma_{ri2}(T) \leq \gamma_{ri2}(T-e) \leq \gamma_{ri2}(T) + 1$.
  • Theorem 24: Trees formed by subdividing edges of a non-trivial tree are 2-rainbow-ER-critical (meaning edge removal increases the domination number by exactly 1).
  • Corollary 27: An $n$-order $\gamma_{ri2}$-ER-critical tree exists if and only if $n \geq 3$ and $n$ is odd.

Limitations and Future Work

  • Focus on Trees: The current work primarily focuses on trees. While some results are presented for general graphs (e.g., Proposition 7 on cliques), the detailed characterizations are limited to trees.
  • Open Problems: The authors suggest several avenues for future research:
  • Finding sharp lower and upper bounds for the 2-rainbow independent domination number of connected $\gamma_{ri2}$-stable and $\gamma_{ri2}$-ER-critical graphs in terms of their order.
  • Determining the minimum/maximum number of edges for connected $\gamma_{ri2}$-stable ($\gamma_{ri2}$-ER-critical) graphs with a given order and domination number.
  • Characterizing all unicyclic $\gamma_{ri2}$-stable ($\gamma_{ri2}$-ER-critical) graphs.

Summary updated

BibTeX
@article{shi2019changing,
  author = {Xiaolong Shi and Pu Wu and Zehui Shao and Vladimir Samodivkin and Seyed Mahmoud Sheikholeslami and Marzieh Soroudi and Shaohui Wang},
  title = {{Changing and Unchanging 2-Rainbow Independent Domination}},
  journal = {IEEE Access},
  year = {2019},
  doi = {10.1109/access.2019.2919976},
}
Figure