Return to search

Locating-Domination in Complementary Prisms.

Let G = (V (G), E(G)) be a graph and G̅ be the complement of G. The complementary prism of G, denoted GG̅, is the graph formed from the disjoint union of G and G̅ by adding the edges of a perfect matching between the corresponding vertices of G and G̅. A set D ⊆ V (G) is a locating-dominating set of G if for every u ∈ V (G)D, its neighborhood N(u)⋂D is nonempty and distinct from N(v)⋂D for all v ∈ V (G)D where v ≠ u. The locating-domination number of G is the minimum cardinality of a locating-dominating set of G. In this thesis, we study the locating-domination number of complementary prisms. We determine the locating-domination number of GG̅ for specific graphs and characterize the complementary prisms with small locating-domination numbers. We also present bounds on the locating-domination numbers of complementary prisms.

Identiferoai:union.ndltd.org:ETSU/oai:dc.etsu.edu:etd-3223
Date09 May 2009
CreatorsHolmes, Kristin Renee Stone
PublisherDigital Commons @ East Tennessee State University
Source SetsEast Tennessee State University
Detected LanguageEnglish
Typetext
Formatapplication/pdf
SourceElectronic Theses and Dissertations
RightsCopyright by the authors.

Page generated in 0.0019 seconds