## Abstract

A *factoring* of a graph G = (V, E) is a collection of spanning subgraphs F_{1}, F_{2}, ... , F_{k}, known as *factors* into which the edge set E has been partitioned. A *dominating set* of a graph is a set of nodes such that every node in the graph is either contained in the set or has an edge to some node in the set. Each factor F_{i} is itself a graph and so has a dominating set. This set is called a *local dominating set* or LDS. An LDS of minimum size contains γi nodes. In addition, there is some set of nodes named a *global dominating set* which dominates all of the factors. If a global dominating set is of minimum size, it is called a GDS and contains γ nodes.

A central question answered by this dissertation is under what circumstances, given a set of integers γ_{l}, γ_{2}, ... , γ_{k}, and γ, there is a graph which can be factored into k factors in such a way that a minimum LDS of F_{i} has size γ_{l}, 1 ≤ i ≤ k, and a GDS has size γ.

The general solution to this central question is complicated. In addition, simpler subproblems are often precisely those which are most applicable to practical problems. For these reasons, simpler solutions are found for several special cases of the general characterization problem.

A strong relationship is demonstrated between two application areas and the ideas of global domination and factoring. We find that a factoring of a graph can represent the parallel computation of a class of constraint problems or the routes of multicast messages in a network.

The applicability of these ideas 1s limited by the computational complexity of the problem of finding a GDS in a factoring. The problem is NP-Hard in general and we find that, more surprisingly, when the factors are very simple structures such as trees or even paths, the problem remains NP-Hard.

## Notes

If this is your thesis or dissertation, and want to learn how to access it or for more information about readership statistics, contact us at STARS@ucf.edu

## Graduation Date

1992

## Semester

Fall

## Advisor

Brigham, Robert C.

## Degree

Doctor of Philosophy (Ph.D.)

## College

College of Arts and Sciences

## Department

Computer Science

## Degree Program

Computer Science

## Format

## Language

English

## Rights

Written permission granted by copyright holder to the University of Central Florida Libraries to digitize and distribute for nonprofit, educational purposes.

## Length of Campus-only Access

None

## Access Status

Doctoral Dissertation (Open Access)

## Identifier

DP0001860

## STARS Citation

Carrington, Julie R., "Global Domination of Factors of a Graph" (1992). *Retrospective Theses and Dissertations*. 4389.

https://stars.library.ucf.edu/rtd/4389

## Contributor (Linked data)

## Accessibility Status

Searchable text