Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 20 of 53 for “"Cayley Graph"”.
-
Finding CCA groups and graphs algorithmically
Given a group G, any subset C of G\{e} induces a Cayley graph, Cay(G,C). The set C also induces a natural edge-colouring of this graph. All affine automorphisms of the Cayley graph preserve this edge-colouring. A Cayley graph Cay(G,C) has the Cayley Colour Automorphism Property (is CCA), if all its …
-
Geometric properties of the golden ratio Thompson’s group
… rational group. We prove properties of the Cayley graph of the monoid M = ⟨L, R : LR2 = RL2 ⟩, whose topological full group is Vτ . Particularly we compute a distance function for the Cayley graph of the monoid M. Additionally, we prove that this Cayley graph is hyperbolic in the sense of …
-
The spectra of DES S-Boxes
We typically do not associate the field of graph theory with the field of cryptography. In graph theory, the aim is to model relationships with a graph and examine properties of that graph. The goal of cryptography is to design a communication system over a nonsecure channel. One connection between …
-
Hamilton decompositions of 6-regular abelian Cayley graphs
… asked whether every connected, vertex-transitive graph has a Hamilton path. This question has generated a considerable amount of interest, yet remains vastly open. To date, there exist no known connected, vertex-transitive graph that does not possess a Hamilton path. For the Cayley graphs, a …
-
Automata on Cayley Graphs
… to realize very general kinds of inputs. Any graph with the above two properties of a tape must, in fact, be the Cayley graph of a suitable group. Recent investigations by various authors have begun to shed some light on what promises to be intimate connections between the geometry of a Cayley …
-
Uniform Mixing on Cayley Graphs over Z_3^d
This thesis investigates uniform mixing on Cayley graphs over Z_3^d. We apply Mullin's results on Hamming quotients, and characterize the 2(d+2)-regular connected Cayley graphs over Z_3^d that admit uniform mixing at time 2pi/9. We generalize Chan's construction on the Hamming scheme H(d,2) to the …
-
Cayley graphs of order 6pq are Hamiltonian
… is a Hamiltonian cycle in the corresponding Cayley graph on G with connecting set S.
-
Embeddings of Product Graphs Where One Factor is a Hypercube
Voltage graph theory can be used to describe embeddings of product graphs if one factor is a Cayley graph. We use voltage graphs to explore embeddings of various products where one factor is a hypercube, describing some minimal and symmetrical embeddings. We then define a graph product, the weak …
-
Some applications of noncommutative groups and semigroups to information security
… SL2(Fp), and compute bounds on the girth of the Cayley graph of the subgroup of SL2(Fp) for specific generators A, B. We demonstrate that even without optimization, these hashes have comparable performance to hashes in the SHA family.
-
Cayley maps for certain cyclic groups with odd generators
… work for both oral and written presentation; A Cayley graph provides us with a discrete model for a finite group with specified generating set. It is desirable to represent such structures in their simplest form and also so that certain symmetries are emphasized. By simplest form, we mean to …
-
Cayley Graphs of Groups and Their Applications
Cayley graphs are graphs associated to a group and a set of generators for that group (there is also an associated directed graph). The purpose of this study was to examine multiple examples of Cayley graphs through group theory, graph theory, and applications. We gave background material on groups …
-
Artin Groups of Extra-Large Type Are Biautomatic
… Using these techniques we examine paths in the Cayley graph of the Artin group. For any Artin group G, with semigroup generators ${\cal A}$, we define a language $L(G) \subset {\cal A}\sp*$. The language L(G) is a set of canonical forms for the Artin group. In the case G is an Artin group of …
-
Average Cayley genus for Cayley maps with dihedral groups
… and let Delta be a generating set for Gamma. A Cayley map associated with Gamma and Delta is an oriented 2-cell embedding of the Cayley graph GDelta (Gamma) such that the rotation of arcs emanating from each vertex is determined by a unique cyclic permutation of generators and their inverses. A …
-
Dehn's Problems And Geometric Group Theory
… on. In this thesis, we study group actions on Cayley graphs and the Farey tree. We prove that a group has a solvable word problem if and only if its associated Cayley graph is constructible. Moreover, we prove that a group is finitely generated if and only if it acts geometrically on a proper …
-
Group action on neighborhood complexes of Cayley graphs
… by S ≐ {g1, …, gn}, one can construct the Cayley Graph Cayley (G,S). Given a distance set D ⊂ Z≥0 and Cayley (G,S) one can construct a D-neighborhood complex. This neighborhood complex is a simplicial complex to which we can associate a chain complex. The group G acts on this chain complex …
-
Optimal Hardy inequalities on lattices in stratified groups
… on optimal Hardy inequalities for discrete graphs. Previous results on integer lattices provided explicit asymptotic descriptions of optimal weights, based on an optimality theorem for graphs that applies only to the locally finite case. We generalize this theorem to encompass graphs that …
-
Enumeration, isomorphism and Hamiltonicity of Cayley graphs: 2-generated and cubic
This thesis explores 2-generated and cubic Cayley graphs. All 2-generated Cayley graphs with generators from Sn where n < 9, were generated. Further, 3-generated cubic Cayley graphs, where n < 7, were also generated. Among these, the cubic Cayley graphs with up to 40320 vertices were tested for …
-
Symmetries, asymmetries and sense of direction
… related to the notion of sense of direction in graphs: We define this notion and provide some examples of labelling that realize it. We then survey the problem of minimal sense of direction in regular graphs using symmetric labelling, and its connection to various notions such as cycle symmetry, …
-
Topics in additive combinatorics
… the problem of finding the clique number of the Cayley graph on 𝔽<sub>2</sub><sup>n</sup> generated by a random subset. We prove a number of results, most notably that for <em>n</em> in a set of density 1, the clique number is concentrated on a single value.</p> <p>In Chapter 3 we prove that …
-
CAYLEY GRAPHS AND APPLICATIONS OF POWER SUM SYMMETRIC FUNCTION
We consider the Cayley graph on the symmetric group Sn generated by di fferent generating sets and we are interested in finding eigenvalues of the graph. With the eigenvalues, we are able to bound its largest independent set by using Delsarte-Ho man Bound. It is well known that the eigenvalues of …
Page 1 of 3