Thesis (M.S.)--Rochester Institute of Technology, 1994. / Typescript. Includes bibliographical references (leaves 77-80).

Thesis (M.A.)--University of the Western Cape, 2008. / Includes bibliographical references (leaves 81- 82).

[pt] O presente trabalho busca apresentar uma proposta de inclusão de tópicos elementares da teoria de Grafos, com destaque para os Grafos Eulerianos, na educação básica. Iniciamos com uma introdução a essa teoria destacando algumas definições importantes que fundamentam o trabalho além de concepções teóricas relevantes para tratar da questão específica dos Grafos Eulerianos. Posteriormente, algumas sugestões de atividades sobre o tema, que podem ser aplicadas em qualquer nível da educação básica desde o Ensino Fundamental até o Ensino Médio, são apresentadas com o intuito de auxiliar e inspirar o professor desse segmento que esteja interessado em utilizar novas propostas na sua prática pedagógica. Assim, esse profissional pode se valer do presente trabalho como um recurso motivador para novas construções ou simplesmente adaptá-lo, alterá-lo e/ou utilizá-lo na realidade da sua sala de aula. Algumas das atividades propostas foram aplicadas com alunos do sétimo ano de uma escola pública do Rio de Janeiro e a metodologia e avaliação desta aplicação encontram-se também descritas no presente estudo. Desta forma, pretende-se promover uma reflexão sobre novas estratégias que incrementem o processo de ensino-aprendizagem da Matemática na busca de uma educação Matemática mais autônoma e mais significativa. / [en] This paper seeks to show a proposal of inclusion of elementary topics of Graphs theory, with emphasis in Eulerian graphs, on basic school. We begin with an introduction to this theory highlighting some important definitions which underpin this paper beyond relevant theoretical conceptions to deal with the specific issue of Eulerian graphs. In addition, some suggestions of activities on the subject, which can be applied in any level of basic education, from Elementary to High School, are presented with the intention of help teachers interested in using new proposals on their pedagogical practice. So they can use this material as a motivating resource for new constructions or just adapt it, change it and/or use it in his classroom routine. Some of the proposed activities were applied with seventh year students from a public school of Rio de Janeiro and the methodology and evaluation of this application are also described on this present work. Therefore it is intended to promote a reflection about new strategies that increase the teaching-learning process of Mathematics in the searching for more autonomy and more meaningful mathematical education.

Submitted by ANDRÉ MENDES CARDOSO SEQUEIRA null (mendes.galan@gmail.com) on 2016-09-26T01:51:44Z No. of bitstreams: 1 diss-andre.pdf: 38256046 bytes, checksum: b968c7253ff683e751216580ba92aa56 (MD5) / Approved for entry into archive by Felipe Augusto Arakaki (arakaki@reitoria.unesp.br) on 2016-09-27T16:24:19Z (GMT) No. of bitstreams: 1 sequeira_amc_me_rcla.pdf: 38256046 bytes, checksum: b968c7253ff683e751216580ba92aa56 (MD5) / Made available in DSpace on 2016-09-27T16:24:19Z (GMT). No. of bitstreams: 1 sequeira_amc_me_rcla.pdf: 38256046 bytes, checksum: b968c7253ff683e751216580ba92aa56 (MD5) Previous issue date: 2016-08-30 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / Neste trabalho verificamos as dificuldades apresentadas pelos alunos da E.E. Romeu de Moraes com relação às representações gráficas. Quando questionados sobre o porquê desta deficiência, foi difícil obter clareza sobre os fatos que os impedem a trabalhar com os gráficos. De maneira geral, nesta escola, os alunos argumentaram que viram poucas vezes o uso desta linguagem e que o uso de tabelas era mais frequente. Precisamos reverter esta situação, mostrando as vantagens que a comunicação via gráfico nos traz, pois dele podemos retirar informações importantes na solução de problemas. Ao longo desta dissertação mostraremos alguns conteúdos propostos para o 3° ano de Ensino Médio (estudo dos coeficientes de uma reta, análise das taxas de variação para a função afim e gráficos estatísticos buscando as medidas de tendência central) e retomaremos outros (par ordenado, plano cartesiano, razão, porcentagem, gráficos de setores, gráfico de barras, histograma e gráfico de linhas). Na maior parte destes assuntos, a representação gráfica ocorre e procuramos oferecê-la aos estudantes de diversas maneiras, seja construindo gráficos, seja observando-os e interpretando-os ou ainda, coletando dados para resolver os problemas propostos. Não pretendemos dar conta de todas as dificuldades apresentadas pelo corpo discente, mas apresentaremos algumas sugestões de atividades que podem facilitar o aprendizado dos mesmos. / In this work we analyze some difficulties when dealing with graphs which were presented by the students from E.E. Romeu de Moraes (São Paulo/SP). When we ask for the reason of this deficiency, it is difficult to get clear on the facts that prevent them working with graphics. In general, the students confirm that very rarely they make use of this feature and also say that dealing with tables is more common. We can change this situation showing the advantages which graphs communication brings to us, because it can derive important information for troubleshooting. Throughout this dissertation we show some proposed content for the 3rd year of high school (the study of coefficients of a straight line, analysis of growth rates for the statistical function and graphs seeking the central tendency) and other subjects (ordered pair, Cartesian plane, ratio, percentage, pie charts, bar graph, histogram and line graph). In most of these issues, the graphical representation occurs and we try to offer it to students in many ways, even drawing graphic, analyzing and interpreting it, or collecting data to solve the problems proposed. We do not intend to solve all the difficulties presented by the students, but we bring some suggestions for activities that can make learning easier to them.

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

