Total Outer-Independent Domination Number: Bounds and Algorithms
In graph theory, the study of domination sets has garnered significant interest due to its applications in network design and analysis. Consider a graph <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2025-03-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/18/3/159 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | In graph theory, the study of domination sets has garnered significant interest due to its applications in network design and analysis. Consider a graph <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>G</mi><mo>(</mo><mi>V</mi><mo>,</mo><mi>E</mi><mo>)</mo></mrow></semantics></math></inline-formula>; a subset of its vertices is a total dominating set (TDS) if, for each <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>x</mi><mo>∈</mo><mi>V</mi><mo>(</mo><mi>G</mi><mo>)</mo></mrow></semantics></math></inline-formula>, there exists an edge in <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mi>E</mi><mo>(</mo><mi>G</mi><mo>)</mo></mrow></semantics></math></inline-formula> connecting <i>x</i> to at least one vertex within this subset. If the subgraph induced by the vertices outside the TDS has no edges, the set is called a total outer-independent dominating set (TOIDS). The total outer-independent domination number, denoted as <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msubsup><mi>γ</mi><mrow><mi>t</mi></mrow><mrow><mi>o</mi><mi>i</mi></mrow></msubsup><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula>, represents the smallest cardinality of such a set. Deciding if a given graph has a TOIDS with at most <i>r</i> vertices is an NP-complete problem. This study introduces new lower and upper bounds for <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msubsup><mi>γ</mi><mrow><mi>t</mi></mrow><mrow><mi>o</mi><mi>i</mi></mrow></msubsup><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula> and presents an exact solution approach using integer linear programming (ILP). Additionally, we develop a heuristic and a procedure to efficiently obtain minimal TOIDS. |
|---|---|
| ISSN: | 1999-4893 |