The strong 3-rainbow index of edge-comb product of a path and a connected graph
<span>Let </span><span class="math inline"><em>G</em></span><span> be a connected and edge-colored graph of order </span><span class="math inline"><em>n</em></span><span>, where adjacent edges may be co...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Indonesian Combinatorial Society (InaCombS); Graph Theory and Applications (GTA) Research Centre; University of Newcastle, Australia; Institut Teknologi Bandung (ITB), Indonesia
2022-03-01
|
| Series: | Electronic Journal of Graph Theory and Applications |
| Subjects: | |
| Online Access: | https://www.ejgta.org/index.php/ejgta/article/view/1201 |
| _version_ | 1811250748049063936 |
|---|---|
| author | Zata Yumni Awanis A.N.M. Salman Suhadi Wido Saputro |
| author_facet | Zata Yumni Awanis A.N.M. Salman Suhadi Wido Saputro |
| author_sort | Zata Yumni Awanis |
| collection | DOAJ |
| description | <span>Let </span><span class="math inline"><em>G</em></span><span> be a connected and edge-colored graph of order </span><span class="math inline"><em>n</em></span><span>, where adjacent edges may be colored the same. A tree in </span><span class="math inline"><em>G</em></span><span> is a rainbow tree if all of its edges have distinct colors. Let </span><span class="math inline"><em>k</em></span><span> be an integer with </span><span class="math inline">2 ≤ <em>k</em> ≤ <em>n</em></span><span>. The minimum number of colors needed in an edge coloring of </span><span class="math inline"><em>G</em></span><span> such that there exists a rainbow tree connecting </span><span class="math inline"><em>S</em></span><span> with minimum size for every </span><span class="math inline"><em>k</em></span><span>-subset </span><span class="math inline"><em>S</em></span><span> of </span><span class="math inline"><em>V</em>(<em>G</em>)</span><span> is called the strong </span><span class="math inline"><em>k</em></span><span>-rainbow index of </span><span class="math inline"><em>G</em></span><span>, denoted by </span><span class="math inline"><em>s</em><em>r</em><em>x</em><sub><em>k</em></sub>(<em>G</em>)</span><span>. In this paper, we study the </span><span class="math inline"><em>s</em><em>r</em><em>x</em><sub>3</sub></span><span> of edge-comb product of a path and a connected graph, denoted by </span><span class="math inline"><em>P</em><sub><em>n</em></sub><sup><em>o</em></sup>⊳<sub><em>e</em></sub><em>H</em></span><span>. It is clearly that </span><span class="math inline">|<em>E</em>(<em>P</em><sub><em>n</em></sub><sup><em>o</em></sup>⊳<sub><em>e</em></sub><em>H</em>)|</span><span> is the trivial upper bound for </span><span class="math inline"><em>s</em><em>r</em><em>x</em><sub>3</sub>(<em>P</em><sub><em>n</em></sub><sup><em>o</em></sup>⊳<sub><em>e</em></sub><em>H</em>)</span><span>. Therefore, in this paper, we first characterize connected graphs </span><span class="math inline"><em>H</em></span><span> with </span><span class="math inline"><em>s</em><em>r</em><em>x</em><sub>3</sub>(<em>P</em><sub><em>n</em></sub><sup><em>o</em></sup>⊳<sub><em>e</em></sub><em>H</em>)=|<em>E</em>(<em>P</em><sub><em>n</em></sub><sup><em>o</em></sup>⊳<sub><em>e</em></sub><em>H</em>)|</span><span>, then provide a sharp upper bound for </span><span class="math inline"><em>s</em><em>r</em><em>x</em><sub>3</sub>(<em>P</em><sub><em>n</em></sub><sup><em>o</em></sup>⊳<sub><em>e</em></sub><em>H</em>)</span><span> where </span><span class="math inline"><em>s</em><em>r</em><em>x</em><sub>3</sub>(<em>P</em><sub><em>n</em></sub><sup><em>o</em></sup>⊳<sub><em>e</em></sub><em>H</em>)≠|<em>E</em>(<em>P</em><sub><em>n</em></sub><sup><em>o</em></sup>⊳<sub><em>e</em></sub><em>H</em>)|</span><span>. We also provide the exact value of </span><span class="math inline"><em>s</em><em>r</em><em>x</em><sub>3</sub>(<em>P</em><sub><em>n</em></sub><sup><em>o</em></sup>⊳<sub><em>e</em></sub><em>H</em>)</span><span> for some connected graphs </span><span class="math inline"><em>H</em></span><span>.</span> |
| first_indexed | 2024-04-12T16:09:16Z |
| format | Article |
| id | doaj.art-b92ac1f3c3194142a93f604e991f930c |
| institution | Directory Open Access Journal |
| issn | 2338-2287 |
| language | English |
| last_indexed | 2024-04-12T16:09:16Z |
| publishDate | 2022-03-01 |
| publisher | Indonesian Combinatorial Society (InaCombS); Graph Theory and Applications (GTA) Research Centre; University of Newcastle, Australia; Institut Teknologi Bandung (ITB), Indonesia |
| record_format | Article |
| series | Electronic Journal of Graph Theory and Applications |
| spelling | doaj.art-b92ac1f3c3194142a93f604e991f930c2022-12-22T03:25:57ZengIndonesian Combinatorial Society (InaCombS); Graph Theory and Applications (GTA) Research Centre; University of Newcastle, Australia; Institut Teknologi Bandung (ITB), IndonesiaElectronic Journal of Graph Theory and Applications2338-22872022-03-01101335010.5614/ejgta.2022.10.1.3244The strong 3-rainbow index of edge-comb product of a path and a connected graphZata Yumni Awanis0A.N.M. Salman1Suhadi Wido Saputro2Institut Teknologi BandungInstitut Teknologi BandungInstitut Teknologi Bandung<span>Let </span><span class="math inline"><em>G</em></span><span> be a connected and edge-colored graph of order </span><span class="math inline"><em>n</em></span><span>, where adjacent edges may be colored the same. A tree in </span><span class="math inline"><em>G</em></span><span> is a rainbow tree if all of its edges have distinct colors. Let </span><span class="math inline"><em>k</em></span><span> be an integer with </span><span class="math inline">2 ≤ <em>k</em> ≤ <em>n</em></span><span>. The minimum number of colors needed in an edge coloring of </span><span class="math inline"><em>G</em></span><span> such that there exists a rainbow tree connecting </span><span class="math inline"><em>S</em></span><span> with minimum size for every </span><span class="math inline"><em>k</em></span><span>-subset </span><span class="math inline"><em>S</em></span><span> of </span><span class="math inline"><em>V</em>(<em>G</em>)</span><span> is called the strong </span><span class="math inline"><em>k</em></span><span>-rainbow index of </span><span class="math inline"><em>G</em></span><span>, denoted by </span><span class="math inline"><em>s</em><em>r</em><em>x</em><sub><em>k</em></sub>(<em>G</em>)</span><span>. In this paper, we study the </span><span class="math inline"><em>s</em><em>r</em><em>x</em><sub>3</sub></span><span> of edge-comb product of a path and a connected graph, denoted by </span><span class="math inline"><em>P</em><sub><em>n</em></sub><sup><em>o</em></sup>⊳<sub><em>e</em></sub><em>H</em></span><span>. It is clearly that </span><span class="math inline">|<em>E</em>(<em>P</em><sub><em>n</em></sub><sup><em>o</em></sup>⊳<sub><em>e</em></sub><em>H</em>)|</span><span> is the trivial upper bound for </span><span class="math inline"><em>s</em><em>r</em><em>x</em><sub>3</sub>(<em>P</em><sub><em>n</em></sub><sup><em>o</em></sup>⊳<sub><em>e</em></sub><em>H</em>)</span><span>. Therefore, in this paper, we first characterize connected graphs </span><span class="math inline"><em>H</em></span><span> with </span><span class="math inline"><em>s</em><em>r</em><em>x</em><sub>3</sub>(<em>P</em><sub><em>n</em></sub><sup><em>o</em></sup>⊳<sub><em>e</em></sub><em>H</em>)=|<em>E</em>(<em>P</em><sub><em>n</em></sub><sup><em>o</em></sup>⊳<sub><em>e</em></sub><em>H</em>)|</span><span>, then provide a sharp upper bound for </span><span class="math inline"><em>s</em><em>r</em><em>x</em><sub>3</sub>(<em>P</em><sub><em>n</em></sub><sup><em>o</em></sup>⊳<sub><em>e</em></sub><em>H</em>)</span><span> where </span><span class="math inline"><em>s</em><em>r</em><em>x</em><sub>3</sub>(<em>P</em><sub><em>n</em></sub><sup><em>o</em></sup>⊳<sub><em>e</em></sub><em>H</em>)≠|<em>E</em>(<em>P</em><sub><em>n</em></sub><sup><em>o</em></sup>⊳<sub><em>e</em></sub><em>H</em>)|</span><span>. We also provide the exact value of </span><span class="math inline"><em>s</em><em>r</em><em>x</em><sub>3</sub>(<em>P</em><sub><em>n</em></sub><sup><em>o</em></sup>⊳<sub><em>e</em></sub><em>H</em>)</span><span> for some connected graphs </span><span class="math inline"><em>H</em></span><span>.</span>https://www.ejgta.org/index.php/ejgta/article/view/1201edge-comb productrainbow coloringrainbow steiner treestrong 3-rainbow index |
| spellingShingle | Zata Yumni Awanis A.N.M. Salman Suhadi Wido Saputro The strong 3-rainbow index of edge-comb product of a path and a connected graph Electronic Journal of Graph Theory and Applications edge-comb product rainbow coloring rainbow steiner tree strong 3-rainbow index |
| title | The strong 3-rainbow index of edge-comb product of a path and a connected graph |
| title_full | The strong 3-rainbow index of edge-comb product of a path and a connected graph |
| title_fullStr | The strong 3-rainbow index of edge-comb product of a path and a connected graph |
| title_full_unstemmed | The strong 3-rainbow index of edge-comb product of a path and a connected graph |
| title_short | The strong 3-rainbow index of edge-comb product of a path and a connected graph |
| title_sort | strong 3 rainbow index of edge comb product of a path and a connected graph |
| topic | edge-comb product rainbow coloring rainbow steiner tree strong 3-rainbow index |
| url | https://www.ejgta.org/index.php/ejgta/article/view/1201 |
| work_keys_str_mv | AT zatayumniawanis thestrong3rainbowindexofedgecombproductofapathandaconnectedgraph AT anmsalman thestrong3rainbowindexofedgecombproductofapathandaconnectedgraph AT suhadiwidosaputro thestrong3rainbowindexofedgecombproductofapathandaconnectedgraph AT zatayumniawanis strong3rainbowindexofedgecombproductofapathandaconnectedgraph AT anmsalman strong3rainbowindexofedgecombproductofapathandaconnectedgraph AT suhadiwidosaputro strong3rainbowindexofedgecombproductofapathandaconnectedgraph |