Ramsey-type results on parameters related to domination
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911906863775744 |
|---|---|
| author | Sun, Jin Hou, Xinmin |
| author_facet | Sun, Jin Hou, Xinmin |
| contents | The following inequality chain $$ ir(G)\le γ(G)\le i(G)\le α(G) \le Γ(G) \le I\!R(G)$$ is known as a domination chain, where $ir(G), γ(G), i(G), α(G), Γ(G)$, and $I\!R(G)$ are the lower irredundance number, the domination number, the independence domination number, the independence number, the upper domination number and the upper irredundance number of $G$, respectively. The Ramsey-type problem seeks to characterize the family $\mathcal H$ of graphs such that every $\mathcal H$-free graph $G$ has a bounded parameter $μ$. The classical Ramsey's theorem states that every $\{K_n, E_n\}$-free graph has a bounded number of vertices. Furuya (Discrete Math.Theor 2018) characterized $\mathcal H$ such that every connected $\mathcal H$-free graph $G$ has a bounded domination number. The characterization of the graph family $\mathcal H$ for which every connected $\mathcal H$-free graph $G$ has a bounded independence number was due to Choi, Furuya, Kim, Park~(Discrete math. 2020) and Chiba, Furuya (Electron. J. Combin., 2022). In this paper, we further characterize $\mathcal H$ such that every connected $\mathcal H$-free graph $G$ has bounded $μ(G)$ for $μ$ belonging to the set $\{ir(G), i(G), Γ(G), \text{IR}(G)\}$. This completes the characterization of $\mathcal H$ for which every connected $\mathcal H$-free graph $G$ has bounded $μ(G)$ for $μ(G)$ along the domination chain. Additionally, we characterize $\mathcal H$ such that every connected $\mathcal H$-free graph $G$ has bounded $μ(G)$ for $μ$ related to the domination number. Specifically, we consider the parameters $O\!I\!R(G)$, $I\!S(G)$, or $I\!R\!S(G)\}$, where $O\!I\!R(G)$, $I\!S(G)$, and $I\!R\!S(G)$ are the open irredundance number, the independence saturation number, and the irredundance saturation number of graph $G$, respectively. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_07667 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Ramsey-type results on parameters related to domination Sun, Jin Hou, Xinmin Combinatorics The following inequality chain $$ ir(G)\le γ(G)\le i(G)\le α(G) \le Γ(G) \le I\!R(G)$$ is known as a domination chain, where $ir(G), γ(G), i(G), α(G), Γ(G)$, and $I\!R(G)$ are the lower irredundance number, the domination number, the independence domination number, the independence number, the upper domination number and the upper irredundance number of $G$, respectively. The Ramsey-type problem seeks to characterize the family $\mathcal H$ of graphs such that every $\mathcal H$-free graph $G$ has a bounded parameter $μ$. The classical Ramsey's theorem states that every $\{K_n, E_n\}$-free graph has a bounded number of vertices. Furuya (Discrete Math.Theor 2018) characterized $\mathcal H$ such that every connected $\mathcal H$-free graph $G$ has a bounded domination number. The characterization of the graph family $\mathcal H$ for which every connected $\mathcal H$-free graph $G$ has a bounded independence number was due to Choi, Furuya, Kim, Park~(Discrete math. 2020) and Chiba, Furuya (Electron. J. Combin., 2022). In this paper, we further characterize $\mathcal H$ such that every connected $\mathcal H$-free graph $G$ has bounded $μ(G)$ for $μ$ belonging to the set $\{ir(G), i(G), Γ(G), \text{IR}(G)\}$. This completes the characterization of $\mathcal H$ for which every connected $\mathcal H$-free graph $G$ has bounded $μ(G)$ for $μ(G)$ along the domination chain. Additionally, we characterize $\mathcal H$ such that every connected $\mathcal H$-free graph $G$ has bounded $μ(G)$ for $μ$ related to the domination number. Specifically, we consider the parameters $O\!I\!R(G)$, $I\!S(G)$, or $I\!R\!S(G)\}$, where $O\!I\!R(G)$, $I\!S(G)$, and $I\!R\!S(G)$ are the open irredundance number, the independence saturation number, and the irredundance saturation number of graph $G$, respectively. |
| title | Ramsey-type results on parameters related to domination |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2308.07667 |