Secure domination in $P_5$-free graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913941849899008 |
|---|---|
| author | Gupta, Uttam K. Henning, Michael A. Maniya, Paras Vinubhai Pradhan, Dinabandhu |
| author_facet | Gupta, Uttam K. Henning, Michael A. Maniya, Paras Vinubhai Pradhan, Dinabandhu |
| contents | A dominating set of a graph $G$ is a set $S \subseteq V(G)$ such that every vertex in $V(G) \setminus S$ has a neighbor in $S$, where two vertices are neighbors if they are adjacent. A secure dominating set of $G$ is a dominating set $S$ of $G$ with the additional property that for every vertex $v \in V(G) \setminus S$, there exists a neighbor $u$ of $v$ in $S$ such that $(S \setminus \{u\}) \cup \{v\}$ is a dominating set of $G$. The secure domination number of $G$, denoted by $γ_s(G)$, is the minimum cardinality of a secure dominating set of $G$. We prove that if $G$ is a $P_5$-free graph, then $γ_s(G) \le \frac{3}{2}α(G)$, where $α(G)$ denotes the independence number of $G$. We further show that if $G$ is a connected $(P_5, H)$-free graph for some $H \in \{ P_3 \cup P_1, K_2 \cup 2K_1, ~\text{paw},~ C_4\}$, then $γ_s(G)\le \max\{3,α(G)\}$. We also show that if $G$ is a $(P_3 \cup P_2)$-free graph, then $γ_s(G)\le α(G)+1$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_08088 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Secure domination in $P_5$-free graphs Gupta, Uttam K. Henning, Michael A. Maniya, Paras Vinubhai Pradhan, Dinabandhu Combinatorics Discrete Mathematics A dominating set of a graph $G$ is a set $S \subseteq V(G)$ such that every vertex in $V(G) \setminus S$ has a neighbor in $S$, where two vertices are neighbors if they are adjacent. A secure dominating set of $G$ is a dominating set $S$ of $G$ with the additional property that for every vertex $v \in V(G) \setminus S$, there exists a neighbor $u$ of $v$ in $S$ such that $(S \setminus \{u\}) \cup \{v\}$ is a dominating set of $G$. The secure domination number of $G$, denoted by $γ_s(G)$, is the minimum cardinality of a secure dominating set of $G$. We prove that if $G$ is a $P_5$-free graph, then $γ_s(G) \le \frac{3}{2}α(G)$, where $α(G)$ denotes the independence number of $G$. We further show that if $G$ is a connected $(P_5, H)$-free graph for some $H \in \{ P_3 \cup P_1, K_2 \cup 2K_1, ~\text{paw},~ C_4\}$, then $γ_s(G)\le \max\{3,α(G)\}$. We also show that if $G$ is a $(P_3 \cup P_2)$-free graph, then $γ_s(G)\le α(G)+1$. |
| title | Secure domination in $P_5$-free graphs |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2503.08088 |