Double Coalitions in Regular Graphs

Abstract A set S of vertices in a graph G is a dominating set of G if every vertex not in S has a neighbor in S , where two vertices are neighbors if they are adjacent. If G is isolate-free, then a set $$S \subseteq V(G)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>S</mml:mi> <mml:mo>⊆</mml:mo> <mml:mi>V</mml:mi> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> is a double dominating set of G if every vertex in $$V(G) \setminus S$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>V</mml:mi> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> <mml:mo>\</mml:mo> <mml:mi>S</mml:mi> </mml:mrow> </mml:math> has at least two neighbors in S , and every vertex in S has at least one neighbor in S . A double coalition in G consists of two disjoint sets of vertices X and Y of G , neither of which is a double dominating set but whose union $$X \cup Y$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>X</mml:mi> <mml:mo>∪</mml:mo> <mml:mi>Y</mml:mi> </mml:mrow> </mml:math> is a double dominating set of G . Such sets X and Y are said to form a double coalition. A double coalition partition in G is a vertex partition $$\Psi = \{V_1,V_2,\ldots ,V_k\}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>Ψ</mml:mi> <mml:mo>=</mml:mo> <mml:mo>{</mml:mo> <mml:msub> <mml:mi>V</mml:mi> <mml:mn>1</mml:mn> </mml:msub> <mml:mo>,</mml:mo> <mml:msub> <mml:mi>V</mml:mi> <mml:mn>2</mml:mn> </mml:msub> <mml:mo>,</mml:mo> <mml:mo>…</mml:mo> <mml:mo>,</mml:mo> <mml:msub> <mml:mi>V</mml:mi> <mml:mi>k</mml:mi> </mml:msub> <mml:mo>}</mml:mo> </mml:mrow> </mml:math> such that for all $$i \in [k]$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>i</mml:mi> <mml:mo>∈</mml:mo> <mml:mo>[</mml:mo> <mml:mi>k</mml:mi> <mml:mo>]</mml:mo> </mml:mrow> </mml:math> , the set $$V_i$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>V</mml:mi> <mml:mi>i</mml:mi> </mml:msub> </mml:math> forms a double coalition with another set $$V_j$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>V</mml:mi> <mml:mi>j</mml:mi> </mml:msub> </mml:math> for some j , where $$j \in [k] \setminus \{i\}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>j</mml:mi> <mml:mo>∈</mml:mo> <mml:mo>[</mml:mo> <mml:mi>k</mml:mi> <mml:mo>]</mml:mo> <mml:mo>\</mml:mo> <mml:mo>{</mml:mo> <mml:mi>i</mml:mi> <mml:mo>}</mml:mo> </mml:mrow> </mml:math> . The double coalition number, $$\textrm{DC}(G)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mtext>DC</mml:mtext> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> </mml:math> , of G equals the maximum order of a double coalition partition in G . We discuss the problem to determine or estimate the best possible constants $$\theta _{r}^{\textrm{reg}}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msubsup> <mml:mi>θ</mml:mi> <mml:mrow> <mml:mi>r</mml:mi> </mml:mrow> <mml:mtext>reg</mml:mtext> </mml:msubsup> </mml:math> and $$\theta _{r}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msub> <mml:mi>θ</mml:mi> <mml:mi>r</mml:mi> </mml:msub> </mml:math> (which depend only on r ) for each $$r \ge 3$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>r</mml:mi> <mml:mo>≥</mml:mo> <mml:mn>3</mml:mn> </mml:mrow> </mml:math> , such that $$\textrm{DC}(G) \le \theta _{r}^{\textrm{reg}} \times r$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mtext>DC</mml:mtext> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow> <mml:mo>≤</mml:mo> <mml:msubsup> <mml:mi>θ</mml:mi> <mml:mrow> <mml:mi>r</mml:mi> </mml:mrow> <mml:mtext>reg</mml:mtext> </mml:msubsup> <mml:mo>×</mml:mo> <mml:mi>r</mml:mi> </mml:mrow> </mml:math> for the class of r -regular graphs G and $$\textrm{DC}(G) \le \theta _{r} \times \Delta (G)$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mtext>DC</mml:mtext> <mml:mrow> <mml:mo>(</mml:mo> <mml:mi>G</mml:mi> <mml:mo>)</mml:mo> </mml:mrow>