We investigate here some aspects of cycle bases of undirected graphs that allow the iterative construction of all elementary cycles. We introduce the concept of quasi-robust bases as a generalization of the notion of robust bases and demonstrate that a certain class of bases of the complete bipartite graphs K m,n with m,n _> 5 is quasi-robust but not robust. We furthermore disprove a conjecture for cycle bases of Cartesian product graphs.

The Rodokmen (Family tree) environment is one of the many envirnments listed in Fraus publishing house textbooks based on the RVP pro ZV (The Framework Educatinal Programme for Basic Education). The environment offers a tool for building of the mathematical schema of terms and their inter-realations as well as the development of the logical thought. In the theorethicl part of this Diploma thesis the relationship of the Rodokmen environment to the RVP pro ZV is being explained, basic mathematical and geneaologic terminology is stated. In this part of the thesis I also explain the relations in the set cocncept, clasify the family relationships and adress the methodology of the age example solving. In the practical part of the thesis I - by the way of experiment - determine how and in what context students understand the stated mathematical terms, the way they apply the understanding in order to solv the relation and age exams or problems, where the numeric operations take place.

Made available in DSpace on 2016-04-27T16:57:50Z (GMT). No. of bitstreams: 1 EDM - Vera Lucia da Silva.pdf: 1384460 bytes, checksum: 3234ebd8c11c96412594a6df13e184cf (MD5) Previous issue date: 2006-11-16 / Secretaria da Educação do Estado de São Paulo / This research is about a teaching project aiming at mastering abilities and concepts related to the solution of problems of Cartesian product. The selected population were students of 4th Grade from a State School in the eastern region of the city of São Paulo. Our reference is the G. Vergnaud Conceptual Fields Theory and we took in consideration theoretical elements from researchers interested in studying the multiplicative reasoning. Data were collected from continuous observation and evaluation of the students performance, from the analyses of the materials produced by them and from interviews. The activities were designed with the intent of establishing connections between adding and multiplying processes and the processes involved in the determination of all the pairs of the Cartesian product. These connections become evident when represented by means of spatial relations promoting the evolution of non-conventional representations, produced by the students, to conventional representations, in Cartesian graphics and tree diagrams. The major contributions of this research for understanding the cognitive operations involved in solving Cartesian product problems are the repertory of non-conventional processes, employed by the selected group of participants, and their justification, and the analyses of the phenomena that occur in the passage from one to the other of the different representations of the Cartesian product. This research also offers contribution for the training of elementary education teachers / Nesta pesquisa, desenvolvemos uma proposta de ensino voltada ao domínio de competências e conceitos, relativos à resolução de problemas de multiplicação cartesiana. A população selecionada foi constituída por alunos de uma classe de 4a série do Ensino Fundamental, de uma Escola Estadual localizada da zona leste do Estado de São Paulo. Tomamos como referência a Teoria dos Campos Conceituais, de G. Vergnaud, e consideramos elementos teóricos de pesquisadores que desenvolvem pesquisas sobre o pensamento multiplicativo. Os dados foram obtidos por meio de registro e avaliação contínua do comportamento dos alunos no desenvolvimento das atividades, da análise do material produzido por eles e de entrevistas, entre outros. No desenvolvimento das atividades, buscamos estabelecer conexões entre procedimentos aditivos e multiplicativos e os processos envolvidos na determinação de todos os pares do produto cartesiano. Essas conexões foram ressaltadas ao serem representadas por meio de relações espaciais, promovendo a evolução de representações não convencionais, produzidas pelos alunos, para representações convencionais, em gráficos cartesianos e de árvore . Como principais contribuições desta pesquisa para a compreensão das operações cognitivas envolvidas na resolução de problemas de produto cartesiano, ressalte-se: o levantamento de um repertório de procedimentos não convencionais empregados pela classe selecionada e suas justificativas, a análise de fenômenos ocorridos na passagem de uma para outra das diferentes representações do produto cartesiano. A pesquisa oferece, igualmente, contribuições para a formação de professores do ensino fundamental

Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2018-03-16T10:48:35Z No. of bitstreams: 2 Dissertação - Juliana Paula Félix - 2018.pdf: 1739140 bytes, checksum: 14e7528cefac5d3322e49131936f3c86 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2018-03-16T10:49:04Z (GMT) No. of bitstreams: 2 Dissertação - Juliana Paula Félix - 2018.pdf: 1739140 bytes, checksum: 14e7528cefac5d3322e49131936f3c86 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2018-03-16T10:49:04Z (GMT). No. of bitstreams: 2 Dissertação - Juliana Paula Félix - 2018.pdf: 1739140 bytes, checksum: 14e7528cefac5d3322e49131936f3c86 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2018-02-19 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / In this work, we investigate the problem of finding identifying codes of minimum size in a variety of graph classes, such as trees corona products, Cartesian products and complementary prisms. For caterpillar trees, we show the minimum size of an identifying code on complete caterpillars, brooms and double brooms. We also prove a sharp upper bound for the general case. For coronas $K_n \circ \overline{K}_m$, we prove what is the minimum size of an identifying code. We demonstrate a sharp upper bound for an identifying code of the Cartesian product of a star and a path $K_{1,n} \square P_m$ and, when $n=3$, we conjecture that the limit proposed is minimum. We also find the minimum cardinality of an identifying code in the complementary prism of complete bipartite graphs and complete split graphs, among with other results: we demonstrate that the complementary prism graph $G\overline{G}$ is identifiable if, and only if, $G$ has at least two vertices; we find what is the smallest size possible of an identifying code of complementary prisms; we prove a sharp upper bound for an identifying code of the complementary prism $G\overline{G}$ of a connected graph $G$, showing that the set $C = V(G)$ is an identifying code with the size proposed and, finally, we determine the size of a minimum identifying code of the complementary prism of a complete bipartite graph, showing that it is an example of a graph that attains our upper bound. / Neste trabalho, investigamos o problema de se encontrar códigos identificadores de cardinalidade mínima em diversas classes de grafos, tais como árvores, produtos coronas, produtos Cartesianos e prismas complementares. Para árvores caterpillar, determinamos a cardinalidade mínima de um código identificador em caterpillars completo, grafos broom e broom duplo, e provamos um limite superior justo para caterpillars gerais. Para coronas, determinamos a cardinalidade mínima de um código identificador em $K_n \circ \overline{K}_m$. Para produtos Cartesianos, investigamos códigos identificadores em grafos $K_{1,n} \square P_m$, definimos um limite superior justo para o caso em que $n=3$ e um limite superior mais abrangente para o caso em que $n \geq 3$. Quando $n=3$, conjecturamos que o limite proposto é mínimo. Para prismas complementares de grafos, encontramos o tamanho de um código identificador mínimo em grafos bipartidos completos e grafos split completos. Para prismas complementares, obtivemos ainda outros resultados: demonstramos que um grafo prisma complementar $G\overline{G}$ é identificável se, e somente se, a ordem de $G$ é pelo menos dois; definimos o menor tamanho possível de um código identificador em um grafo $G\overline{G}$; determinamos um limite superior justo para o código identificador de um grafo conexo, mostrando também que seu conjunto de vértices é um conjunto identificador com o tamanho proposto e, finalmente, mostramos que o grafo bipartido completo é um exemplo de grafo que atinge a igualdade do limite superior apresentado.

