In 1975, Sheehan conjectured that every simple 4-regular hamiltonian graph has a second Hamilton cycle. If Sheehan's Conjecture holds, then the result can be extended to all simple d-regular hamiltonian graphs with d at least 3. First, we survey some previous results which verify the existence of a second Hamilton cycle if d is large enough. We will then demonstrate some techniques for finding a second Hamilton cycle that will be used throughout this paper. Finally, we use these techniques and show that for certain 4-regular Hamiltonian graphs whose automorphism group is large enough, a second Hamilton cycle exists.

In 1975, Sheehan conjectured that every simple 4-regular hamiltonian graph has a second Hamilton cycle. If Sheehan's Conjecture holds, then the result can be extended to all simple d-regular hamiltonian graphs with d at least 3. First, we survey some previous results which verify the existence of a second Hamilton cycle if d is large enough. We will then demonstrate some techniques for finding a second Hamilton cycle that will be used throughout this paper. Finally, we use these techniques and show that for certain 4-regular Hamiltonian graphs whose automorphism group is large enough, a second Hamilton cycle exists.

In the first part of the thesis we define an automorphism φn for each star graph Stn of degree n-1, which yields permutations of labels for the edges of Stn taken from the set of integers {1,..., [n/2c]}. By decomposing these permutations into permutation cycles, we are able to identify edge-disjoint Hamilton cycles that are automorphic images of a known two-labelled Hamilton cycle H1 2(n) in Stn. The search for edge-disjoint Hamilton cycles in star graphs is important for the design of interconnection network topologies in computer science. All our results improve on the known bounds for numbers of any kind of edge-disjoint Hamilton cycles in star graphs.

Let G be a graph and k be an integer greater than or equal to the chromatic number of G. The k-colouring graph of G is the graph whose vertices are k-colourings of G, with two colourings adjacent if they colour exactly one vertex differently. We explore the Hamiltonicity and connectivity of such graphs, with particular focus on the k-colouring graphs of complete multipartite graphs. We determine the connectivity of the k-colouring graph of the complete graph on n vertices for all n, and show that the k-colouring graph of a complete multipartite graph K is 2-connected whenever k is at least the chromatic number of K plus one. Additionally, we examine a conjecture that every connected k-colouring graph is 2-connected, and give counterexamples for k greater than or equal to 4. As our main result, we show that for all k greater than or equal to 2t, the k-colouring graph of a complete t-partite graph is Hamiltonian. Finally, we characterize the complete multipartite graphs K whose k-colouring graphs are Hamiltonian when k is the chromatic number of K plus one. / Graduate

A reação de Fenton é o nome dado à oxidação de ferro(II) a ferro(III) pela água oxigenada, uma reação que produz espécies com alto poder oxidante como o radical hidroxila. Neste trabalho, foi desenvolvida uma metodologia espectrofotométrica para o acompanhamento da formação de ferro(III) nos momentos iniciais da reação de Fenton. Esta metodologia foi aplicada a quatro conjuntos de reações: (A) o sistema Fenton simples, contendo apenas ferro(II) e H2O2; (B) o sistema A contendo isopropanol, um substrato orgânico simples que sofre principalmente oxidação a acetona; (C) o sistema A contendo o catalisador 3,5-di-terc-butil-catecol (H2DTBCat); (D) o sistema C mais isopropanol, que corresponde ao sistema catalítico completo. Em cada conjunto, variou-se as concentrações de ferro(II) e H2O2. Um modelo cinético, baseado num conjunto de reações explícitas e as respectivas constantes de velocidade, foi desenvolvido para simular a velocidade de formação de ferro(III) para estes quatro conjuntos de reações. Utilizando reações relatadas na literatura, o modelo forneceu simulações que reproduziram satisfatoriamente os dados experimentais dos conjuntos A e B. No caso dos conjuntos C e D, porém, foi necessário propor uma etapa envolvendo a formação de ferro(IV) ou ferril, estabilizado por complexação com o H2DTBCat. Entretanto, mesmo com a inclusão desta espécie, o modelo não captou a complexidade do sistema em altas concentrações de peróxido e ferro. Esta falha foi atribuída à rápida degradação competitiva do H2DTBCat nestas condições, com a subseqüente participação destes produtos de degradação na reação ou como co-catalisadores ou como inibidores. / The Fenton reaction is the name given to the oxidation of iron(II) to iron(III) by hydrogen peroxide, a reaction that produces highly oxidizing species like the hydroxyl radical. In this work, a spectrophotometric methodology is developed to accompany the formation of iron(III) during the initial moments of the Fenton reaction. This methodology was applied to four sets of reactions: (A) the simple Fenton system, containing only iron(II) and H2O2; (B) system A containing isopropanol, a simple substrate that undergoes principally oxidation to acetone; (C) system A containing the catalyst 3,5-di-tert-butyl-catechol (H2DTBCat); (D) system C plus isopropanol, corresponding to the complete catalytic system. For each set of reactions, the concentrations of iron(II) and H2O2 were varied. A kinetic model, based on explicit chemical reactions and their respective rate constants, was developed to simulate the the rate of formation of iron(III) for these four sets of reactions above. Using reactions described in the literature, the model produced simulations that satisfactorily reproduced the experimental data of sets A and B. In the case of sets C and D, however, it was necessary to propose an additional step involving the formation of iron(IV) or ferril, stabilized by complexation with H2DTBCat. Nonetheless, even with the inclusion of this species, the model failed to capture the complexity of the system at high concentrations of peroxide and iron. This failure was attributed to the rapid competitive degradation of H2DTBCat under these conditions, with the subsequent participation of the degradation products in the reaction as either co-catalysts or inhibitors.

