List rainbow connection number of graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910870490054656 |
|---|---|
| author | Tang, Rongxia Liu, Henry Shi, Yueping Wang, Chenming |
| author_facet | Tang, Rongxia Liu, Henry Shi, Yueping Wang, Chenming |
| contents | An edge-coloured path is rainbow if all of its edges have distinct colours. Let $G$ be a connected graph. The rainbow connection number of $G$, denoted by $rc(G)$, is the minimum number of colours in an edge-colouring of $G$ such that, any two vertices are connected by a rainbow path. The strong rainbow connection number of $G$, denoted by $src(G)$, is the minimum number of colours in an edge-colouring of $G$ such that, any two vertices are connected by a rainbow geodesic (i.e., a path of shortest length). These two notions of connectivity of graphs were introduced by Chartrand, Johns, McKeon and Zhang in 2008. In this paper, we introduce the list rainbow connection number $rc^\ell(G)$, and the list strong rainbow connection number $src^\ell(G)$. These two parameters are the versions of $rc(G)$ and $src(G)$ that involve list edge-colourings. Among our results, we will determine the list rainbow connection number and list strong rainbow connection number of some specific graphs. We will also characterise all pairs of positive integers $a$ and $b$ such that, there exists a connected graph $G$ with $src(G)=a$ and $src^\ell(G)=b$, and similarly for the pair $rc^\ell$ and $src^\ell$. Finally, we propose the question of whether or not we have $rc(G)=rc^\ell(G)$, for all connected graphs $G$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_08964 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | List rainbow connection number of graphs Tang, Rongxia Liu, Henry Shi, Yueping Wang, Chenming Combinatorics 05C15 An edge-coloured path is rainbow if all of its edges have distinct colours. Let $G$ be a connected graph. The rainbow connection number of $G$, denoted by $rc(G)$, is the minimum number of colours in an edge-colouring of $G$ such that, any two vertices are connected by a rainbow path. The strong rainbow connection number of $G$, denoted by $src(G)$, is the minimum number of colours in an edge-colouring of $G$ such that, any two vertices are connected by a rainbow geodesic (i.e., a path of shortest length). These two notions of connectivity of graphs were introduced by Chartrand, Johns, McKeon and Zhang in 2008. In this paper, we introduce the list rainbow connection number $rc^\ell(G)$, and the list strong rainbow connection number $src^\ell(G)$. These two parameters are the versions of $rc(G)$ and $src(G)$ that involve list edge-colourings. Among our results, we will determine the list rainbow connection number and list strong rainbow connection number of some specific graphs. We will also characterise all pairs of positive integers $a$ and $b$ such that, there exists a connected graph $G$ with $src(G)=a$ and $src^\ell(G)=b$, and similarly for the pair $rc^\ell$ and $src^\ell$. Finally, we propose the question of whether or not we have $rc(G)=rc^\ell(G)$, for all connected graphs $G$. |
| title | List rainbow connection number of graphs |
| topic | Combinatorics 05C15 |
| url | https://arxiv.org/abs/2503.08964 |