dc.contributor.advisor Jia, Xingde dc.contributor.author Schneider, Joni J. ( ) dc.date.accessioned 2020-09-02T14:36:05Z dc.date.available 2020-09-02T14:36:05Z dc.date.issued 2012-08 dc.identifier.citation Schneider, J. J. (2012). Extremal Cayley graphs (Unpublished thesis). Texas State University-San Marcos, San Marcos, Texas. dc.identifier.uri https://digital.library.txstate.edu/handle/10877/12518 dc.description.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. dc.format Text dc.format.extent 75 pages dc.format.medium 1 file (.pdf) dc.language.iso en dc.subject Cayley graphs dc.subject Extremal problems dc.subject Information networks dc.title Extremal Cayley Graphs txstate.documenttype Thesis thesis.degree.department Mathematics thesis.degree.grantor Texas State University--San Marcos thesis.degree.level Masters thesis.degree.name Master of Science txstate.access restricted dc.description.department Mathematics
﻿