We say a graph is locally P if the induced graph on the neighbourhood of every vertex has the property P. Specically, a graph is locally traceable (LT) or locally hamiltonian (LH) if the induced graph on the neighbourhood of every vertex is traceable or hamiltonian, respectively. A locally locally hamiltonian (L2H) graph is a graph in which the graph induced by the neighbourhood of each vertex is an LH graph. This concept is generalized to an arbitrary degree of nesting, to make it possible to work with LkH graphs. This thesis focuses on the global cycle properties of LT, LH and LkH graphs. Methods are developed to construct and combine such graphs to create others with desired properties. It is shown that with the exception of three graphs, LT graphs with maximum degree no greater than 5 are fully cycle extendable (and hence hamiltonian), but the Hamilton cycle problem for LT graphs with maximum degree 6 is NP-complete. Furthermore, the smallest nontraceable LT graph has order 10, and the smallest value of the maximum degree for which LT graphs can be nontraceable is 6. It is also shown that LH graphs with maximum degree 6 are fully cycle extendable, and that there exist nonhamiltonian LH graphs with maximum degree 9 or less for all orders greater than 10. The Hamilton cycle problem is shown to be NP-complete for LH graphs with maximum degree 9. The construction of r-regular nonhamiltonian graphs is demonstrated, and it is shown that the number of vertices in a longest path in an LH graph can contain a vanishing fraction of the vertices of the graph. NP-completeness of the Hamilton cycle problem for LkH graphs for higher values of k is also investigated. / Mathematical Sciences / D. Phil. (Mathematics)

