Publication Date
2025
Document Type
Thesis
Committee Members
Daniel Slilaty, Ph.D. (Advisor); Xiaoyu Liu, Ph.D. (Committee Member); Xiangqian Zhou, Ph.D. (Committee Member); Yuqing Chen, Ph.D. (Committee Member)
Degree Name
Master of Science (MS)
Abstract
The girth of a graph G is the minimum length of a cycle in G. A (k,g)-graph is a k-regular graph of girth g. A (k,g)-cage is a (k,g)-graph with the smallest possible number of vertices. For example, K4 is the unique (3,3)-cage, K3,3 is the unique (3,4)-cage, and the Petersen Graph is the unique (3,5)-cage. The search for cages particular values of (k,g) is an ongoing area of considerable research. For values of (k,g) where the number vertices in a (k,g)-cage is not known, covering graphs have recently been used for constructing progressively smaller and smaller (k,g)-graphs. The covering graphs used have all been constructed using group-theoretic techniques; in particular, regular covering graphs coming from voltage graphs. We will review the general construction method for all covering graphs which uses what are called permutation gain graphs. We used this construction in an attempt to find new (k,g)-graphs. Some interesting graphs are constructed. Our second topic was to generalize the concept of cages to signed graphs. A signed graph is a pair (G,σ) in which G is a graph and σ: E(G) → {+,−}. A cycle in G is called positive or negative according to the product of the signs on its edges. A circuit in a signed graph is a set of edges which is either: the edge set of a positive cycle or the edges set of the union of two negative cycles which intersect in at most a single vertex. The girth of (G,σ) is the smallest possible order of a circuit. A (k,g)-signed graph is a signed graph (G,σ) in which G is k-regular and which has girth g. A (k,g)±-cage is a (k,g)-signed graph with the smallest possible number of vertices. We determine all (3,g)±-cages whose underlying graphs are simple for girth g ≤ 8 and we also find all (4, 5)±-cages whose underlying graphs are simple. Finally we show that there is a signing of the k-dimensional hypercube for each k ≥ 3 which has girth 6. This yields an infinite family of (k, 6)-signed graphs with 2k vertices.
Page Count
87
Department or Program
Department of Mathematics and Statistics
Year Degree Awarded
2025
Copyright
Copyright 2025, all rights reserved. My ETD will be available under the "Fair Use" terms of copyright law.
ORCID ID
0009-0005-8626-8028
