| Title: | On the rainbow connection of Cartesian products and their subgraphs |
|---|
| Authors: | ID Klavžar, Sandi (Author)
ID Mekiš, Gašper (Author) |
|---|
| Files: |  Discussiones_Mathematicae_Graph_Theory_2012_Klavzar,_Mekis_On_the_rainbow_connection_of_Cartesian_products_and_their_subgraphs.pdf (125,60 KB)
MD5: 08E030D2D9C851DDED1D3C0708735260
 http://www.discuss.wmie.uz.zgora.pl/gt/index.php?doi=10.7151/dmgt.1644
|
|---|
| Language: | English |
|---|
| Work type: | Scientific work |
|---|
| Typology: | 1.01 - Original Scientific Article |
|---|
| Organization: | FNM - Faculty of Natural Sciences and Mathematics
|
|---|
| Abstract: | Rainbow connection number of Cartesian products and their subgraphs are considered. Previously known bounds are compared and non-existence of such bounds for subgraphs of products are discussed. It is shown that the rainbow connection number of an isometric subgraph of a hypercube is bounded above with the rainbow connection number of the hypercube. Isometric subgraphs of hypercubes with the rainbow connection number smaller as much as possible than the rainbow connection of the hypercube are constructed. The concept of c-strong rainbow coloring is introduced. In particular it is proved that the so-called ▫$\Theta$▫-coloring of an isometric subgraph of a hypercube is its unique optimal c-strong rainbow coloring. |
|---|
| Keywords: | graph theory, rainbow connection, strong rainbow connection, Cartesian product of graphs, isometric subgraph, hypercube |
|---|
| Publication status: | Published |
|---|
| Publication version: | Version of Record |
|---|
| Submitted for review: | 08.06.2011 |
|---|
| Article acceptance date: | 06.02.2012 |
|---|
| Publisher: | University of Zielona Góra |
|---|
| Year of publishing: | 2012 |
|---|
| Number of pages: | str. 783-793 |
|---|
| Numbering: | Letn. 32, št. 4 |
|---|
| PID: | 20.500.12556/DKUM-65350  |
|---|
| ISSN: | 1234-3099 |
|---|
| UDC: | 519.17 |
|---|
| ISSN on article: | 1234-3099 |
|---|
| COBISS.SI-ID: | 16417369 |
|---|
| NUK URN: | URN:SI:UM:DK:5HDKVZY4 |
|---|
| Publication date in DKUM: | 31.03.2017 |
|---|
| Views: | 1365 |
|---|
| Downloads: | 510 |
|---|
| Metadata: |    |
|---|
| Categories: | Misc.
|
|---|
|
:
|
Copy citation |
|---|
| | | | Average score: | (0 votes) |
|---|
| Your score: | Voting is allowed only for logged in users. |
|---|
| Share: |  |
|---|
Hover the mouse pointer over a document title to show the abstract or click
on the title to get all document metadata. |