A reação de Fenton é o nome dado à oxidação de ferro(II) a ferro(III) pela água oxigenada, uma reação que produz espécies com alto poder oxidante como o radical hidroxila. Neste trabalho, foi desenvolvida uma metodologia espectrofotométrica para o acompanhamento da formação de ferro(III) nos momentos iniciais da reação de Fenton. Esta metodologia foi aplicada a quatro conjuntos de reações: (A) o sistema Fenton simples, contendo apenas ferro(II) e H2O2; (B) o sistema A contendo isopropanol, um substrato orgânico simples que sofre principalmente oxidação a acetona; (C) o sistema A contendo o catalisador 3,5-di-terc-butil-catecol (H2DTBCat); (D) o sistema C mais isopropanol, que corresponde ao sistema catalítico completo. Em cada conjunto, variou-se as concentrações de ferro(II) e H2O2. Um modelo cinético, baseado num conjunto de reações explícitas e as respectivas constantes de velocidade, foi desenvolvido para simular a velocidade de formação de ferro(III) para estes quatro conjuntos de reações. Utilizando reações relatadas na literatura, o modelo forneceu simulações que reproduziram satisfatoriamente os dados experimentais dos conjuntos A e B. No caso dos conjuntos C e D, porém, foi necessário propor uma etapa envolvendo a formação de ferro(IV) ou ferril, estabilizado por complexação com o H2DTBCat. Entretanto, mesmo com a inclusão desta espécie, o modelo não captou a complexidade do sistema em altas concentrações de peróxido e ferro. Esta falha foi atribuída à rápida degradação competitiva do H2DTBCat nestas condições, com a subseqüente participação destes produtos de degradação na reação ou como co-catalisadores ou como inibidores. / The Fenton reaction is the name given to the oxidation of iron(II) to iron(III) by hydrogen peroxide, a reaction that produces highly oxidizing species like the hydroxyl radical. In this work, a spectrophotometric methodology is developed to accompany the formation of iron(III) during the initial moments of the Fenton reaction. This methodology was applied to four sets of reactions: (A) the simple Fenton system, containing only iron(II) and H2O2; (B) system A containing isopropanol, a simple substrate that undergoes principally oxidation to acetone; (C) system A containing the catalyst 3,5-di-tert-butyl-catechol (H2DTBCat); (D) system C plus isopropanol, corresponding to the complete catalytic system. For each set of reactions, the concentrations of iron(II) and H2O2 were varied. A kinetic model, based on explicit chemical reactions and their respective rate constants, was developed to simulate the the rate of formation of iron(III) for these four sets of reactions above. Using reactions described in the literature, the model produced simulations that satisfactorily reproduced the experimental data of sets A and B. In the case of sets C and D, however, it was necessary to propose an additional step involving the formation of iron(IV) or ferril, stabilized by complexation with H2DTBCat. Nonetheless, even with the inclusion of this species, the model failed to capture the complexity of the system at high concentrations of peroxide and iron. This failure was attributed to the rapid competitive degradation of H2DTBCat under these conditions, with the subsequent participation of the degradation products in the reaction as either co-catalysts or inhibitors.

