On independent coalition in graphs and independent coalition graphs

Alikhani, Saeid (author), Bakhshesh, Davood (author), Golmohammadi, Hamidreza (author), Klavžar, Sandi (author)

An independent coalition in a graph $G$ consists of two disjoint, independent vertex sets $V_1$ and $V_2$, such that neither $V_1$ nor $V_2$ is a dominating set, but the union $V_1\cup V_2$ is an independent dominating set of $G$. An independent coalition partition of $G$ is a partition $\{V_1, \ldots, V_k\}$ of $V(G)$ such that for every $i\in [k]$, either the set $V_i$ consists of a single dominating vertex of $G$, or $V_i$ forms an independent coalition with some other part $V_j$. The independent coalition number $IC(G)$ of $G$ is the maximum order of an independent coalition of $G$. The independent coalition graph ${\rm ICG}(G,\pi)$ of $\pi=\{V_1, \ldots, V_k\}$ (and of $G$) has the vertex set $\{V_1,\ldots, V_k\}$, vertices $V_i$ and $V_j$ being adjacent if $V_i$ and $V_j$ form an independent coalition in $G$. In this paper, a large family of graphs with $IC(G) = 0$ is described and graphs $G$ with $IC(G)\in \{n(G), n(G)-1\}$ characterized. Some properties of ${\rm ICG}(G,\pi)$ are presented. The independent coalition graphs of paths are characterized, and the independent coalition graphs of cycles described.

• Language: English
• Keywords: dominating set, independent set, independent coalition, independent coalition number, independent coalition graphs
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: FMF - Faculty of Mathematics and Physics
• Publication status: Published
• Publication version: Version of Record
• Publication date: 01.01.2025
• Year: 2025
• Number of pages: Str. 533-544
• Numbering: Vol. 45, no. 2
• PID: 20.500.12556/RUL-168412
• UDC: 519.17
• ISSN on article: 1234-3099
• DOI: 10.7151/dmgt.2543
• COBISS.SI-ID: 232324611
• Publication date in RUL: 11.04.2025

Record is a part of a journal

• Title: Discussiones mathematicae : Graph theory
• Shortened title: Discuss. Math., Graph Theory
• Publisher: Technical University Press
• ISSN: 1234-3099
• COBISS.SI-ID: 7487065

Licences

• License: CC BY-NC-ND 4.0, Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
• Link: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Description: The most restrictive Creative Commons license. This only allows people to download and share the work for no commercial gain and for no other purposes.

Secondary language

• Language: Slovenian
• Keywords: dominacijska množica, neodvisna množica, neodvisna koalicija, neodvisnostno koalicijsko število, grafi neodvisnih koalicij