<p>A set <i>S</i> of vertices in an isolate-free graph <i>G</i> is a total dominating set if every vertex of <i>G</i> is adjacent to some other vertex in <i>S</i>. A total coalition in <i>G</i> consists of two disjoint sets of vertices <i>X</i> and <i>Y</i> of <i>G</i>, neither of which is a total dominating set but whose union <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(X \cup Y\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>X</mi> <mo>∪</mo> <mi>Y</mi> </mrow> </math></EquationSource> </InlineEquation> is a total dominating set of <i>G</i>. Such sets <i>X</i> and <i>Y</i> are said to form a total coalition. A total coalition partition in <i>G</i> is a vertex partition <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\(\Psi = \{V_1,V_2,\ldots ,V_k\}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Ψ</mi> <mo>=</mo> <mo stretchy="false">{</mo> <msub> <mi>V</mi> <mn>1</mn> </msub> <mo>,</mo> <msub> <mi>V</mi> <mn>2</mn> </msub> <mo>,</mo> <mo>…</mo> <mo>,</mo> <msub> <mi>V</mi> <mi>k</mi> </msub> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation> such that for all <InlineEquation ID="IEq3"> <EquationSource Format="TEX">\(i \in [k]\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>i</mi> <mo>∈</mo> <mo stretchy="false">[</mo> <mi>k</mi> <mo stretchy="false">]</mo> </mrow> </math></EquationSource> </InlineEquation>, the set <InlineEquation ID="IEq4"> <EquationSource Format="TEX">\(V_i\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>V</mi> <mi>i</mi> </msub> </math></EquationSource> </InlineEquation> forms a total coalition with another set <InlineEquation ID="IEq5"> <EquationSource Format="TEX">\(V_j\)</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>V</mi> <mi>j</mi> </msub> </math></EquationSource> </InlineEquation> for some <i>j</i>, where <InlineEquation ID="IEq6"> <EquationSource Format="TEX">\(j \in [k] \setminus \{i\}\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>j</mi> <mo>∈</mo> <mo stretchy="false">[</mo> <mi>k</mi> <mo stretchy="false">]</mo> <mo lspace="0.15em" rspace="0.15em" stretchy="false">\</mo> <mo stretchy="false">{</mo> <mi>i</mi> <mo stretchy="false">}</mo> </mrow> </math></EquationSource> </InlineEquation>. We emphasize that none of the sets in <InlineEquation ID="IEq7"> <EquationSource Format="TEX">\(\Psi \)</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="normal">Ψ</mi> </math></EquationSource> </InlineEquation> is a total dominating set of <i>G</i>. The total coalition number <InlineEquation ID="IEq8"> <EquationSource Format="TEX">\(C_t(G)\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>C</mi> <mi>t</mi> </msub> <mrow> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </mrow> </math></EquationSource> </InlineEquation> in <i>G</i> equals the maximum order of a total coalition partition in <i>G</i>. We study total coalitions in claw-free cubic graphs with certain structural properties, namely, graphs containing double-bonded triangle-units, that is, two vertex disjoint triangles joined by two edges.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Total Coalitions in Claw-Free Cubic Graphs Containing Double-Bonded Triangle-Units

  • Zoltán L. Blázsik,
  • Michael A. Henning,
  • Shahin N. Jogan

摘要

A set S of vertices in an isolate-free graph G is a total dominating set if every vertex of G is adjacent to some other vertex in S. A total coalition in G consists of two disjoint sets of vertices X and Y of G, neither of which is a total dominating set but whose union \(X \cup Y\) X Y is a total dominating set of G. Such sets X and Y are said to form a total coalition. A total coalition partition in G is a vertex partition \(\Psi = \{V_1,V_2,\ldots ,V_k\}\) Ψ = { V 1 , V 2 , , V k } such that for all \(i \in [k]\) i [ k ] , the set \(V_i\) V i forms a total coalition with another set \(V_j\) V j for some j, where \(j \in [k] \setminus \{i\}\) j [ k ] \ { i } . We emphasize that none of the sets in \(\Psi \) Ψ is a total dominating set of G. The total coalition number \(C_t(G)\) C t ( G ) in G equals the maximum order of a total coalition partition in G. We study total coalitions in claw-free cubic graphs with certain structural properties, namely, graphs containing double-bonded triangle-units, that is, two vertex disjoint triangles joined by two edges.