Έστω $V$ ένα σύνολο $n$ κορυφών και έστω ${\cal M}$ ένα πεπερασμένα αριθμήσιμο σύνολο $m$ ετικετών. Ένα γράφημα ετικετών προκύπτει αν αντιστοιχήσουμε σε κάθε κορυφή $v \in V$ ένα υποσύνολο $S_v$ του ${\cal M}$ και στη συνέχεια ενώσουμε όποιες κορυφές έχουν κοινά στοιχεία στα αντίστοιχα σύνολα ετικετών τους. Η παρούσα διδακτορική διατριβή ασχολείται με την εξέταση συνδυαστικών ιδιοτήτων και το σχεδιασμό και ανάλυση αλγορίθμων που σχετίζονται με δυο μοντέλα τυχαίων γραφημάτων που προκύπτουν από την επιλογή των συνόλων $S_v$ με βάση συγκεκριμένες κατανομές. Το πρώτο από αυτά τα μοντέλα ονομάζεται \emph{Μοντέλο Τυχαίων Γραφηματων Τομής Ετικετών} ${\cal G}_{n, m, p}$ (\textlatin{random intersection graphs model}) και κάθε σύνολο ετικετών $S_v$ διαμορφώνεται επιλέγοντας ανεξάρτητα κάθε ετικέτα με πιθανότητα $p$. Το δεύτερο μοντέλο ονομάζεται \emph{Ομοιόμορφο Μοντέλο Τυχαίων Γραφηματων Τομής Ετικετών} ${\cal G}_{n, m, \lambda}$ (\textlatin{uniform random intersection graphs model}) και κάθε σύνολο ετικετών $S_v$ επιλέγεται (ανεξάρτητα για κάθε κορυφή) ισοπίθανα ανάμεσα σε όλα τα υποσύνολα του ${\cal M}$ μεγέθους $\lambda$. Τα μοντέλα αυτά μπορούν να χρησιμοποιηθούν για να μοντελοποιήσουν καταστάσεις που αφορούν θέματα ασφάλειας σε δίκτυα αισθητήρων, αλλά και για την αναπαράσταση των συγκρούσεων (\textlatin{conflicts}) που δημιουργούνται σε περιπτώσεις διαμοιρασμού πόρων. Ακόμα, μπορούν να χρησιμοποιηθούν για τη μοντελοποίηση κοινωνικών γραφημάτων (\textlatin{social graphs}) στα οποία δυο οντότητες συνδέονται όταν έχουν κάποιο κοινό χαρακτηριστικό. Στο Μοντέλο Τυχαίων Γραφηματων Τομής Ετικετών ${\cal G}_{n, m, p}$ μελετάμε καταρχήν το πρόβλημα της ύπαρξης κύκλων \textlatin{Hamilton}. Συγκεκριμένα, αποδεικνύουμε ένα άνω φράγμα για την πιθανότητα επιλογής ετικετών $p$ έτσι ώστε κάθε στιγμιότυπο του ${\cal G}_{n, m, p}$ να περιέχει ένα κύκλο \textlatin{Hamilton} με πιθανότητα που τείνει στο 1 καθώς το $n$ τείνει στο άπειρο. Ακόμα, αναλύουμε δυο πιθανοτικούς αλγορίθμους που, για ορισμένες τιμές των παραμέτρων $m, p$ του μοντέλου, καταφέρνουν να κατασκευάσουν ένα κύκλο \textlatin{Hamilton} με πιθανότητα που τείνει στο 1, δηλαδή σχεδόν πάντα. Επίσης, δείχνουμε ότι σχεδόν κάθε στιγμιότυπο του ${\cal G}_{n, m, p}$ έχει καλή επεκτασιμότητα (\textlatin{expansion}), ακόμα και για $p$ πολύ κοντά στο κατώφλι συνεκτικότητας του μοντέλου. Στη συνέχεια, δίνουμε βέλτιστα άνω φράγματα (που ισχύουν με πιθανότητα που τείνει στο 1 σε ένα ευρύ πεδίο τιμών των παραμέτρων του μοντέλου) για σημαντικές ποσότητες που αφορούν τυχαίους περιπάτους σ ε στιγμιότυπα του ${\cal G}_{n, m, p}$ όπως ο χρόνος μίξης (\textlatin{mixing time}) και ο χρόνος κάλυψης (\textlatin{cover time}). Στο Ομοιόμορφο Μοντέλο Τυχαίων Γραφηματων Τομής Ετικετών ${\cal G}_{n, m, \lambda}$ μελετάμε την ύπαρξη κύκλων \textlatin{Hamilton} σε ένα ορισμένο πεδίο τιμών των παραμέτρων $m, \lambda$ του μοντέλου. Τέλος, υπολογίζουμε με τη βοήθεια της Πιθανοτικής Μεθόδου το κατώφλι ύπαρξης ανεξάρτητων συνόλων κορυφών. / Let $V$ be a set of $i$ vertices and let ${\cal M}$ be a finite set of $m$ labels. An intersection graph is then constructed by assigning to each vertex $v \in V$ a subset $S_v$ of ${\cal M}$ and then connecting every pair of vertices that have common labels in their corresponding label sets. This thesis concerns the study of combinatorial properties, as well as the design and analysis of algorithms on two kinds of random intersection graphs models that arise from different choices of the distribution that we use to construct the sets $S_v$. In the first of these models, called \emph{Random Intersection Graphs Model} ${\cal G}_{n, m, p}$, each set of labels $S_v$ is constructed by choosing independently each label with probability $p$. In the second model, called \emph{Uniform Random Intersection Graphs Model} ${\cal G}_{n, m, \lambda}$, each label set $S_v$ is selected equiprobably (and independently for each vertex $v$) among all subsets of ${\cal M}$ of size $\lambda$. These models can be used to abstract situations that concern the efficient and secure communication in sensor networks, but can also be used to model the conflicts that occur in oblivious resource sharing in distributed settings. Moreover, random intersection graph models can be used to model social graphs, in which two entities are connected when they have a common feature. In the Random Intersection Graphs Model ${\cal G}_{n, m, p}$, we first study the existence and efficient construction of Hamilton cycles. More specifically, we give an upper bound for the probability $p$ that is needed for almost every random instance $G_{n, m, p}$ of the model to have a Hamilton cycle. We also present two polynomial time, randomized algorithms for constructing Hamilton cycles in a wide range of the parameters $m, p$. Moreover, we show that almost every random instance of the ${\cal G}_{n, m, p}$ model is an expander, even for $p$ very close to the connectivity threshold. Finally, we give close to optimal bounds (that hold with probability that goes to 1 for a wide range of the parameters of the model) for important quantities (like the mixing time and the cover time) concerning random walks on random instances of ${\cal G}_{n, m, p}$. In the Uniform Random Intersection Graphs Model ${\cal G}_{n, m, \lambda}$ we study the existence of Hamilton cycles for a ce rtain range of the parameters $m, \lambda$. Finally, by using the probabilistic method we compute the independence number of ${\cal G}_{n, m, \lambda}$.

- / -