Packings and coverings of the complete graph with trees

Haghshenas, Sadegheh (2015) Packings and coverings of the complete graph with trees. Doctoral (PhD) thesis, Memorial University of Newfoundland.

[img] [English] PDF - Accepted Version
Available under License - The author retains copyright ownership and moral rights in this thesis. Neither the thesis nor substantial extracts from it may be printed or otherwise reproduced without the author's permission.

Download (3550Kb)

Abstract

In this thesis, we define the spectrum problem for packings (coverings) of G to be the problem of finding all graphs H such that a maximum G-packing (minimum G- covering) of the complete graph with the leave (excess) graph H exists. The set of achievable leave (excess) graphs in G-packings (G-coverings) of the complete graph is called the spectrum of leave (excess) graphs for G. Then, we consider this problem for trees with up to five edges. We will prove that for any tree T with up to five edges, if the leave graph in a maximum T-packing of the complete graph Kn has i edges, then the spectrum of leave graphs for T is the set of all simple graphs with i edges. In fact, for these T and i and H any simple graph with i edges, we will construct a maximum T-packing of Kn with the leave graph H. We will also show that for any tree T with k ≤ 5 edges, if the excess graph in a minimum T-covering of the complete graph Kn has i edges, then the spectrum of excess graphs for T is the set of all simple graphs and multigraphs with i edges, except for the case that T is a 5-star, for which the graph formed by four multiple edges is not achievable when n = 12.

Item Type: Thesis (Doctoral (PhD))
URI: http://research.library.mun.ca/id/eprint/12161
Item ID: 12161
Additional Information: Includes bibliographical references (pages 98-101).
Keywords: packing, covering, leave graph, excess graph
Department(s): Science, Faculty of > Mathematics and Statistics
Date: December 2015
Date Type: Submission
Library of Congress Subject Heading: Trees (Graph theory); Complete graphs; Decomposition (Mathematics); Graph labelings

Actions (login required)

View Item View Item

Downloads

Downloads per month over the past year

View more statistics