No description available.

No description available.

A Hamilton cycle is a cycle which passes through every vertex of a graph. A Hamilton cycle decomposition of a k-regular graph is defined as the partition of the edge set into Hamilton cycles if k is even, or a partition into Hamilton cycles and a 1-factor, if k is odd. Consequently, for 2-regular or 3-regular graphs, finding a Hamilton cycle decompositon is equilvalent to finding a Hamilton cycle. Two classes of graphs are studies in this thesis and both have significant symmetry. The first class of graphs is the 6-regular circulant graphs. These are a king of Cayley graph. Given a finite group A and a subset S ⊆ A, the Cayley Graph Cay(A,S) is the simple graph with vertex set A and edge set {{a, as}|a ∈ A, s ∈ S}. If the group A is cyclic then the graph is called a circulant graph. This thesis proves two results on 6-regular circulant graphs: 1. There is a Hamilton cycle decomposition of every 6-regular circulant graph Cay(Z[subscript n],S) in which S has an element of order n; 2. There is a Hamilton cycle decomposition of every connected 6-regular circulant graph of odd order. The second class of graphs examined in this thesis is a futher generalization of the Generalized Petersen graphs. The Petersen graph is well known as a highly symmetrical graph which does not contain a Hamilton cycle. In 1983 Alspach completely determined which Generalized Petersen graphs contain Hamilton cycles. In this thesis we define a larger class of graphs which includes the Generalized Petersen graphs as a special case. We call this larger class spoked Cayley graphs. We determine which spoked Cayley graphs on Abelian groups are Hamiltonian. As a corollary, we determine which are 1-factorable.

No description available.

No description available.

A Hamilton cycle is a cycle which passes through every vertex of a graph. A Hamilton cycle decomposition of a k-regular graph is defined as the partition of the edge set into Hamilton cycles if k is even, or a partition into Hamilton cycles and a 1-factor, if k is odd. Consequently, for 2-regular or 3-regular graphs, finding a Hamilton cycle decompositon is equilvalent to finding a Hamilton cycle. Two classes of graphs are studies in this thesis and both have significant symmetry. The first class of graphs is the 6-regular circulant graphs. These are a king of Cayley graph. Given a finite group A and a subset S ⊆ A, the Cayley Graph Cay(A,S) is the simple graph with vertex set A and edge set {{a, as}|a ∈ A, s ∈ S}. If the group A is cyclic then the graph is called a circulant graph. This thesis proves two results on 6-regular circulant graphs: 1. There is a Hamilton cycle decomposition of every 6-regular circulant graph Cay(Z[subscript n],S) in which S has an element of order n; 2. There is a Hamilton cycle decomposition of every connected 6-regular circulant graph of odd order. The second class of graphs examined in this thesis is a futher generalization of the Generalized Petersen graphs. The Petersen graph is well known as a highly symmetrical graph which does not contain a Hamilton cycle. In 1983 Alspach completely determined which Generalized Petersen graphs contain Hamilton cycles. In this thesis we define a larger class of graphs which includes the Generalized Petersen graphs as a special case. We call this larger class spoked Cayley graphs. We determine which spoked Cayley graphs on Abelian groups are Hamiltonian. As a corollary, we determine which are 1-factorable.

Interval graphs admit elegant ordering and structural characterizations. A natural digraph analogue of interval graphs, called chronological interval digraphs, has recently been identified and studied. We introduce the class of chronological rectangle digraphs, and show that they are a higher dimensional analogue of chronological interval digraphs. A main goal of this thesis is to establish a foundation of knowledge about this class, including basic properties and an ordering characterization. Our most significant result is a forbidden induced subdigraph characterization for the series-parallel digraphs which are chronological rectangle. We also discuss obtaining chronological rectangle digraphs from orientations of graphs. In addition we introduce the related concept of the chronological interval dimension of a digraph, and determine the digraphs for which it is defined. Unit and proper chronological rectangle digraphs, defined analogously to unit and proper interval graphs, are also introduced and studied. / Graduate

