Distance-Local Rainbow Connection Number
Under an edge coloring (not necessarily proper), a rainbow path is a path whose edge colors are all distinct. The d-local rainbow connection number lrcd(G) (respectively, d-local strong rainbow connection number lsrcd(G)) is the smallest number of colors needed to color the edges of G such that any...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2022-11-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.2325 |
| _version_ | 1797760627015417856 |
|---|---|
| author | Septyanto Fendy Sugeng Kiki A. |
| author_facet | Septyanto Fendy Sugeng Kiki A. |
| author_sort | Septyanto Fendy |
| collection | DOAJ |
| description | Under an edge coloring (not necessarily proper), a rainbow path is a path whose edge colors are all distinct. The d-local rainbow connection number lrcd(G) (respectively, d-local strong rainbow connection number lsrcd(G)) is the smallest number of colors needed to color the edges of G such that any two vertices with distance at most d can be connected by a rainbow path (respectively, rainbow geodesic). This generalizes rainbow connection numbers, which are the special case d = diam(G). We discuss some bounds and exact values. Moreover, we also characterize all triples of positive integers d, a, b such that there is a connected graph G with lrcd(G) = a and lsrcd(G) = b. |
| first_indexed | 2024-03-12T19:01:16Z |
| format | Article |
| id | doaj.art-6b74c7d662474068a4da86a6116113ce |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T19:01:16Z |
| publishDate | 2022-11-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-6b74c7d662474068a4da86a6116113ce2023-08-02T06:34:51ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922022-11-014241027103910.7151/dmgt.2325Distance-Local Rainbow Connection NumberSeptyanto Fendy0Sugeng Kiki A.1Faculty of Mathematics and Natural Sciences, Department of Mathematics, Universitas Indonesia, Depok 16424, IndonesiaFaculty of Mathematics and Natural Sciences, Department of Mathematics, Universitas Indonesia, Depok 16424, IndonesiaUnder an edge coloring (not necessarily proper), a rainbow path is a path whose edge colors are all distinct. The d-local rainbow connection number lrcd(G) (respectively, d-local strong rainbow connection number lsrcd(G)) is the smallest number of colors needed to color the edges of G such that any two vertices with distance at most d can be connected by a rainbow path (respectively, rainbow geodesic). This generalizes rainbow connection numbers, which are the special case d = diam(G). We discuss some bounds and exact values. Moreover, we also characterize all triples of positive integers d, a, b such that there is a connected graph G with lrcd(G) = a and lsrcd(G) = b.https://doi.org/10.7151/dmgt.2325rainbow connectionchromatic numberline graph05c1505c3805c40 |
| spellingShingle | Septyanto Fendy Sugeng Kiki A. Distance-Local Rainbow Connection Number Discussiones Mathematicae Graph Theory rainbow connection chromatic number line graph 05c15 05c38 05c40 |
| title | Distance-Local Rainbow Connection Number |
| title_full | Distance-Local Rainbow Connection Number |
| title_fullStr | Distance-Local Rainbow Connection Number |
| title_full_unstemmed | Distance-Local Rainbow Connection Number |
| title_short | Distance-Local Rainbow Connection Number |
| title_sort | distance local rainbow connection number |
| topic | rainbow connection chromatic number line graph 05c15 05c38 05c40 |
| url | https://doi.org/10.7151/dmgt.2325 |
| work_keys_str_mv | AT septyantofendy distancelocalrainbowconnectionnumber AT sugengkikia distancelocalrainbowconnectionnumber |