Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2501.10140 |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910788236607488 |
|---|---|
| author | Valenzuela-Tripodoro, J. C. Mateos-Camacho, M. A. Cera, M. Casablanca, R. M. Álvarez-Ruiz, M. P. |
| author_facet | Valenzuela-Tripodoro, J. C. Mateos-Camacho, M. A. Cera, M. Casablanca, R. M. Álvarez-Ruiz, M. P. |
| contents | Domination in graphs is a widely studied field, where many different definitions have been introduced in the last years to respond to different network requirements. This paper presents a new dominating parameter based on the well-known strong Roman domination model. Given a positive integer $p$, we call a $p$-strong Roman domination function ($p$-StRDF) in a graph $G$ to a function $f:V(G)\rightarrow \{0,1,2, \ldots , \left\lceil \frac{Δ+p}{p} \right\rceil \}$ having the property that if $f(v)=0$, then there is a vertex $u\in N(v)$ such that $f(u) \ge 1+ \left\lceil \frac{ |B_0\cap N(u)|}{p} \right\rceil $, where $B_0$ is the set of vertices with label $0$. The $p$-strong Roman domination number $γ_{StR}^p(G)$ is the minimum weight (sum of labels) of a $p$-StRDF on $G$. We study the NP-completeness of the \emph{$p$-StRD}-problem, we also provide general and tight upper and lower bounds depending on several classical invariants of the graph and, finally, we determine the exact values for some families of graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_10140 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | p-Strong Roman Domination in Graphs Valenzuela-Tripodoro, J. C. Mateos-Camacho, M. A. Cera, M. Casablanca, R. M. Álvarez-Ruiz, M. P. Combinatorics Domination in graphs is a widely studied field, where many different definitions have been introduced in the last years to respond to different network requirements. This paper presents a new dominating parameter based on the well-known strong Roman domination model. Given a positive integer $p$, we call a $p$-strong Roman domination function ($p$-StRDF) in a graph $G$ to a function $f:V(G)\rightarrow \{0,1,2, \ldots , \left\lceil \frac{Δ+p}{p} \right\rceil \}$ having the property that if $f(v)=0$, then there is a vertex $u\in N(v)$ such that $f(u) \ge 1+ \left\lceil \frac{ |B_0\cap N(u)|}{p} \right\rceil $, where $B_0$ is the set of vertices with label $0$. The $p$-strong Roman domination number $γ_{StR}^p(G)$ is the minimum weight (sum of labels) of a $p$-StRDF on $G$. We study the NP-completeness of the \emph{$p$-StRD}-problem, we also provide general and tight upper and lower bounds depending on several classical invariants of the graph and, finally, we determine the exact values for some families of graphs. |
| title | p-Strong Roman Domination in Graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2501.10140 |