Realizable Triples in Dominator Colorings
Abstract
Given a graph G and its vertex set V(G), the chromatic number, Chi(G), represents the minimum number of colors required to color the vertices of G so that no two adjacent vertices have the same color. The domination number of G, gamma(G), the minimum number of vertices in a set S, where every vertex in the set ( ) V G S is adjacent to a vertex in S. The dominator chromatic number of the graph, Chi subd (G) represents the smallest number of colors required in a proper coloring of G with the additional property that every vertex dominates a color class. The ordered triple, (a, b, c), is realizable if a connected graph G exists with gamma(G) = a, Chi(G) = b, and Chi subd (G) = c. For every ordered triple, (a, b, c) of positive integers, if either (a) a=1 and b=c greater or equal 2 or (b) 2 less than or equal a, b<c and c less than or equal a+b, previous work has shown that the triple is realizable. The bounds do not consider the case a=b=c. In an effort to realize all the ordered triples, we explore graphs and graph classes with a=b=c=k greater or equal 2.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jun 01, 2007
- Accession Number
- ADA470182
Entities
People
- Douglas M. Fletcher
Organizations
- Naval Postgraduate School