Skip to content
Home
About Us
Resources
Profiles Metrics
Authors Directory
Institutions Directory
Top Authors
Top Institutions
Top Sponsors
AI Digest
Contact Us
Menu
Home
About Us
Resources
Profiles Metrics
Authors Directory
Institutions Directory
Top Authors
Top Institutions
Top Sponsors
AI Digest
Contact Us
Home
About Us
Resources
Profiles Metrics
Authors Directory
Institutions Directory
Top Authors
Top Institutions
Top Sponsors
AI Digest
Contact Us
Menu
Home
About Us
Resources
Profiles Metrics
Authors Directory
Institutions Directory
Top Authors
Top Institutions
Top Sponsors
AI Digest
Contact Us
Publication Details
AFRICAN RESEARCH NEXUS
SHINING A SPOTLIGHT ON AFRICAN RESEARCH
mathematics
Rainbow disconnection in graphs
Discussiones Mathematicae - Graph Theory, Volume 38, No. 4, Year 2018
Notification
URL copied to clipboard!
Description
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. © 2018 Academy of Management. All rights reserved.
Authors & Co-Authors
Chartrand, Gary
United States, Kalamazoo
Western Michigan University
Haynes, Teresa W.
United States, Johnson
East Tennessee State University
Hedetniemi, Stephen T.
Unknown Affiliation
Zhang, Ping
United States, Kalamazoo
Western Michigan University
Statistics
Citations: 17
Authors: 4
Affiliations: 3
Identifiers
Doi:
10.7151/dmgt.2061
ISSN:
12343099