Back to search

University of South Florida

Domination in Graphs

Abstract

dc:description

Vizing conjectured in 1963 that the domination number of the Cartesian product of two graphs is at least the product of their domination numbers; this remains one of the biggest open problems in the study of domination in graphs. Several partial results have been proven, but the conjecture has yet to be proven in general. The purpose of this thesis was to study Vizing's conjecture, related results, and open problems related to the conjecture. We give a survey of classes of graphs that are known to satisfy the conjecture, and of Vizing-like inequalities and conjectures for different types of domination and graph products. We also give an improvement of the Clark-Suen inequality. Some partial results about fair domination are presented, and we summarize some open problems related to Vizing's conjecture.

Degree

thesis:*
Level thesis:degree_level
Thesis
Discipline thesis:degree_discipline
Mathematics and Statistics
Grantor
University of South Florida
Year dc:date
2010

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Tarr, Jennifer M
Contributors dc:contributor
  • Stephen Suen, Ph.D.
  • Natasa Jonoska, Ph.D.
  • Brendan Nagle, Ph.D.

Subjects

dc:subject × 7

Rights

Language dc:language
EN-US

Identifiers

dc:identifier.*
Repository record dc:identifier
https://digitalcommons.usf.edu/etd/1786

Chain of custody

source
Harvested from
University of South Florida
Base URL
digitalcommons.usf.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Tarr, Jennifer M. Domination in Graphs. Thesis thesis, University of South Florida, 2010. https://digitalcommons.usf.edu/etd/1786