Přejít k obsahu


Characterizing forbidden pairs for rainbow connection in graphs with minimum degree 2

Citace:
HOLUB, P., RYJÁČEK, Z., SCHIERMEYER, I., VRÁNA, P. Characterizing forbidden pairs for rainbow connection in graphs with minimum degree 2. DISCRETE MATHEMATICS, 2016, roč. 339, č. 2, s. 1058-1068. ISSN: 0012-365X
Druh: ČLÁNEK
Jazyk publikace: eng
Anglický název: Characterizing forbidden pairs for rainbow connection in graphs with minimum degree 2
Rok vydání: 2016
Autoři: RNDr. Přemysl Holub Ph.D. , Prof. RNDr. Zdeněk Ryjáček DrSc. , Ingo Schiermeyer , Mgr. Petr Vrána Ph.D. ,
Abstrakt CZ: Souvislý hranově obarvený graf G je duhově souvislý, jestliže mezi každými dvěma různými uzly grafu G existuje cesta, jejíž hrany mají různé barvy, a číslo duhové souvislosti rc(G) grafu G je nejmenší počet barev, které jsou potřebné, aby G byl duhově souvislý. V článku podáváme úplnou charakterizaci dvojic (X, Y) souvislých grafů, pro které existuje konstanta k taková, že pro každý souvislý graf G bez (X, Y) s minimálním stupněm alespoň 2 platí, že rc(G) je nejvýše diam(G)+k (kde diam(G) je průměr grafu G).
Abstrakt EN: A connected edge-colored graph G is rainbow-connected if any two distinct vertices of G are connected by a path whose edges have pairwise distinct colors; the rainbow connection number rc(G) of G is the minimum number of colors that are needed in order to make G rainbow connected. In this paper, we complete the discussion of pairs (X, Y) of connected graphs for which there is a constant k such that, for every connected (X, Y)-free graph G with minimum degree at least 2, rc(G) is at most diam(G)+k (where diam(G) is the diameter of G), by giving a complete characterization.
Klíčová slova

Zpět

Patička