This thesis discusses colouring, circular list colouring and adapted game colouring of graphs. For colouring, this thesis obtains a sufficient condition for a planar graph to be 3-colourable. Suppose G is a planar graph. Let H_G be the graph with vertex set V (H_G) = {C : C is a cycle of G with |C| ∈ {4, 6, 7}} and edge set E(H_G) = {CiCj : Ci and Cj have edges in common}. We prove that if any 3-cycles and 5-cycles are not adjacent to i-cycles for 3 ≤ i ≤ 7, and H_G is a forest, then G is 3-colourable. For circular consecutive choosability, this thesis obtains a basic relation among chcc(G), X(G) and Xc(G) for any finite graph G. We show that for any finite graph G, X(G) − 1 ≤ chcc(G) < 2 Xc(G). We also determine the value of chcc(G) for complete graphs, trees, cycles, balanced complete bipartite graphs and some complete multi-partite graphs. Upper and lower bounds for chcc(G) are given for some other classes of graphs. For adapted game chromatic number, this thesis studies the adapted game chromatic number of various classes of graphs. We prove that the maximum adapted game chromatic number of trees is 3; the maximum adapted game chromatic number of outerplanar graphs is 5; the maximum adapted game chromatic number of partial k-trees is between k + 2 and 2k + 1; and the maximum adapted game chromatic number of planar graphs is between 6 and 11. We also give upper bounds for the Cartesian product of special classes of graphs, such as the Cartesian product of partial k-trees and outerplanar graphs, or planar graphs.

