Thesis (Ph.D.) - Carleton University, 2002. / Includes bibliographical references (p. 98-100). Also available in electronic format on the Internet.

A labeling of a graph G is said to be r-distinguishing if no automorphism of G preserves all of the vertex labels. The smallest such number r for which there is an r-distinguishing labeling on G is called the distinguishing number of G. The distinguishing set of a group Gamma, D(Gamma), is the set of distinguishing numbers of graphs G in which Aut(G) = Gamma. It is shown that D(Gamma) is non-empty for any finite group Gamma. In particular, D(D_n) is found where D_n is the dihedral group with 2n elements. From there, the generalized Petersen graphs, GP(n,k), are defined and the automorphism groups and distinguishing numbers of such graphs are given. / Master of Science

Many models in the physical and life sciences formulated as dynamical systems have a positive steady state, with the local behavior of this steady state determined by the eigenvalues of its Jacobian matrix. The first part of this thesis is concerned with analyzing the linear stability of the steady state by using sign patterns, which are matrices with entries from the set {+,-,0}. The linear stability is related to the allowed refined inertias of the sign pattern of the Jacobian matrix of the system, where the refined inertia of a matrix is a 4-tuple (n+, n_-, ; nz; 2np) with n+ (n_) equal to the number of eigenvalues with positive (negative) real part, nz equal to the number of zero eigenvalues, and 2np equal to the number of nonzero pure imaginary eigenvalues. This type of analysis is useful when the parameters of the model are of known sign but unknown magnitude. The usefulness of sign pattern analysis is illustrated with several biological examples, including biochemical reaction networks, predator{prey models, and an infectious disease model. The refined inertias allowed by sign patterns with specific digraph structures have been studied, for example, for tree sign patterns. In the second part of this thesis, such results on refined inertias are extended by considering sign and zero-nonzero patterns with digraphs isomorphic to strongly connected orientations of the Petersen graph. / Graduate

Philosophiae Doctor - PhD / The history of the pursuit of uncolourable cubic graphs dates back more than a century. This pursuit has evolved from the slow discovery of individual uncolourable cubic graphs such as the famous Petersen graph and the Blanusa snarks, to discovering in nite classes of uncolourable cubic graphs such as the Louphekine and Goldberg snarks, to investigating parameters which measure the uncolourability of cubic graphs. These parameters include resistance, oddness and weak oddness, ow resistance, among others. In this thesis, we consider current ideas and problems regarding the uncolourability of cubic graphs, centering around these parameters. We introduce new ideas regarding the structural complexity of these graphs in question. In particular, we consider their 3-critical subgraphs, speci cally in relation to resistance. We further introduce new parameters which measure the uncolourability of cubic graphs, speci cally relating to their 3-critical subgraphs and various types of cubic graph reductions. This is also done with a view to identifying further problems of interest. This thesis also presents solutions and partial solutions to long-standing open conjectures relating in particular to oddness, weak oddness and resistance.

Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2017-09-22T11:27:19Z No. of bitstreams: 2 Dissertação - Kariny de Andrade Dirino - 2017.pdf: 1986993 bytes, checksum: fd843aaf3aee361fd3b4dd512828d8f0 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2017-09-22T11:27:47Z (GMT) No. of bitstreams: 2 Dissertação - Kariny de Andrade Dirino - 2017.pdf: 1986993 bytes, checksum: fd843aaf3aee361fd3b4dd512828d8f0 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2017-09-22T11:27:47Z (GMT). No. of bitstreams: 2 Dissertação - Kariny de Andrade Dirino - 2017.pdf: 1986993 bytes, checksum: fd843aaf3aee361fd3b4dd512828d8f0 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2017-08-28 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / Considering a layered directed graphs we may associate it to an algebra, denoted as , whose generators are the edges of the graph and the relations are defined through: every ways with the same initial vertex and the same final vertex determine different fractorizations for the same polynomial with coefficients in a non-commutative ring. We present a study about these algebras and their main properties, presenting some classes of examples and having as central focus the Hasse graph of the partially ordered set of k -faces of Petersen graph, . We discuss the results on basis for algebras of type we calculate their Hilbert series and the automorphisms group of these algebras, we determine the subgraphs induced by the set of vertices fixed by each and we calculate the graded trace generating functions, in order to introduce problems related to koszulity. / Dado um grafo orientado em níveis podemos associar a ele uma álgebra, denotada por cujos geradores são as arestas do grafo e as relações são definidas mediante: todos os caminhos com o mesmo vértice inicial e mesmo vértice final determinam fatorações distintas para o mesmo polinômio com coeficientes em um anel não comutativo. Exibimos um estudo sobre essas álgebras e suas principais propriedades, apresentando algumas classes de exemplos e tendo como foco central o grafo de Hasse do conjunto parcialmente ordenado das k-faces do grafo de Petersen, . Abordamos resultados sobre bases para álgebras do tipo , calculamos as suas séries de Hilbert e o grupo dos automorfismos dessas álgebras, determinamos os subgrafos induzidos pelo conjunto dos vértices fixados por cada e calculamos as funções geradoras do traço graduado, a fim de introduzirmos problemas relacionados à koszulidade.

Dans cette thèse, nous nous intéressons à differentes colorations des sommets d’un graphe et aux homomorphismes de graphes. Nous nous intéressons plus spécialement aux graphes planaires et aux graphes peu denses. Nous considérons la coloration propre des sommets, la coloration acyclique, la coloration étoilée, lak-forêt-coloration, la coloration fractionnaire et la version par liste de la plupart de ces concepts.Dans le Chapitre 2, nous cherchons des conditions suffisantes de 3-liste colorabilité des graphes planaires. Ces conditions sont exprimées en termes de sous-graphes interdits et nos résultats impliquent plusieurs résultats connus.La notion de la coloration acyclique par liste des graphes planaires a été introduite par Borodin, Fon-Der Flaass, Kostochka, Raspaud, et Sopena. Ils ont conjecturé que tout graphe planaire est acycliquement 5-liste coloriable. Dans le Chapitre 3, on obtient des conditions suffisantes pour qu’un graphe planaire admette une k-coloration acyclique par liste avec k 2 f3; 4; 5g.Dans le Chapitre 4, nous montrons que tout graphe subcubique est 6-étoilé coloriable.D’autre part, Fertin, Raspaud et Reed ont montré que le graphe de Wagner ne peut pas être 5-étoilé-coloriable. Ce fait implique que notre résultat est optimal. De plus, nous obtenons des nouvelles bornes supérieures sur la choisissabilité étoilé d’un graphe planaire subcubique de maille donnée.Une k-forêt-coloration d’un graphe G est une application ¼ de l’ensemble des sommets V (G) de G dans l’ensemble de couleurs 1; 2; ¢ ¢ ¢ ; k telle que chaque classede couleur induit une forêt. Le sommet-arboricité de G est le plus petit entier ktel que G a k-forêt-coloration. Dans le Chapitre 5, nous prouvons une conjecture de Raspaud et Wang affirmant que tout graphe planaire sans triangles intersectants admet une sommet-arboricité au plus 2.Enfin, au Chapitre 6, nous nous concentrons sur le problème d’homomorphisme des graphes peu denses dans le graphe de Petersen. Plus précisément, nous prouvons que tout graphe sans triangles ayant un degré moyen maximum moins de 5=2 admet un homomorphisme dans le graphe de Petersen. En outre, nous montrons que la borne sur le degré moyen maximum est la meilleure possible. / In this thesis, we are interested in various vertex coloring and homomorphism problems of graphs with special emphasis on planar graphs and sparsegraphs. We consider proper vertex coloring, acyclic coloring, star coloring, forestcoloring, fractional coloring and the list version of most of these concepts.In Chapter 2, we consider the problem of finding sufficient conditions for a planargraph to be 3-choosable. These conditions are expressed in terms of forbiddensubgraphs and our results extend several known results.The notion of acyclic list coloring of planar graphs was introduced by Borodin,Fon-Der Flaass, Kostochka, Raspaud, and Sopena. They conjectured that everyplanar graph is acyclically 5-choosable. In Chapter 3, we obtain some sufficientconditions for planar graphs to be acyclically k-choosable with k 2 f3; 4; 5g.In Chapter 4, we prove that every subcubic graph is 6-star-colorable. On theother hand, Fertin, Raspaud and Reed showed that the Wagner graph cannot be5-star-colorable. This fact implies that our result is best possible. Moreover, weobtain new upper bounds on star choosability of planar subcubic graphs with givengirth.A k-forest-coloring of a graph G is a mapping ¼ from V (G) to the set f1; ¢ ¢ ¢ ; kgsuch that each color class induces a forest. The vertex-arboricity of G is the smallestinteger k such that G has a k-forest-coloring. In Chapter 5, we prove a conjecture ofRaspaud and Wang asserting that every planar graph without intersecting triangleshas vertex-arboricity at most 2.Finally, in Chapter 6, we focus on the homomorphism problems of sparse graphsto the Petersen graph. More precisely, we prove that every triangle-free graph withmaximum average degree less than 5=2 admits a homomorphism to the Petersengraph. Moreover, we show that the bound on the maximum average degree in ourresult is best possible.