Rainbow cycles through specified vertices
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917679235858432 |
|---|---|
| author | Liu, Henry |
| author_facet | Liu, Henry |
| contents | An edge-coloured cycle is rainbow if the edges have distinct colours. Let $G$ be a graph such that any $k$ vertices lie in a cycle of $G$. The $k$-rainbow cycle index of $G$, denoted by $crx_k(G)$, is the minimum number of colours required to colour the edges of $G$ such that, for every set $S$ of $k$ vertices in $G$, there exists a rainbow cycle in $G$ containing $S$. In this paper, we will first prove some results about the parameter $crx_k(G)$ for general graphs $G$. One of the results is a classification of all graphs $G$ such that $crx_k(G)=e(G)$, for $k=1,2$. We will also determine $crx_k(G)$ for some specific graphs $G$, including wheels, complete graphs, complete bipartite and multipartite graphs, and discrete cubes. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_19717 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Rainbow cycles through specified vertices Liu, Henry Combinatorics 05C15, 05C38 An edge-coloured cycle is rainbow if the edges have distinct colours. Let $G$ be a graph such that any $k$ vertices lie in a cycle of $G$. The $k$-rainbow cycle index of $G$, denoted by $crx_k(G)$, is the minimum number of colours required to colour the edges of $G$ such that, for every set $S$ of $k$ vertices in $G$, there exists a rainbow cycle in $G$ containing $S$. In this paper, we will first prove some results about the parameter $crx_k(G)$ for general graphs $G$. One of the results is a classification of all graphs $G$ such that $crx_k(G)=e(G)$, for $k=1,2$. We will also determine $crx_k(G)$ for some specific graphs $G$, including wheels, complete graphs, complete bipartite and multipartite graphs, and discrete cubes. |
| title | Rainbow cycles through specified vertices |
| topic | Combinatorics 05C15, 05C38 |
| url | https://arxiv.org/abs/2405.19717 |