Rainbow connection number of generalized composition
Let be a connected graph with . The rainbow connection number is the smallest for which there is a map such that any two vertices can be connected by a path whose edge colors are all distinct. The generalized composition is obtained by replacing each with the graph . We prove if each has at least ve...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Taylor & Francis Group
2020-01-01
|
| Series: | AKCE International Journal of Graphs and Combinatorics |
| Subjects: | |
| Online Access: | http://dx.doi.org/10.1016/j.akcej.2018.10.001 |
| _version_ | 1818849749255585792 |
|---|---|
| author | Fendy Septyanto Kiki Ariyanti Sugeng |
| author_facet | Fendy Septyanto Kiki Ariyanti Sugeng |
| author_sort | Fendy Septyanto |
| collection | DOAJ |
| description | Let be a connected graph with . The rainbow connection number is the smallest for which there is a map such that any two vertices can be connected by a path whose edge colors are all distinct. The generalized composition is obtained by replacing each with the graph . We prove if each has at least vertices, improving known upper bounds of Basavaraju et al. and Gologranc et al. (2014). We prove the same result when but with some additional conditions. When , we show that the largest possible value of is related to whether every vertex of is contained in a triangle or not. |
| first_indexed | 2024-12-19T06:38:11Z |
| format | Article |
| id | doaj.art-49c86d1a268e4f6faec9f95804333b75 |
| institution | Directory Open Access Journal |
| issn | 0972-8600 2543-3474 |
| language | English |
| last_indexed | 2024-12-19T06:38:11Z |
| publishDate | 2020-01-01 |
| publisher | Taylor & Francis Group |
| record_format | Article |
| series | AKCE International Journal of Graphs and Combinatorics |
| spelling | doaj.art-49c86d1a268e4f6faec9f95804333b752022-12-21T20:32:11ZengTaylor & Francis GroupAKCE International Journal of Graphs and Combinatorics0972-86002543-34742020-01-0117136737210.1016/j.akcej.2018.10.0011760556Rainbow connection number of generalized compositionFendy Septyanto0Kiki Ariyanti Sugeng1Department of Mathematics and Natural Sciences, Universitas IndonesiaDepartment of Mathematics and Natural Sciences, Universitas IndonesiaLet be a connected graph with . The rainbow connection number is the smallest for which there is a map such that any two vertices can be connected by a path whose edge colors are all distinct. The generalized composition is obtained by replacing each with the graph . We prove if each has at least vertices, improving known upper bounds of Basavaraju et al. and Gologranc et al. (2014). We prove the same result when but with some additional conditions. When , we show that the largest possible value of is related to whether every vertex of is contained in a triangle or not.http://dx.doi.org/10.1016/j.akcej.2018.10.001compositionlexicographic productrainbow connection |
| spellingShingle | Fendy Septyanto Kiki Ariyanti Sugeng Rainbow connection number of generalized composition AKCE International Journal of Graphs and Combinatorics composition lexicographic product rainbow connection |
| title | Rainbow connection number of generalized composition |
| title_full | Rainbow connection number of generalized composition |
| title_fullStr | Rainbow connection number of generalized composition |
| title_full_unstemmed | Rainbow connection number of generalized composition |
| title_short | Rainbow connection number of generalized composition |
| title_sort | rainbow connection number of generalized composition |
| topic | composition lexicographic product rainbow connection |
| url | http://dx.doi.org/10.1016/j.akcej.2018.10.001 |
| work_keys_str_mv | AT fendyseptyanto rainbowconnectionnumberofgeneralizedcomposition AT kikiariyantisugeng rainbowconnectionnumberofgeneralizedcomposition |