Submitted by Cássia Santos (cassia.bcufg@gmail.com) on 2017-01-02T14:12:29Z No. of bitstreams: 2 Dissertação - Eduardo Silva Lira - 2016.pdf: 6831540 bytes, checksum: 4fe7b9bd7a7a3584d1cb48239b390f70 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2017-01-03T09:39:46Z (GMT) No. of bitstreams: 2 Dissertação - Eduardo Silva Lira - 2016.pdf: 6831540 bytes, checksum: 4fe7b9bd7a7a3584d1cb48239b390f70 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2017-01-03T09:39:46Z (GMT). No. of bitstreams: 2 Dissertação - Eduardo Silva Lira - 2016.pdf: 6831540 bytes, checksum: 4fe7b9bd7a7a3584d1cb48239b390f70 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2016-12-01 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / From Carathéodory’s theorem arises the definition of the Carathéodory number for graphs. This number is well-known for monophonic and triangle-path convexities. It is limited for some classes of graphs on P3 and geodesic convexities but is known to be unlimited only on P3-convexity. Driven by open questions in geodesic convexity, in this work we study the Carathéodory number in this convexity. For general graphs and cartesian product, we prove that the Carathéodory number is unlimited. We characterize the Carathéodory number for trees, cographs, for the complementary prisms of cographs and simple graphs Kn, Pn and Cn, for the complement and the complementary prism of the graph KnKn and for the cartesian products PnxPm, KnxKm and PnxKm. / Do Teorema de Carathéodory da geometria surge a definição do número de Carathéodory para grafos. Este número é bem determinado na convexidade monofônica e na convexidade de caminho de triângulos. Ele é limitado para algumas classes de grafos nas convexidades P3 e geodésica, mas só foi provado ser ilimitado na convexidade P3. Motivados pelas questões em aberto na convexidade geodosésica, neste trabalho estudamos o número de Carathéodory nesta convexidade. Para grafos gerais e para produtos cartesianos, provamos que o número de Carathéodory é ilimitado. Determinamos o número de Carathéodory para árvores, cografos, para o prisma complementar de cografos e dos grafos simples Kn, Pn e Cn, para o complemento e prisma complementar do grafo KnKn e para os produtos cartesianos PnxPm, KnxKm e PnxKm.

The concept of \emph{proper connection number} of graphs is an extension of proper colouring and is motivated by rainbow connection number of graphs. Let $G$ be an edge-coloured graph. Andrews et al.\cite{Andrews2016} and, independently, Borozan et al.\cite{Borozan2012} introduced the concept of proper connection number as follows: A coloured path $P$ in an edge-coloured graph $G$ is called a \emph{properly coloured path} or more simple \emph{proper path} if two any consecutive edges receive different colours. An edge-coloured graph $G$ is called a \emph{properly connected graph} if every pair of vertices is connected by a proper path. The \emph{proper connection number}, denoted by $pc(G)$, of a connected graph $G$ is the smallest number of colours that are needed in order to make $G$ properly connected. Let $k\geq2$ be an integer. If every two vertices of an edge-coloured graph $G$ are connected by at least $k$ proper paths, then $G$ is said to be a \emph{properly $k$-connected graph}. The \emph{proper $k$-connection number} $pc_k(G)$, introduced by Borozan et al. \cite{Borozan2012}, is the smallest number of colours that are needed in order to make $G$ a properly $k$-connected graph. The aims of this dissertation are to study the proper connection number and the proper 2-connection number of several classes of connected graphs. All the main results are contained in Chapter 4, Chapter 5 and Chapter 6. Since every 2-connected graph has proper connection number at most 3 by Borozan et al. \cite{Borozan2012} and the proper connection number of a connected graph $G$ equals 1 if and only if $G$ is a complete graph by the authors in \cite{Andrews2016, Borozan2012}, our motivation is to characterize 2-connected graphs which have proper connection number 2. First of all, we disprove Conjecture 3 in \cite{Borozan2012} by constructing classes of 2-connected graphs with minimum degree $\delta(G)\geq3$ that have proper connection number 3. Furthermore, we study sufficient conditions in terms of the ratio between the minimum degree and the order of a 2-connected graph $G$ implying that $G$ has proper connection number 2. These results are presented in Chapter 4 of the dissertation. In Chapter 5, we study proper connection number at most 2 of connected graphs in the terms of connectivity and forbidden induced subgraphs $S_{i,j,k}$, where $i,j,k$ are three integers and $0\leq i\leq j\leq k$ (where $S_{i,j,k}$ is the graph consisting of three paths with $i,j$ and $k$ edges having an end-vertex in common). Recently, there are not so many results on the proper $k$-connection number $pc_k(G)$, where $k\geq2$ is an integer. Hence, in Chapter 6, we consider the proper 2-connection number of several classes of connected graphs. We prove a new upper bound for $pc_2(G)$ and determine several classes of connected graphs satisfying $pc_2(G)=2$. Among these are all graphs satisfying the Chv\'tal and Erd\'{o}s condition ($\alpha({G})\leq\kappa(G)$ with two exceptions). We also study the relationship between proper 2-connection number $pc_2(G)$ and proper connection number $pc(G)$ of the Cartesian product of two nontrivial connected graphs. In the last chapter of the dissertation, we propose some open problems of the proper connection number and the proper 2-connection number.