The study of cycles, particularly Hamiltonian cycles, is very important in many applications. Bondy posited his famous metaconjecture, that every condition sufficient for Hamiltonicity actually guarantees a graph is pancyclic. Pancyclicity is a stronger structural property than Hamiltonicity. An even stronger structural property is for a graph to be cycle extendable. Hendry conjectured that any graph which is Hamiltonian and chordal is cycle extendable. In this dissertation, cycle extendability is investigated and generalized. It is proved that chordal 2-connected K1,3-free graphs are cycle extendable. S-cycle extendability was defined by Beasley and Brown, where S is any set of positive integers. A conjecture is presented that Hamiltonian chordal graphs are {1, 2}-cycle extendable. Dirac’s Theorem is an classic result establishing a minimum degree condition for a graph to be Hamiltonian. Ore’s condition is another early result giving a sufficient condition for Hamiltonicity. In this dissertation, generalizations of Dirac’s and Ore’s Theorems are presented. The Chvatal-Erdos condition is a result showing that if the maximum size of an independent set in a graph G is less than or equal to the minimum number of vertices whose deletion increases the number of components of G, then G is Hamiltonian. It is proved here that the Chvatal-Erdos condition guarantees that a graph is cycle extendable. It is also shown that a graph having a Hamiltonian elimination ordering is cycle extendable. The existence of Hamiltonian cycles which avoid sets of edges of a certain size and certain subgraphs is a new topic recently investigated by Harlan, et al., which clearly has applications to scheduling and communication networks among other things. The theory is extended here to bipartite graphs. Specifically, the conditions for the existence of a Hamiltonian cycle that avoids edges, or some subgraph of a certain size, are determined for the bipartite case. Briefly, this dissertation contributes to the state of the art of Hamiltonian cycles, cycle extendability and edge and graph avoiding Hamiltonian cycles, which is an important area of graph theory.

No description available.

For a graph G = (V (G), E (G)), a set S ~ V (G) dominates G if each vertex in V (G) \S is adjacent to a vertex in S. The domination number I (G) (independent domination number i (G)) of G is the minimum cardinality amongst its dominating sets (independent dominating sets). G is k-edge-domination-critical, abbreviated k-1- critical, if the domination number k decreases whenever an edge is added. Further, G is hamiltonian if it has a cycle that passes through each of its vertices. This dissertation assimilates research generated by two conjectures: Conjecture I. Every 3-1-critical graph with minimum degree at least two is hamiltonian. Conjecture 2. If G is k-1-critical, then I ( G) = i ( G). The recent proof of Conjecture I is consolidated and presented accessibly. Conjecture 2 remains open for k = 3 and has been disproved for k :::>: 4. The progress is detailed and proofs of new results are presented. / Mathematical Science / M. Sc. (Mathematics)

A snake (coil) is an induced path (cycle) in a hypercube. They are well known from the snake-in-the-box (coil-in-the-box) problem which asks for the longest snake (coil) in a hypercube. They have been generalized to k-snakes (k-coils) which preserve distances between their every two vertices at distance at most k − 1 in hypercube. We study them as a variant of Locke's hypothesis. It states that a balanced set F ⊆ V (Qn) of cardinality 2m can be avoided by a Hamiltonian cycle if n ≥ m + 2 and m ≥ 1. We show that if S is a k-snake (k-coil) in Qn for n ≥ k ≥ 6 (n ≥ k ≥ 7), then Qn − V (S) is Hamiltonian laceable. For a fixed k the number of vertices of a k-coil may even be exponential with n. We introduce a dragon, which is an induced tree in a hypercube, and its generalization a k-dragon which preserves distances between its every two vertices at distance at most k−1 in hypercube. By proving a specific lemma from my Bachelor thesis that was previously verified by a computer, we finish the proof of the theorem regarding Hamiltonian laceability of hypercubes without n-dragons.

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 various properties including Hamiltonicity and diameter. These results are available on the internet in easy to read tables. The motivation for the testing of Cayley graphs for Hamiltonicity was the conjecture that states that every connected Cayley graph is Hamiltonian. New enumeration results are presented for various classes of 2-generated Cayley graphs. Previously known enumeration results are presented for cubic Cayley graphs.Finally, isomorphism and color isomorphism of 2-generated and cubic Cay­ley graphs is explored. Numerous new results are presented. All algorithms used in this thesis are explained in full.

For a graph G = (V (G), E (G)), a set S ~ V (G) dominates G if each vertex in V (G) \S is adjacent to a vertex in S. The domination number I (G) (independent domination number i (G)) of G is the minimum cardinality amongst its dominating sets (independent dominating sets). G is k-edge-domination-critical, abbreviated k-1- critical, if the domination number k decreases whenever an edge is added. Further, G is hamiltonian if it has a cycle that passes through each of its vertices. This dissertation assimilates research generated by two conjectures: Conjecture I. Every 3-1-critical graph with minimum degree at least two is hamiltonian. Conjecture 2. If G is k-1-critical, then I ( G) = i ( G). The recent proof of Conjecture I is consolidated and presented accessibly. Conjecture 2 remains open for k = 3 and has been disproved for k :::>: 4. The progress is detailed and proofs of new results are presented. / Mathematical Science / M. Sc. (Mathematics)

The problem of defining cycles in infinite graphs has received much attention in the literature. Diestel and Kuhn have proposed viewing a graph as 1-complex, and defining a topology on the point set of the graph together with its ends. In this setting, a circle in the graph is a homeomorph of the unit circle S^1 in this topological space. For locally finite graphs this setting appears to be natural, as many classical theorems on cycles in finite graphs extend to the infinite setting. A Hamilton circle in a graph is a circle containing all the vertices of the graph. We exhibit a necessary and sufficient condition that a countable graph contain a Hamilton circle in terms of the existence of Hamilton cycles in an increasing sequence of finite graphs. As corollaries, we obtain extensions to locally finite graphs of Zhan's theorem that all 7-connected line graphs are hamiltonian (confirming a conjecture of Georgakopoulos), and Ryjacek's theorem that all 7-connected claw-free graphs are hamiltonian. A third corollary of our main result is Georgakopoulos' theorem that the square of every two-connected locally finite graph contains a Hamilton circle (an extension of Fleischner's theorem that the square of every two-connected finite graph is Hamiltonian).