Accession Number:

ADA470182

Title:

Realizable Triples in Dominator Colorings

Descriptive Note:

Master's thesis

Corporate Author:

NAVAL POSTGRADUATE SCHOOL MONTEREY CA DEPT OF MATHEMATICS

Personal Author(s):

Report Date:

2007-06-01

Pagination or Media Count:

43.0

Abstract:

Given a graph G and its vertex set VG, the chromatic number, ChiG, 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, gammaG, 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 gammaG a, ChiG b, and Chi subd G c. For every ordered triple, a, b, c of positive integers, if either a a1 and bc greater or equal 2 or b 2 less than or equal a, bc and c less than or equal ab, previous work has shown that the triple is realizable. The bounds do not consider the case abc. In an effort to realize all the ordered triples, we explore graphs and graph classes with abck greater or equal 2.

Subject Categories:

  • Theoretical Mathematics
  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE