Thesis (M.S.)--Boise State University, 2010. / Title from t.p. of PDF file (viewed July 30, 2010). Includes abstract. Includes bibliographical references (leaf 55).

Thesis (M. Sc.)--University of Canterbury, 2008. / Typescript (photocopy). Includes bibliographical references (p. 118-119). Also available via the World Wide Web.

This dissertation has three principal components. The first component is about the connections between the dimension of posets and the size of matchings in comparability and incomparability graphs. In 1951, Hiraguchi proved that for any finite poset P, the dimension of P is at most half of the number of points in P. We develop some new inequalities for the dimension of finite posets. These inequalities are then used to bound dimension in terms of the maximum size of matchings. We prove that if the dimension of P is d and d is at least 3, then there is a matching of size d in the comparability graph of P, and a matching of size d in the incomparability graph of P. The bounds in above theorems are best possible, and either result has Hiraguchi's theorem as an immediate corollary. In the second component, we focus on an extremal graph theory problem whose solution relied on the construction of a special kind of posets. In 1959, Paul Erdos, in a landmark paper, proved the existence of graphs with arbitrarily large girth and arbitrarily large chromatic number using probabilistic method. In a 1991 paper of Kriz and Nesetril, they introduced a new graph parameter eye(G). They show that there are graphs with large girth and large chromatic number among the class of graphs having eye parameter at most three. Answering a question of Kriz and Nesetril, we were able to strengthen their results and show that there are graphs with large girth and large chromatic number among the class of graphs having eye parameter at most two. The last component is about random posets--the poset version of the Erdos-Renyi random graphs. In 1991, Erdos, Kierstead and Trotter (EKT) investigated random height 2 posets and obtained several upper and lower bounds on the dimension of the random posets. Motivated by some extremal problems involving conditions which force a poset to contain a large standard example, we were compelled to revisit this subject. Our sharpened analysis allows us to conclude that as p approaches 1, the expected value of dimension first increases and then decreases, a subtlety not identified in EKT. Along the way, we establish connections with classical topics in analysis as well as with latin rectangles. Also, using structural insights drawn from this research, we are able to make progress on the motivating extremal problem with an application of the asymmetric form of the Lovasz Local Lemma.

In this dissertation we treat three tiling problems and three problems in combinatorial geometry, extremal graph theory and sparse Ramsey theory. We first consider tilings of $\mathbb{Z}^n$. In this setting a tile $T$ is just a finite subset of $\mathbb{Z}^n$. We say that $T$ tiles $\mathbb{Z}^n$ if the latter set admits a partition into isometric copies of $T$. Chalcraft observed that there exist $T$ that do not tile $\mathbb{Z}^n$ but tile $\mathbb{Z}^{d}$ for some $d > n$. He conjectured that such $d$ exists for any given tile. We prove this conjecture in Chapter 2. In Chapter 3 we prove a conjecture of Lonc, stating that for any poset $P$ of size a power of $2$, if $P$ has a greatest and a least element, then there is a positive integer $k$ such that $[2]^k$ can be partitioned into copies of $P$. The third tiling problem is about vertex-partitions of the hypercube graph $Q_n$. Offner asked: if $G$ is a subgraph of $Q_n$ such $|G|$ is a power of $2$, must $V(Q_d)$, for some $d$, admit a partition into isomorphic copies of $G$? In Chapter 4 we answer this question in the affirmative. We follow up with a question in combinatorial geometry. A line in a planar set $P$ is a maximal collinear subset of $P$. P\'or and Wood considered colourings of finite $P$ without large lines with a bounded number of colours. In particular, they examined whether monochromatic lines always appear in such colourings provided that $|P|$ is large. They conjectured that for all $k,l \ge 2$ there exists an $n \ge 2$ such that if $|P| \ge n$ and $P$ does not contain a line of cardinality larger than $l$, then every colouring of $P$ with $k$ colours produces a monochromatic line. In Chapter 5 we construct arbitrarily large counterexamples for the case $k=l=3$. We follow up with a problem in extremal graph theory. For any graph, we say that a given edge is triangular if it forms a triangle with two other edges. How few triangular edges can there be in a graph with $n$ vertices and $m$ edges? For sufficiently large $n$ we prove a conjecture of F\"uredi and Maleki that gives an exact formula for this minimum. This proof is given in Chapter 6. Finally, Chapter 7 is concerned with degrees of vertices in directed hypergraphs. One way to prescribe an orientation to an $r$-uniform graph $H$ is to assign for each of its edges one of the $r!$ possible orderings of its elements. Then, for any $p$-set of vertices $A$ and any $p$-set of indices $I \subset [r]$, we define the $I$-degree of $A$ to be the number of edges containing vertices $A$ in precisely the positions labelled by $I$. Caro and Hansberg were interested in determining whether a given $r$-uniform hypergraph admits an orientation where every set of $p$ vertices has some $I$-degree equal to $0$. They conjectured that a certain Hall-type condition is sufficient. We show that this is true for $r$ large, but false in general.

[pt] Este trabalho procura motivar e propor direções para uma abordagem de rudimentos da Teoria de Grafos nos anos finais da educação secundária brasileira. Os conceitos básicos da teoria são apresentados no contexto de desafios lúdicos e situações cotidianas. Procura-se ainda destacar a interdisciplinaridade e a atualidade do tema, apresentando exemplos provenientes de ramos tão diversos como eletrônica, transportes, arqueologia e genética. / [en] This work makes a case for the inclusion of some rudimentary Graph Theory in the final years of secondary education in Brazil, and also puts forward some suggestions of approach. The most basic concepts are presented in a light key, taking advange of puzzles and day to day situations. An effort was made to highlight the connections and applications of the theory to many branches of science and technology, such as electronics, transports, archeology and genetics.

This dissertation develops a cost model for a particular implementation of the database query language GraphLog. The order in which the subgoals of a GraphLog query are executed has a major effect on the total processing time. Our model may be used to compare the expected execution costs for different orderings of the same general query, thus, allowing us to select an efficient execution plan. We describe two cost models: one that is tailored to a specific architecture and another that is more general. Both models assume a top-down evaluation strategy. In particular, we address the issue of how to handle recursive predicates. We also provide some experimental results that confirm the validity of our work. / Graduate

ARAÚJO, Júlio César Silva. Coloração em convexidade em grafos. 2012. 207 f. Tese (Mestrado em ciência da computação)- Universidade Federal do Ceará, Fortaleza-CE, 2012. / Submitted by Elineudson Ribeiro (elineudsonr@gmail.com) on 2016-08-04T12:28:10Z No. of bitstreams: 1 2012_tese_jcsaraujo.pdf: 2148108 bytes, checksum: 966c00be231160cb1e161402770627d6 (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2016-08-05T15:46:03Z (GMT) No. of bitstreams: 1 2012_tese_jcsaraujo.pdf: 2148108 bytes, checksum: 966c00be231160cb1e161402770627d6 (MD5) / Made available in DSpace on 2016-08-05T15:46:03Z (GMT). No. of bitstreams: 1 2012_tese_jcsaraujo.pdf: 2148108 bytes, checksum: 966c00be231160cb1e161402770627d6 (MD5) Previous issue date: 2012 / In this thesis, we study several problems of Graph Theory concerning Graph Coloring and Graph Convexity. Most of the results contained here are related to the computational complexity of these problems for particular graph classes. In the first and main part of this thesis, we deal with Graph Coloring which is one of the most studied areas of Graph Theory. We first consider three graph coloring problems called Greedy Coloring, Weighted Coloring and Weighted Improper Coloring. Then, we deal with a decision problem, called Good Edge-Labeling, whose de finition was motivated by the Wavelength Assignment problem in optical networks. The second part of this thesis is devoted to a graph optimization parameter called (geodetic) hull number. The de finition of this parameter is motivated by an extension to graphs of the notions of convex sets and convex hulls in the Euclidean space. Finally, we present in the appendix other works developed during this thesis, one about Eulerian and Hamiltonian directed hypergraphs and the other concerning distributed storage systems. / Nesta tese, estudamos vários problemas de teoria dos grafos relativos à coloração e convexidade em grafos. A maioria dos resultados contidos aqui são ligados à complexidade computacional destes problemas para classes de grafos particulares. Na primeira, e principal, parte desta tese, discutimos coloração de grafos que é uma das áreas mais importantes de teoria dos grafos. Primeiro, consideramos três problemas de coloração chamados coloração gulosa, coloração ponderada e coloração ponderada imprópria. Em seguida, discutimos um problema de decisão, chamado boa rotulagem de arestas, cuja de finição foi motivada pelo problema de atribuição de frequências em redes óticas. A segunda parte desta tese é dedicada a um parâmetro de otimização em grafos chamado de número de fecho (geodético). A de finição deste parâmetro é motivada pela extensão das noções de conjuntos e fecho convexos no espaço Euclidiano. Por m, apresentamos em anexo outros trabalhos desenvolvidos durante esta tese, um em hipergrafos dirigidos Eulerianos e Hamiltonianos e outro sobre sistemas de armazenamento distribuído.

xiv, 183 p. : ill. A print copy of this thesis is available through the UO Libraries. Search the library catalog for the location and call number. / As the Internet has evolved over time, the interconnection patterns of the members of this "network of networks" have changed. Can we characterize those changes? Have those changes been good or bad? What does "good" mean in this context? Has market power been centralizing or decentralizing? How certain can we be of our answer? What are the limitations of our data? These are the questions which motivate this dissertation. In this dissertation, we answer these questions and more by carefully taking a long-term quantitative study of the evolution of the topology of the Internet's AS graph. In order to do this study, we spend most of the dissertation developing methods of data processing and data analysis all informed by ideas from networking, data mining, graph theory, and statistics. The contributions are both theoretical and practical. The theoretical contributions include an in-depth analysis of the complexity of AS graph measurement as well as of the difficulty of reconstructing the AS graph from available data. The practical contributions include the design of graph metrics to capture properties of interest, usable approximation algorithms for several AS graph analysis methods, and an analysis of the evolution of the AS graph over time. It is our hope that these methods may prove useful in other domains, and that the conclusions about the evolution of the Internet topology prove useful for Internet operators, network researchers, policy makers, and others. / Committee in charge: Andrzej Proskurowski, Chairperson, Computer & Information Science; Arthur Farley, Member, Computer & Information Science; Jun Li, Member, Computer & Information Science; Anne van den Nouweland, Outside Member, Economics

Made available in DSpace on 2015-05-14T16:52:58Z (GMT). No. of bitstreams: 0 Previous issue date: 2014-12-12Bitstream added on 2015-05-14T16:59:37Z : No. of bitstreams: 1 000829398.pdf: 735180 bytes, checksum: 47660f344914d561b93a77ad264e4c4b (MD5) / O objetivo principal deste trabalho é obter um resultado sobre separação de superficies por grafos. A Homologia Relativa é a principal ferramenta usada, obtendo uma versão particular da Dualidade de Lefschetz. Para a elaboração desta dissertação foram estudados: grafos, homologia simplicial, homologia relativa e grafos em superficies. O estudo foi baseado em grande parte no livro Graphs, Surfaces and Homology de P. J. Giblin / The main goal of this work is to get a result on separation of surfaces by graphs. The Relative Homology is the principal tool used and we get a particular version of Lefschetz duality. For the preparation of this dissertation we studied: graphs, simplicial homology, relative homology and graphs on surfaces. The study was based on the book Graphs, Surfaces and Homology of P. J. Giblin

abstract: Since the seminal work of Tur ́an, the forbidden subgraph problem has been among the central questions in extremal graph theory. Let ex(n;F) be the smallest number m such that any graph on n vertices with m edges contains F as a subgraph. Then the forbidden subgraph problem asks to find ex(n; F ) for various graphs F . The question can be further generalized by asking for the extreme values of other graph parameters like minimum degree, maximum degree, or connectivity. We call this type of question a Tura ́n-type problem. In this thesis, we will study Tura ́n-type problems and their variants for graphs and hypergraphs. Chapter 2 contains a Tura ́n-type problem for cycles in dense graphs. The main result in this chapter gives a tight bound for the minimum degree of a graph which guarantees existence of disjoint cycles in the case of dense graphs. This, in particular, answers in the affirmative a question of Faudree, Gould, Jacobson and Magnant in the case of dense graphs. In Chapter 3, similar problems for trees are investigated. Recently, Faudree, Gould, Jacobson and West studied the minimum degree conditions for the existence of certain spanning caterpillars. They proved certain bounds that guarantee existence of spanning caterpillars. The main result in Chapter 3 significantly improves their result and answers one of their questions by proving a tight minimum degree bound for the existence of such structures. Chapter 4 includes another Tur ́an-type problem for loose paths of length three in a 3-graph. As a corollary, an upper bound for the multi-color Ramsey number for the loose path of length three in a 3-graph is achieved. / Dissertation/Thesis / Doctoral Dissertation Mathematics 2018