Author : Bethel I. McGrew
Publisher :
ISBN 13 :
Total Pages : 110 pages
Book Rating : 4.:/5 (132 download)
Book Synopsis From Multi-prime to Subset Labelings of Graphs by : Bethel I. McGrew
Download or read book From Multi-prime to Subset Labelings of Graphs written by Bethel I. McGrew and published by . This book was released on 2021 with total page 110 pages. Available in PDF, EPUB and Kindle. Book excerpt: A graph labeling is an assignment of labels (elements of some set) to the vertices or edges (or both) of a graph G. If only the vertices of G are labeled, then the resulting graph is a vertex-labeled graph. If only the edges are labeled, the resulting graph is an edge-labeled graph. The concept was first introduced in the 19th century when Arthur Cayley established Cayley's Tree Formula, which proved that there are n^n-2 distinct labeled trees of order n. Since then, it has grown into a popular research area. In this study, we first review several types of labelings, then turn to the particular problem of multi-prime labelings, where products of distinct primes are assigned as labels that are disjoint for adjacent vertices and intersecting for non-adjacent vertices. We express the problem in the equivalent language of subset labelings, denoting elements in a label by their indices 1, 2, ... , k. A graph’s subset index is the smallest number of elements k from which we can assign a subset labeling f, considered as a function with domain V(G) and range P *([k]) (i.e., the power set of [k] with the empty set omitted). It turns out that the problem of determining the subset index for graph classes such as paths and cycles is nontrivial. For paths of order n, we determine the index up to n = 24, and for cycles of order n, we determine it up to n = 18. We also describe the connection between the problem of determining the subset index of a graph and a combinatorics problem related to the so-called Erdős-Ko-Rado Theorem, namely the problem of determining the largest possible family of sets such that every set is disjoint from at most some fixed number of sets in the collection. Our work on subset labelings of cycles in particular has resulted in the correction of a significant research result in this area, reopening the problem for further research. We also consider the problem of determining the subset index for other graph classes, including prisms and grids, for which we present upper bounds in terms of the subset indices of paths and cycles. We conclude by studying the problem for select graph unions.
