Rainbow Connection Number of Dense Graphs
An edge-colored graph G is rainbow connected, if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of a connected graph G, denoted rc(G), is the smallest number of colors that are needed in order to make G rainbow connected. In this paper we sho...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2013-07-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.1692 |
| _version_ | 1797704413447454720 |
|---|---|
| author | Li Xueliang Liu Mengmeng Schiermeyer Ingo |
| author_facet | Li Xueliang Liu Mengmeng Schiermeyer Ingo |
| author_sort | Li Xueliang |
| collection | DOAJ |
| description | An edge-colored graph G is rainbow connected, if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of a connected graph G, denoted rc(G), is the smallest number of colors that are needed in order to make G rainbow connected. In this paper we show that rc(G) ≤ 3 if |E(G)| ≥ + 2, and rc(G) ≤ 4 if |E(G)| ≥ + 3. These bounds are sharp. |
| first_indexed | 2024-03-12T05:20:04Z |
| format | Article |
| id | doaj.art-b45afe9911d9421e84a349167899aa11 |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T05:20:04Z |
| publishDate | 2013-07-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-b45afe9911d9421e84a349167899aa112023-09-03T07:47:22ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922013-07-0133360361110.7151/dmgt.1692Rainbow Connection Number of Dense GraphsLi Xueliang0Liu Mengmeng1Schiermeyer Ingo2Center for Combinatorics and LPMC-TJKLC Nankai University Tianjin 300071, ChinaCenter for Combinatorics and LPMC-TJKLC Nankai University Tianjin 300071, ChinaInstitut für Diskrete Mathematik und Algebra echnische Universität Bergakademie Freiberg 09596 Freiberg, GermanyAn edge-colored graph G is rainbow connected, if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of a connected graph G, denoted rc(G), is the smallest number of colors that are needed in order to make G rainbow connected. In this paper we show that rc(G) ≤ 3 if |E(G)| ≥ + 2, and rc(G) ≤ 4 if |E(G)| ≥ + 3. These bounds are sharp.https://doi.org/10.7151/dmgt.1692edge-colored graphrainbow coloringrainbow connection number |
| spellingShingle | Li Xueliang Liu Mengmeng Schiermeyer Ingo Rainbow Connection Number of Dense Graphs Discussiones Mathematicae Graph Theory edge-colored graph rainbow coloring rainbow connection number |
| title | Rainbow Connection Number of Dense Graphs |
| title_full | Rainbow Connection Number of Dense Graphs |
| title_fullStr | Rainbow Connection Number of Dense Graphs |
| title_full_unstemmed | Rainbow Connection Number of Dense Graphs |
| title_short | Rainbow Connection Number of Dense Graphs |
| title_sort | rainbow connection number of dense graphs |
| topic | edge-colored graph rainbow coloring rainbow connection number |
| url | https://doi.org/10.7151/dmgt.1692 |
| work_keys_str_mv | AT lixueliang rainbowconnectionnumberofdensegraphs AT liumengmeng rainbowconnectionnumberofdensegraphs AT schiermeyeringo rainbowconnectionnumberofdensegraphs |