We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
RAINBOW DISCONNECTION IN GRAPHS.
- Authors
CHARTRAND, GARY; DEVEREAUX, STEPHEN; HAYNES, TERESA W.; HEDETNIEMI, STEPHEN T.; PING ZHANG
- Abstract
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.
- Subjects
GRAPH connectivity; GRAPH theory; PATHS &; cycles in graph theory; GRAPH coloring; INTEGERS
- Publication
Discussiones Mathematicae: Graph Theory, 2018, Vol 38, Issue 4, p1007
- ISSN
1234-3099
- Publication type
Article
- DOI
10.7151/dmgt.2061