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 66 for “"Cayley graphs"”.
-
Extremal Cayley Graphs
… 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 …
-
Colouring Cayley Graphs
… three ways to bound the chromatic number on a Cayley graph. 1. If the connection set contains information about a smaller graph, then these two graphs are related. Using this information, we will show that Cayley graphs cannot have chromatic number three. 2. We will prove a general statement …
-
Automata on Cayley Graphs
… 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 graph and the group-theoretic properties of the underlying group.
-
State Transfer & Strong Cospectrality in Cayley Graphs
… prove various results about these properties in Cayley graphs. We consider how big a set of pairwise strongly cospectral vertices can be in a graph. We prove an upper bound on the size of such a set in normal Cayley graphs in terms of the multiplicities of the eigenvalues of the graph. We then …
-
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 …
-
Cayley graphs of order 6pq are Hamiltonian
… is a Hamiltonian cycle in the corresponding Cayley graph on G with connecting set S.
-
The Directed Forest Complex of Cayley Graphs
… in Γ. We study the directed forest complex of Cayley graphs of finite groups. The homology of DF(Γ) contains information about the graph, Γ and about the group, G. The ultimate goal is to classify DF(Γ) up to homotopy, compute its homology, and interpret the findings in terms of properties of …
-
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 …
-
Splines on Cayley Graphs of the Symmetric Group
… spline rings where the underlying graph is the Cayley graph of a symmetric group generated by a collection of transpositions. These rings generalize the GKM construction for equivariant cohomology rings of flag, regular semisimple Hessenberg, and permutohedral varieties. These cohomology rings …
-
Hamilton decompositions of 6-regular abelian Cayley graphs
… that does not possess a Hamilton path. For the Cayley graphs, a subclass of vertex-transitive graphs, the following conjecture was made: Weak Lovász Conjecture: Every nontrivial, finite, connected Cayley graph is hamiltonian. The Chen-Quimpo Theorem proves that Cayley graphs on abelian groups …
-
Cayley Graphs of Semigroups and Applications to Hashing
… a new proposal for hash functions based on Cayley graphs of semigroups. In our proposed hash function, the noncommutative semigroup of linear functions under composition is considered as platform for the scheme. We will also discuss its efficiency, pseudorandomness and security features. …
-
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 …
-
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 …
-
Cayley Graphs of PSL(2) over Finite Commutative Rings
… the deepest open questions in graph theory, and Cayley graphs are an applicable and useful subtopic of algebra. Chapter 1 will introduce Hadwiger's conjecture and Cayley graphs, providing a summary of background information on those topics, and continuing by introducing our problem. Chapter 2 …
-
Analysis of wormhole routings in cayley graphs of permutation groups.
… Recently, new classes of networks called Cayley graphs of permutation groups are considered very promising alternatives. Although proposed Cayley networks have superior topological properties over the traditional network topologies, the design of the deadlock-free wormhole routing …
-
Analysis And Construction Of Extremal Circulant And Other Abelian Cayley Graphs
… of extremal circulant and other Abelian Cayley graphs. For the purpose of this thesis, extremal graphs are understood as graphs with largest possible order for given degree and diameter, and the search for them is called the degree-diameter problem. The emphasis is on circulant graphs and …
-
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 …
-
Extremal Metric and Topological Properties of Vertex Transitive and Cayley Graphs
… degree diameter problem we investigate finding graphs as large as possible with a given degree and diameter. Further, we may consider additional properties of such extremal graphs, for example restrictions on the kinds of symmetries that the graph in question exhibits. <br></br><br></br> We …
-
STRUCTURAL PROPERTIES OF I-GRAPHS: THEIR INDEPENDENCE NUMBERS AND CAYLEY GRAPHS
… numbers and algebraic properties of I-graphs. The I-graphs are a further generalization of the Generalized Petersen graphs whose independence numbers have been previously researched. Specifically, we give bounds for the independence number of different I-graphs and sub-classes of …
Page 1 of 4