- Tytuł:
- Rainbow Disconnection in Graphs
- Autorzy:
-
Chartrand, Gary
Devereaux, Stephen
Haynes, Teresa W.
Hedetniemi, Stephen T.
Zhang, Ping - Powiązania:
- https://bibliotekanauki.pl/articles/31342243.pdf
- Data publikacji:
- 2018-11-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
edge coloring
rainbow connection
rainbow disconnection - Opis:
- Let G be a nontrivial connected, edge-colored graph. An edge-cut R of G is called a rainbow cut if no two edges in R are colored the same. An edge-coloring of G is a rainbow disconnection coloring if for every two distinct vertices u and v of G, there exists a rainbow cut in G, where u and v belong to different components of G − R. We introduce and study the rainbow disconnection number rd(G) of G, which is defined as the minimum number of colors required of a rainbow disconnection coloring of G. It is shown that the rainbow disconnection number of a nontrivial connected graph G equals the maximum rainbow disconnection number among the blocks of G. It is also shown that for a nontrivial connected graph G of order n, rd(G) = n−1 if and only if G contains at least two vertices of degree n − 1. The rainbow disconnection numbers of all grids Pm □ Pn are determined. Furthermore, it is shown for integers k and n with 1 ≤ k ≤ n − 1 that the minimum size of a connected graph of order n having rainbow disconnection number k is n + k − 2. Other results and a conjecture are also presented.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2018, 38, 4; 1007-1021
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł