In this thesis, we are concerned with finite simple graphs. Given a subset $S$ of $\{3,4,\ldots,2n-1\}$, the additive graph generated by $S$ has vertex set $V=[n]$ and edge set $E$, with $(i,j) \in E$ if and only if $i+j \in S$. The focus of this thesis is the relationship between generating sets $S$ and monotone properties in the corresponding graphs. We make the first known investigation of the \textit{Traversal by Prime Sum Problem}, in which the set $S$ is the prime numbers and the property of interest is a Hamilton cycle. A number of new results are proved concerning both these graphs and the additive graphs for which the set $S$ is the practical numbers.\\ For any subset $S$ of $\{3,4,\ldots,2n-1\}$, we prove that the $|S|$-closure of the additive graph generated by $S$ is the complete graph; this allows for the determination of tight thresholds for a number of monotone properties in terms of $|S|$ using results from closure theory. These graphs are shown to be the first known wide-ranging and representative subclass of graphs with complete $k$-closure, and they afford a new and simple construction of minimum graphs with complete $k$-closure. Finally, as an example of the number-theoretic interpretations of these graphs and their properties, we generalize a theorem by Cramer concerning prime numbers to a number of different sequences. / \'tant donn\'{e} un sous-ensemble $S$ de $\{3,4,\ldots,2n-1\}$, le graphe additif engendr\' par $S$ a un ensemble de sommets $V=[n]$ et un ensemble d'arr\^tes $E$, telle que $(i,j) \in E$ si et seulement si $i+j \in S$. L'objectif de cette th\`se est l'\'{e}tude des relations entre l'ensemble $S$ et les propri\'t\'{e}s monotones du graphe additif correspondant. On effectue les premi\`{e}res recherches connue sur le \textit{Traversal By Prime Sum Problem}, probl\`{e}me dans lequel l'ensemble $S$ correspond \`{a} l'ensemble des nombres premiers et la propri\'t\'{e} de graphe recherch\'e est l'existence d'un cycle hamiltonien. De nouveaux r\'{e}sultats sont \'tablis pour ce probl\`me ainsi que dans le cas o\` $S$ est l'ensemble des entiers pratiques.\\ Pour un tel $S$ quelconque, on d\'{e}montre que la $|S|$-fermeture du graphe additif engendr\' par $S$ est un graphe complet. Ainsi, en utilisant les r\'{e}sultats de la th\'orie de la fermeture on parvient \` d\'{e}terminer le seuil pour plusieurs propri\'t\'{e}s monotones des graphes en terme de $|S|$. Ces graphes sont les premiers repr\'sentant connus d'une large sous-classe de graphe $k$-ferm\'{e}s complets. Ils permettent de donner une construction nouvelle et simple de graphe ferm\'s et complets minimaux. Enfin, comme exemple d'interpr\'{e}tation arithm\'tique de ces graphes et de leurs propri\'{e}t\'s, on g\'{e}n\'ralise un th\'{e}or\`{e}me de Cramer sur les nombres premiers \`{a} d'autres suites d'entiers.
| Identifer | oai:union.ndltd.org:LACETR/oai:collectionscanada.gc.ca:QMM.21911 |
| Date | January 2008 |
| Creators | Costain, Gregory |
| Contributors | Adrian Roshan Vetta (Internal/Supervisor) |
| Publisher | McGill University |
| Source Sets | Library and Archives Canada ETDs Repository / Centre d'archives des thèses électroniques de Bibliothèque et Archives Canada |
| Language | English |
| Detected Language | English |
| Type | Electronic Thesis or Dissertation |
| Format | application/pdf |
| Coverage | Master of Science (Department of Mathematics and Statistics) |
| Rights | All items in eScholarship@McGill are protected by copyright with all rights reserved unless otherwise indicated. |
| Relation | Electronically-submitted theses. |
Page generated in 0.0015 seconds