Temat: strong rainbow connection - Katalog OPAC zbiorów

Skocz do pozycji: 1.

Tytuł:: On the rainbow connection of Cartesian products and their subgraphs
Autorzy:: Klavžar, Sandi
Mekiš, Gašper
Powiązania:: https://bibliotekanauki.pl/articles/743307.pdf
Data publikacji:: 2012
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: rainbow connection
strong rainbow connection
Cartesian product of graphs
isometric subgraph
hypercube
Opis:: 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 by the rainbow connection number of the hypercube. Isometric subgraphs of hypercubes with the rainbow connection number as small as possible compared to the rainbow connection of the hypercube are constructed. The concept of c-strong rainbow connected coloring is introduced. In particular, it is proved that the so-called Θ-coloring of an isometric subgraph of a hypercube is its unique optimal c-strong rainbow connected coloring.
Źródło:: Discussiones Mathematicae Graph Theory; 2012, 32, 4; 783-793
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Zmień widok

na półce

Skocz do pozycji: 2.

Tytuł:: On Proper (Strong) Rainbow Connection of Graphs
Autorzy:: Jiang, Hui
Li, Wenjing
Li, Xueliang
Magnant, Colton
Powiązania:: https://bibliotekanauki.pl/articles/32083886.pdf
Data publikacji:: 2021-05-01
Wydawca:: Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
Tematy:: proper (strong) rainbow connection number
Cartesian product
chromatic index
Opis:: A path in an edge-colored graph $G$ is called a rainbow path if no two edges on the path have the same color. The graph $G$ is called rainbow connected if between every pair of distinct vertices of $G$, there is a rainbow path. Recently, Johnson et al. considered this concept with the additional requirement that the coloring of $G$ is proper. The proper rainbow connection number of $G$, denoted by $prc(G)$, is the minimum number of colors needed to properly color the edges of $G$ so that $G$ is rainbow connected. Similarly, the proper strong rainbow connection number of $G$, denoted by $psrc(G)$, is the minimum number of colors needed to properly color the edges of $G$ such that for any two distinct vertices of $G$, there is a rainbow geodesic (shortest path) connecting them. In this paper, we characterize those graphs with proper rainbow connection numbers equal to the size or within 1 of the size. Moreover, we completely solve a question proposed by Johnson et al. by proving that if $G = K_{p1} \Box \dots \Box K_{pn}$, where $n≥ 1$, and $p_1, . . ., p_n>1$ are integers, then $prc(G) = psrc(G) = χ^′(G)$, where $χ^′(G)$ denotes the chromatic index of $G$. Finally, we investigate some suffcient conditions for a graph $G$ to satisfy $prc(G) = rc(G)$, and make some slightly positive progress by using a relation between $rc(G)$ and the girth of the graph.
Źródło:: Discussiones Mathematicae Graph Theory; 2021, 41, 2; 469-479
2083-5892
Pojawia się w:: Discussiones Mathematicae Graph Theory
Dostawca treści:: Biblioteka Nauki

Artykuł

Zmień widok

na półce

Informacja

Wyszukujesz frazę "strong rainbow connection" wg kryterium: Temat

Źródło danych

Dostawca treści

Kolekcja

Rok wydania

Wydawca

Temat

Autor

Typ dokumentu

Język