Extremal Cayley Graphs
Date
2012-08
Authors
Schneider, Joni J.
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Let Γ be a finite group with m elements. Let A be a nonempty subset of Γ. The Cayley digraph of Γ generated by A, denoted by Cay (Γ, A), is the digraph with vertex set Γ and arc set {uv | u-1v ∈ A}. A simple example of a Cayley digraph is the n-Cube.
A Cayley digraph can be considered as a graphical representation of a finite group by its generating set. Cayley digraphs of finite abelian groups are often used to model communication networks. Because of their complex algebraic structure and their applications in network theory, Cayley digraphs have been studied extensively in recent years. In this thesis, we focus on some optimization problems about Cayley digraphs. In particular, we study how large the number of vertices a Cayley digraph can have for a given diameter and degree. This is one of the central problems in the study of extremal Cayley digraphs.
Let ℤm denote the cyclic group of residue classes of integers modulo m with addition. Given any two positive integers d and k, define m(d, k) as the largest positive integer m such that there exists a set A of k integers with diam(Cay(ℤm, A)) ≤ d, where diam(G) denotes that diameter of a graph G. In other words, m(d, k) = max {m | diam(Cay(ℤm, A)) ≤ d / A / |A|=k. We will study this extremal function. In particular, we will prove a lower bound for m(d,k).
We will introduce a geometric representation of ℤm with respect to a generating set A. This representation was first introduced by C. K. Wong and Don Coppersmith in 1974. This geometric representation of ℤm is very useful in establishing upper bounds for m(d,k). We will discuss some properties of the A-representation of ℤm in two and three dimensional cases. We will also use this method to prove upper bounds for m(d, 2). Some other related extremal functions will also be studied in this thesis.
Description
Keywords
Cayley graphs, extremal problems, information networks
Citation
Schneider, J. J. (2012). Extremal Cayley graphs (Unpublished thesis). Texas State University-San Marcos, San Marcos, Texas.