Neste projeto inicia-se o estudo de classificação de aplicações estáveis. Para isto usamos grafos que irão corresponder ao conjunto singular destas aplicações. Em um primeiro momento estudamos o caso de aplicações estáveis de superfícies no plano e depois estudamos aplicações estáveis de 3-variedades em \'R POT. 3\' / In this project we began the study of classification of stable maps. For this we use graphs that correspond to the singular set of these applications. At first we study the case of stable maps of surfaces in the plane and then we study stable maps of a 3-manifold in \'R POT. 3\'

Given a hyperbolic surface, the set of all closed geodesics whose length is minimal form a graph on the surface, in fact a so called fat graph, which we call the systolic graph. The central question that we study in this thesis is: which fat graphs are systolic graphs for some surface -we call such graphs admissible. This is motivated in part by the observation that we can naturally decompose the moduli space of hyperbolic surfaces based on the associated systolic graphs. A systolic graph has a metric on it, so that all cycles on the graph that correspond to geodesics are of the same length and all other cycles have length greater than these. This can be formulated as a simple condition in terms of equations and inequations for sums of lengths of edges. We call this combinatorial admissibility. Our first main result is that admissibility is equivalent to combinatorial admissibility. This is proved using properties of negative curvature, specifically that polygonal curves with long enough sides, in terms of a lower bound on the angles, are close to geodesics. Using the above result, it is easy to see that a subgraph of an admissible graph is admissible. Hence it suffices to characterize minimal non-admissible fat graphs. Another major result of this thesis is that there are infinitely many minimal non-admissible fat graphs (in contrast, for instance, to the classical result that there are only two minimal non-planar graphs).

The classical graph edge coloring problem deals in coloring the edges of a given graph with minimum number of colors such that no two adjacent edges in the graph, get the same color in the proposed coloring. In the following work, we look at the other end of the spectrum where in our goal is to maximize the number of colors used for coloring the edges of the graph under some vertex specific constraints. We deal with the MAXIMUM EDGE COLORING problem which is defined as the following –For an integer q ≥2 and a graph G, the goal is to find a coloring of the edges of G with the maximum number of colors such that every vertex of the graph sees at most q colors. The question is very well motivated by the problem of channel assignment in wireless networks. This problem is NP-hard for q ≥ 2, and has been well-studied from the point of view of approximation. This problem has not been studied in the parameterized context before. Hence as a next step, this thesis investigates the parameterized complexity of this problem where the standard parameter is the solution size. The main focus of the work is the special case of q=2 ,i.e. MAXIMUM EDGE 2-COLORING which is theoretically intricate and practically relevant in the wireless networks setting. We first show an exponential kernel for the MAXIMUM EDGE q-COLORING problem where q is a fixed constant and q ≥ 2.We do a more specific analysis for the kernel of the MAXIMUM EDGE 2-COLORING problem. The kernel obtained here is still exponential in size but is better than the kernel obtained for MAXIMUM EDGE q-COLORING problem in case of q=2. We then show a fixed parameter tractable algorithm for the MAXIMUM EDGE 2-COLORING problem with a running time of O*∗(kO(k)).We also show a fixed parameter tractable algorithm for the MAXIMUM EDGE q-COLORING problem with a running time of O∗(kO(qk) qO(k)). The fixed parameter tractability of the dual parametrization of the MAXIMUM EDGE 2-COLORING problem is established by arguing a linear vertex kernel for the problem. We also show that the MAXIMUM EDGE 2-COLORING problem remains hard on graphs where the maximum degree is a constant and also on graphs without cycles of length four. In both these cases, we obtain quadratic kernels. A closely related variant of the problem is the question of MAX EDGE{1,2-}COLORING. For this problem, the vertices in the input graph may have different qε,{1.2} values and the goal is to use at least k colors for the edge coloring of the graph such that every vertex sees at most q colors, where q is either one or two. We show that the MAX EDGE{1,2}-COLORING problem is W[1]-hard on graphs that have no cycles of length four.

This thesis is about graph-indexed random walks, Lipschitz mappings and graph homo- morphisms. It discusses connections between these notions, surveys the existing results, and shows new results. Graph homomorphism is an adjacency-preserving mapping between two graphs. Our main objects of study are graph homomorphisms to an infinite path. We are interested in two parameters: maximum range and average range. The average range of a graph is the expected size of the image of a uniformly picked random homomorphism to an infinite path. We obtain formulas for several graph classes and investigate main conjectures on this parameter. For maximum range parameter we show a general formula and an algorithm to compute it for general graphs. Besides that, we study the problem of extending a prescribed partial graph homomorphism to a full graph homomorphism. We show that this problem is polynomial in some cases. 1

M.Sc. / Within the field of Graph Theory the many ways in which graphs can be coloured have received a lot of attention over the years. T.R. Jensen and B. Toft provided a summary in [8] of the most important results and research done in this field. These results were cited by R. Diestel in [5] as “The Four Colour Problem” wherein it is attempted to colour every map with four colours in such a way that adjacent countries will be assigned different colours. This was first noted as a problem by Francis Guthrie in 1852 and later, in 1878, by Cayley who presented it to the London Mathematical Society. In 1879 Kempe published a proof, but it was incorrect and lead to the adjustment by Heawood in 1890 to prove the five colour theorem. In 1977 Appel and Haken were the first to publish a solution for the four colour problem in [2] of which the proof was mostly based on work done by Birkhoff and Heesch. The proof is done in two steps that can be described as follows: firstly it is shown that every triangulation contains at least one of 1482 certain “unavoidable configurations” and secondly, by using a computer, it is shown that each of these configurations is “reducible”. In this context the term “reducible” is used in the sense that any plane triangulation containing such a configuration is 4-colourable by piecing together 4- colourings of smaller plane triangulations. These two steps resulted in an inductive proof that all plane triangulations and therefore all planar graphs are 4-colourable.