Document Type
Article
Publication Date
1-2-2020
Description
Let (Formula presented.) be a graph. For two disjoint sets of vertices (Formula presented.) and (Formula presented.), set (Formula presented.) dominates set (Formula presented.) if every vertex in (Formula presented.) is adjacent to at least one vertex in (Formula presented.). In this paper we introduce the upper domatic number (Formula presented.), which equals the maximum order (Formula presented.) of a vertex partition (Formula presented.) such that for every (Formula presented.), (Formula presented.), either (Formula presented.) dominates (Formula presented.) or (Formula presented.) dominates (Formula presented.), or both. We study properties of the upper domatic number of a graph, determine bounds on (Formula presented.), and compare (Formula presented.) to a related parameter, the transitivity (Formula presented.) of (Formula presented.).
Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 International License.
Citation Information
Haynes, Teresa W.; Hedetniemi, Jason T.; Hedetniemi, Stephen T.; McRae, Alice; and Phillips, Nicholas. 2020. The Upper Domatic Number of a Graph. AKCE International Journal of Graphs and Combinatorics. Vol.17(1). 139-148. https://doi.org/10.1016/j.akcej.2018.09.003 ISSN: 0972-8600
Copyright Statement
© 2018 Kalasalingam University. Published with license by Taylor & Francis Group, LLC. This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.