Perfect coalition in graphs
| Autor: | Mojdeh, Doost Ali, Samadzadeh, Mohammad Reza |
|---|---|
| Rok vydání: | 2024 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | \noindent A perfect dominating set in a graph $G=(V,E)$ is a subset $S \subseteq V$ such that each vertex in $V \setminus S$ has exactly one neighbor in $S$. A perfect coalition in $G$ consists of two disjoint sets of vertices $V_i$ and $V_j$ such that i) neither $V_i$ nor $V_j$ is a dominating set, ii) each vertex in $V(G) \setminus V_i$ has at most one neighbor in $V_i$ and each vertex in $V(G) \setminus V_j$ has at most one neighbor in $V_j$, and iii) $V_i \cup V_j$ is a perfect dominating set. A perfect coalition partition (abbreviated $prc$-partition) in a graph $G$ is a vertex partition $\pi= \lbrace V_1,V_2,\dots ,V_k \rbrace$ such that for each set $V_i$ of $\pi$ either $V_i$ is a singleton dominating set, or there exists a set $V_j \in \pi$ that forms a perfect coalition with $V_i$. In this paper, we initiate the study of perfect coalition partitions in graphs. We obtain a bound on the number of perfect coalitions involving each member of a perfect coalition partition, in terms of maximum degree. The perfect coalition of some special graphs are investigated. The graph $G$ with $\delta(G)=1$, the triangle-free graphs $G$ with prefect coalition number of order of $G$ and the trees $T$ with prefect coalition number in $\{n,n-1,n-2\}$ where $n=|V(T)|$ are characterized. Comment: 18 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|