For a graph G, the vertex partition <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$\sigma =\{V_1, V_2,\cdots , V_k\}$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>σ</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> is a connecting coalition partition if each <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$V_i \in \sigma , |V_i| > 1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>V</mi> <mi>i</mi> </msub> <mo>∈</mo> <mi>σ</mi> <mo>,</mo> <mrow> <mo stretchy="false">|</mo> <msub> <mi>V</mi> <mi>i</mi> </msub> <mo stretchy="false">|</mo> </mrow> <mo>></mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>, induces a disconnected graph but a union with some <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$V_j \in \sigma , |V_j| > 1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>V</mi> <mi>j</mi> </msub> <mo>∈</mo> <mi>σ</mi> <mo>,</mo> <mrow> <mo stretchy="false">|</mo> <msub> <mi>V</mi> <mi>j</mi> </msub> <mo stretchy="false">|</mo> </mrow> <mo>></mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>, <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$V_i \cup V_j$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>V</mi> <mi>i</mi> </msub> <mo>∪</mo> <msub> <mi>V</mi> <mi>j</mi> </msub> </mrow> </math></EquationSource> </InlineEquation> induces a connected graph; otherwise <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$V_i \in \sigma $</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>V</mi> <mi>i</mi> </msub> <mo>∈</mo> <mi>σ</mi> </mrow> </math></EquationSource> </InlineEquation> is a singleton set containing a full vertex of G in <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$\sigma $</EquationSource> <EquationSource Format="MATHML"><math> <mi>σ</mi> </math></EquationSource> </InlineEquation>. Among all possible connecting coalition partitions for a graph G, the cardinality of the partition <InlineEquation ID="IEq7"> <EquationSource Format="TEX">$\sigma $</EquationSource> <EquationSource Format="MATHML"><math> <mi>σ</mi> </math></EquationSource> </InlineEquation> having the maximum value is the connecting coalition number, <InlineEquation ID="IEq8"> <EquationSource Format="TEX">$\zeta (G)$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>ζ</mi> <mo stretchy="false">(</mo> <mi>G</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>. In this article, we determine the connecting coalition number for the Cartesian product of graphs. For graphs <InlineEquation ID="IEq9"> <EquationSource Format="TEX">$G_\mathcal {F}$</EquationSource> <EquationSource Format="MATHML"><math> <msub> <mi>G</mi> <mi mathvariant="script">F</mi> </msub> </math></EquationSource> </InlineEquation>, that do not attain a connecting coalition partition, the connecting coalition partition for <InlineEquation ID="IEq10"> <EquationSource Format="TEX">$G_\mathcal {F} \square G$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <msub> <mi>G</mi> <mi mathvariant="script">F</mi> </msub> <mo>□</mo> <mi>G</mi> </mrow> </math></EquationSource> </InlineEquation>, with a given graph G, is determined. The existence of the connecting coalition partition for the Cartesian product of any two non-trivial graphs is proved.

Connecting Coalition Partitions in the Cartesian Product of Graphs

期刊论文
发表日期：

2026年7月28日

查看全文

Merin Cherian,
Tabitha Agnes Mangam

摘要

For a graph G, the vertex partition $\sigma =\{V_1, V_2,\cdots , V_k\}$ $σ = {V_{1}, V_{2}, \dots, V_{k}}$ is a connecting coalition partition if each $V_i \in \sigma , |V_i| > 1$ $V_{i} \in σ, | V_{i} | > 1$ , induces a disconnected graph but a union with some $V_j \in \sigma , |V_j| > 1$ $V_{j} \in σ, | V_{j} | > 1$ , $V_i \cup V_j$ $V_{i} \cup V_{j}$ induces a connected graph; otherwise $V_i \in \sigma $ $V_{i} \in σ$ is a singleton set containing a full vertex of G in $\sigma $ $σ$ . Among all possible connecting coalition partitions for a graph G, the cardinality of the partition $\sigma $ $σ$ having the maximum value is the connecting coalition number, $\zeta (G)$ $ζ (G)$ . In this article, we determine the connecting coalition number for the Cartesian product of graphs. For graphs $G_\mathcal {F}$ $G_{F}$ , that do not attain a connecting coalition partition, the connecting coalition partition for $G_\mathcal {F} \square G$ $G_{F} □ G$ , with a given graph G, is determined. The existence of the connecting coalition partition for the Cartesian product of any two non-trivial graphs is proved.