Return to search

Restricted and Unrestricted Coverings of Complete Bipartite Graphs with Hexagons

A minimal covering of a graph G with isomorphic copies of graph H is a set {H1, H2, H3, ... , Hn} where Hi is isomorphic to H, the vertex set of Hi is a subset of G, the edge set of G is a subset of the union of Hi's, and the cardinality of the union of Hi's minus G is minimum. Some studies have been made of covering the complete graph in which case an added condition of the edge set of Hi is the subset of the edge set of G for all i which implies no additional restrictions. However, if G is not the complete graph, then this condition may have implications. We will give necessary and sufficient conditions for minimal coverings of complete bipartite graph with 6-cycles, which we call minimal unrestricted coverings. We also give necessary and sufficient conditions for minimal coverings of the complete bipartite graph with 6-cycles with the added condition the edge set of Hi is a subset of G for all i, and call these minimal restricted coverings.

Identiferoai:union.ndltd.org:ETSU/oai:dc.etsu.edu:etd-2315
Date01 May 2013
CreatorsSurber, Wesley M
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.0017 seconds