In the Game of Light, as formulated in "Harmonic Evolutions" (J. Kocik, 2007), there is a definition of dynamic graphs and a thorough explanation of how to find the structure of the digraph that shows the changing of states during the game. This thesis furthers this research in two directions: first, by exploring what happens when there are more than two vertex states, by expanding the state space to any cyclic group. Secondly, the research attempted to identify families of graphs and describe their graph states using only the number of vertex states. To further both of these goals, two programs were written, one as a calculator to compute the digraph structure, and one as a visualization tool that automates the game of light, allowing users to input graphs with simple point and click commands, and to easily see how graphs evolve. Finally, about one hundred graphs were evaluated using the calculator, and the resulting structures are recorded.

abstract: A tiling is a collection of vertex disjoint subgraphs called tiles. If the tiles are all isomorphic to a graph $H$ then the tiling is an $H$-tiling. If a graph $G$ has an $H$-tiling which covers all of the vertices of $G$ then the $H$-tiling is a perfect $H$-tiling or an $H$-factor. A goal of this study is to extend theorems on sufficient minimum degree conditions for perfect tilings in graphs to directed graphs. Corrádi and Hajnal proved that every graph $G$ on $3k$ vertices with minimum degree $delta(G)ge2k$ has a $K_3$-factor, where $K_s$ is the complete graph on $s$ vertices. The following theorem extends this result to directed graphs: If $D$ is a directed graph on $3k$ vertices with minimum total degree $delta(D)ge4k-1$ then $D$ can be partitioned into $k$ parts each of size $3$ so that all of parts contain a transitive triangle and $k-1$ of the parts also contain a cyclic triangle. The total degree of a vertex $v$ is the sum of $d^-(v)$ the in-degree and $d^+(v)$ the out-degree of $v$. Note that both orientations of $C_3$ are considered: the transitive triangle and the cyclic triangle. The theorem is best possible in that there are digraphs that meet the minimum degree requirement but have no cyclic triangle factor. The possibility of added a connectivity requirement to ensure a cycle triangle factor is also explored. Hajnal and Szemerédi proved that if $G$ is a graph on $sk$ vertices and $delta(G)ge(s-1)k$ then $G$ contains a $K_s$-factor. As a possible extension of this celebrated theorem to directed graphs it is proved that if $D$ is a directed graph on $sk$ vertices with $delta(D)ge2(s-1)k-1$ then $D$ contains $k$ disjoint transitive tournaments on $s$ vertices. We also discuss tiling directed graph with other tournaments. This study also explores minimum total degree conditions for perfect directed cycle tilings and sufficient semi-degree conditions for a directed graph to contain an anti-directed Hamilton cycle. The semi-degree of a vertex $v$ is $min{d^+(v), d^-(v)}$ and an anti-directed Hamilton cycle is a spanning cycle in which no pair of consecutive edges form a directed path. / Dissertation/Thesis / Ph.D. Mathematics 2013

O objetivo deste trabalho é fazer um estudo amplo e sequencial sobre combinatória. Iniciase com os fundamentos da combinatória enumerativa, tais como permutações, combinações simples, combinações completas e os lemas de Kaplanski. Num segundo momento é apresentado uma abordagem aos problemas de contagem utilizando a teoria de conjuntos; são abordados o princípio da inclusão-exclusão, permutações caóticas e a contagem de funções. No terceiro momento é feito um aprofundamento do conceito de permutação sob a ótica da álgebra abstrata. É explorado o conceito de grupo de permutações e resultados importantes relacionados. Na sequência propõe-se uma relação de ordem completa e estrita para o grupo de permutações. Por fim, investiga-se dois problemas interessantes da combinatória: a determinação do número de caminhos numa malha quadriculada e a contagem de permutações que desconhecem padrões de comprimento três. / The objective of this work is to make a broad and sequential study on combinatorics. It begins with the foundations of enumerative combinatorics, such as permutations, simple combinations, complete combinations, and Kaplanskis lemmas. In a second moment an approach is presented to the counting problems using set theory; the principle of inclusion-exclusion, chaotic permutations and the counting of functions are addressed. In the third moment a deepening of the concept of permutation is made from the perspective of abstract algebra. The concept of group of permutations and related important results is explored. A strict total order relation for the permutation group is proposed. Finally, we investigate two interesting combinatorial problems: the determination of the number of paths in a grid and the number of permutations that avoids patterns of length three.