To see the other types of publications on this topic, follow the link: Graph theory.
Dissertations / Theses on the topic 'Graph theory'
Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles
Consult the top 50 dissertations / theses for your research on the topic 'Graph theory.'
Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.
You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.
Browse dissertations / theses on a wide variety of disciplines and organise your bibliography correctly.
1
Bessy, Stéphane. "Some problems in graph theory and graphs algorithmic theory." Habilitation à diriger des recherches, Université Montpellier II - Sciences et Techniques du Languedoc, 2012. http://tel.archives-ouvertes.fr/tel-00806716.
Full textAbstract:
This document is a long abstract of my research work, concerning graph theory and algorithms on graphs. It summarizes some results, gives ideas of the proof for some of them and presents the context of the different topics together with some interesting open questions connected to them The first part precises the notations used in the rest of the paper; the second part deals with some problems on cycles in digraphs; the third part is an overview of two graph coloring problems and one problem on structures in colored graphs; finally the fourth part focus on some results in algorithmic graph theory, mainly in parametrized complexity.
2
Myers, Joseph Samuel. "Extremal theory of graph minors and directed graphs." Thesis, University of Cambridge, 2003. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.619614.
Full text
3
Johnson, Chase R. "Molecular Graph Theory." Digital WPI, 2010. https://digitalcommons.wpi.edu/etd-theses/1179.
Full textAbstract:
Graph Theory is a branch of mathematics that has a wealth of applications to other science and engineering disciplines, specifically Chemistry. The primary application of graphs to Chemistry is related to understanding of structure and symmetry at the molecular level. By projecting a molecule to the plane and examining it as a graph, a lot can be learned about the underlying molecular structure of a given compound. Using concepts of Graph Theory this masters project examines the underlying structures of two specific families of compounds, fullerenes and zeolites, from a chemical and mathematical perspective.
4
Feghali, Carl. "Topics in graph colouring and extremal graph theory." Thesis, Durham University, 2016. http://etheses.dur.ac.uk/11790/.
Full textAbstract:
In this thesis we consider three problems related to colourings of graphs and one problem in extremal graph theory. Let $G$ be a connected graph with $n$ vertices and maximum degree $\Delta(G)$. Let $R_k(G)$ denote the graph with vertex set all proper $k$-colourings of $G$ and two $k$-colourings are joined by an edge if they differ on the colour of exactly one vertex. Our first main result states that $R_{\Delta(G)+1}(G)$ has a unique non-trivial component with diameter $O(n^2)$. This result can be viewed as a reconfigurations analogue of Brooks' Theorem and completes the study of reconfigurations of colourings of graphs with bounded maximum degree. A Kempe change is the operation of swapping some colours $a$, $b$ of a component of the subgraph induced by vertices with colour $a$ or $b$. Two colourings are Kempe equivalent if one can be obtained from the other by a sequence of Kempe changes. Our second main result states that all $\Delta(G)$-colourings of a graph $G$ are Kempe equivalent unless $G$ is the complete graph or the triangular prism. This settles a conjecture of Mohar (2007). Motivated by finding an algorithmic version of a structure theorem for bull-free graphs due to Chudnovsky (2012), we consider the computational complexity of deciding if the vertices of a graph can be partitioned into two parts such that one part is triangle-free and the other part is a collection of complete graphs. We show that this problem is NP-complete when restricted to five classes of graphs (including bull-free graphs) while polynomial-time solvable for the class of cographs. Finally we consider a graph-theoretic version formulated by Holroyd, Spencer and Talbot (2007) of the famous Erd\H{o}s-Ko-Rado Theorem in extremal combinatorics and obtain some results for the class of trees.
5
Nikwigize, Adolphe. "Graph theory : Route problems." Thesis, Linnéuniversitetet, Institutionen för datavetenskap, fysik och matematik, DFM, 2012. http://urn.kb.se/resolve?urn=urn:nbn:se:lnu:diva-17397.
Full text
6
Berg, Deborah. "Connections Between Voting Theory and Graph Theory." Scholarship @ Claremont, 2005. https://scholarship.claremont.edu/hmc_theses/178.
Full textAbstract:
Mathematical concepts have aided the progression of many different fields of study. Math is not only helpful in science and engineering, but also in the humanities and social sciences. Therefore, it seemed quite natural to apply my preliminary work with set intersections to voting theory, and that application has helped to focus my thesis. Rather than studying set intersections in general, I am attempting to study set intersections and what they mean in a voting situation. This can lead to better ways to model preferences and to predict which campaign platforms will be most popular. Because I feel that allowing people to only vote for one candidate results in a loss of too much information, I consider approval voting, where people can vote for as many platforms as they like.
7
Hatt, Justin Dale. "Online assessment of graph theory." Thesis, Brunel University, 2016. http://bura.brunel.ac.uk/handle/2438/13389.
Full textAbstract:
The objective of this thesis is to establish whether or not online, objective questions in elementary graph theory can be written in a way that exploits the medium of computer-aided assessment. This required the identification and resolution of question design and programming issues. The resulting questions were trialled to give an extensive set of answer files which were analysed to identify whether computer delivery affected the questions in any adverse ways and, if so, to identify practical ways round these issues. A library of questions spanning commonly-taught topics in elementary graph theory has been designed, programmed and added to the graph theory topic within an online assessment and learning tool used at Brunel University called Mathletics. Distracters coded into the questions are based on errors students are likely to make, partially evidenced by final examination scripts. Questions were provided to students in Discrete Mathematics modules with an extensive collection of results compiled for analysis. Questions designed for use in practice environments were trialled on students from 2007 – 2008 and then from 2008 to 2014 inclusive under separate testing conditions. Particular focus is made on the relationship of facility and discrimination between comparable questions during this period. Data is grouped between topic and also year group for the 2008 – 2014 tests, namely 2008 to 2011 and 2011 to 2014, so that it may then be determined what factors, if any, had an effect on the overall results for these questions. Based on the analyses performed, it may be concluded that although CAA questions provide students with a means for improving their learning in this field of mathematics, what makes a question more challenging is not solely based on the number of ways a student can work out his/her solution but also on several other factors that depend on the topic itself.
8
Keevash, Peter. "Topics in extremal graph theory." Thesis, University of Cambridge, 2003. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.619938.
Full text
9
Law, Ka-ho, and 羅家豪. "Some results in graph theory." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2010. http://hub.hku.hk/bib/B44899816.
Full text
10
Morrison, Julie Lindsay. "Computational graph theory in bioinformatics." Thesis, University of Strathclyde, 2006. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.435114.
Full text
11
Richer, Duncan Christopher. "Graph theory and combinatorial games." Thesis, University of Cambridge, 2000. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.621916.
Full text
12
Eggemann, Nicole. "Some applications of graph theory." Thesis, Brunel University, 2009. http://bura.brunel.ac.uk/handle/2438/3953.
Full text
13
Nieh, Ari. "Fractional Analogues in Graph Theory." Scholarship @ Claremont, 2001. https://scholarship.claremont.edu/hmc_theses/131.
Full textAbstract:
Tait showed in 1878 that the Four Color Theorem is equivalent to being able to three-color the edges of any planar, three-regular, two-edge connected graph. Not surprisingly, this equivalent problem proved to be equally difficult. We consider the problem of fractional colorings, which resemble ordinary colorings but allow for some degree of cheating. Happily, it is known that every planar three-regular, two-edge connected graph is fractionally three-edge colorable. Is there an analogue to Tait’s Theorem which would allow us to derive the Fractional Four Color Theorem from this edge-coloring result?
14
Letzter, Shoham. "Extremal graph theory with emphasis on Ramsey theory." Thesis, University of Cambridge, 2015. https://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.709415.
Full text
15
Reed, Bruce. "A semi-strong perfect graph theorem /." Thesis, McGill University, 1986. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=72812.
Full text
16
Meek, Darrin Leigh. "On graph approximation heuristics : an application to vertex cover on planar graphs." Thesis, Georgia Institute of Technology, 1991. http://hdl.handle.net/1853/24088.
Full text
17
Zuffi, Lorenzo. "Simplicial Complexes From Graphs Toward Graph Persistence." Master's thesis, Alma Mater Studiorum - Università di Bologna, 2017. http://amslaurea.unibo.it/13519/.
Full textAbstract:
Persistent homology is a branch of computational topology which uses geometry and topology for shape description and analysis. This dissertation is an introductory study to link persistent homology and graph theory, the connection being represented by various methods to build simplicial complexes from a graph. The methods we consider are the complex of cliques, of independent sets, of neighbours, of enclaveless sets and complexes from acyclic subgraphs, each revealing several properties of the underlying graph. Moreover, we apply the core ideas of persistence theory in the new context of graph theory, we define the persistent block number and the persistent edge-block number.
18
Anderson, Jon K. "Genetic algorithms applied to graph theory." Virtual Press, 1999. http://liblink.bsu.edu/uhtbin/catkey/1136714.
Full textAbstract:
This thesis proposes two new variations on the genetic algorithm. The first attempts to improve clustering problems by optimizing the structure of a genetic string dynamically during the run of the algorithm. This is done by using a permutation on the allele which is inherited by the next generation. The second is a multiple pool technique which ensures continuing convergence by maintaining unique lineages and merging pools of similar age. These variations will be tested against two well-known graph theory problems, the Traveling Salesman Problem and the Maximum Clique Problem. The results will be analyzed with respect to string rates, child improvement, pool rating resolution, and average string age.Department of Computer Science
19
Peng, Richard. "Algorithm Design Using Spectral Graph Theory." Research Showcase @ CMU, 2013. http://repository.cmu.edu/dissertations/277.
Full textAbstract:
Spectral graph theory is the interplay between linear algebra and combinatorial graph theory. Laplace’s equation and its discrete form, the Laplacian matrix, appear ubiquitously in mathematical physics. Due to the recent discovery of very fast solvers for these equations, they are also becoming increasingly useful in combinatorial optimization, computer vision, computer graphics, and machine learning.
In this thesis, we develop highly efficient and parallelizable algorithms for solving linear systems involving graph Laplacian matrices. These solvers can also be extended to symmetric diagonally dominant matrices and M-matrices, both of which are closely related to graph Laplacians. Our algorithms build upon two decades of progress on combinatorial preconditioning, which connects numerical and combinatorial algorithms through spectral graph theory. They in turn rely on tools from numerical analysis, metric embeddings, and random matrix theory.
We give two solver algorithms that take diametrically opposite approaches. The first is motivated by combinatorial algorithms, and aims to gradually break the problem into several smaller ones. It represents major simplifications over previous solver constructions, and has theoretical running time comparable to sorting. The second is motivated by numerical analysis, and aims to rapidly improve the algebraic connectivity of the graph. It is the first highly efficient solver for Laplacian linear systems that parallelizes almost completely.
Our results improve the performances of applications of fast linear system solvers ranging from scientific computing to algorithmic graph theory. We also show that these solvers can be used to address broad classes of image processing tasks, and give some preliminary experimental results.
20
Islam, Mustafa R. "A hypertext graph theory reference system." Virtual Press, 1993. http://liblink.bsu.edu/uhtbin/catkey/879844.
Full textAbstract:
G-Net system is being developed by the members of the G-Net research group under the supervision of Dr. K. Jay Bagga. The principle objective of the G-Net system is to provide an integrated tool for dealing with various aspects of graph theory. G-Net system is divided into two parts. GETS (Graph theory Experiments Tool Set) will provide a set of tools to experiment with graph theory, and HYGRES (HYpertext Graph theory Reference Service), the second subcomponent of the G-Net system to aid graph theory study and research. In this research a hypertext application is built to present the graph theory concepts, graph models and the algorithms. In other words, HYGRES (Guide Version) provides the hypertext facilities for organizing a graph theory database in a very natural and interactive way. An hypertext application development tool, called Guide, is used to implement this version of HYGRES. This project integrates the existing version of GETS so that it can also provide important services to HYGRES. The motivation behind this project is to study the initial criterion for developing a hypertext system, which can be used for future development of a stand alone version of the G-Net system.Department of Computer Science
21
Edwards, C. S. "Some extremal problems in graph theory." Thesis, University of Reading, 1986. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.373467.
Full text
22
Garbe, Frederik. "Extremal graph theory via structural analysis." Thesis, University of Birmingham, 2018. http://etheses.bham.ac.uk//id/eprint/8869/.
Full textAbstract:
We discuss two extremal problems in extremal graph theory. First we establish a precise characterisation of 4-uniform hypergraphs with minimum codegree close to n/2 which contain a Hamilton 2-cycle. As a corollary we determine the exact Dirac threshold for Hamilton 2-cycles in 4-uniform hypergraphs, and we provide a polynomial-time algorithm which answers the corresponding decision problem for 4-graphs with minimum degree close to n/2. In contrast we also show that the corresponding decision problem for tight Hamilton cycles in dense k-graphs is NP-complete. Furthermore we study the following bootstrap percolation process: given a connected graph G, we infect an initial set A of vertices, and in each step a vertex v becomes infected if at least a p-proportion of its neighbours are infected. A set A which infects the whole graph is called a contagious set. Our main result states that for every pin (0,1] and for every connected graph G on n vertices the minimal size of a contagious set is less than 2pn or 1. This result is best-possible, but we provide a stronger bound in the case of graphs of girth at least five. Both proofs exploit the structure of a minimal counterexample.
23
Grinshpun, Andrey Vadim. "Some problems in Graph Ramsey Theory." Thesis, Massachusetts Institute of Technology, 2015. http://hdl.handle.net/1721.1/97767.
Full textAbstract:
Thesis: Ph. D., Massachusetts Institute of Technology, Department of Mathematics, 2015.This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections.
Cataloged from student-submitted PDF version of thesis.
Includes bibliographical references (pages 149-156).
A graph G is r-Ramsey minimal with respect to a graph H if every r-coloring of the edges of G yields a monochromatic copy of H, but the same is not true for any proper subgraph of G. The study of the properties of graphs that are Ramsey minimal with respect to some H and similar problems is known as graph Ramsey theory; we study several problems in this area. Burr, Erdös, and Lovász introduced s(H), the minimum over all G that are 2- Ramsey minimal for H of [delta](G), the minimum degree of G. We find the values of s(H) for several classes of graphs H, most notably for all 3-connected bipartite graphs which proves many cases of a conjecture due to Szabó, Zumstein, and Zürcher. One natural question when studying graph Ramsey theory is what happens when, rather than considering all 2-colorings of a graph G, we restrict to a subset of the possible 2-colorings. Erdös and Hajnal conjectured that, for any fixed color pattern C, there is some [epsilon] > 0 so that every 2-coloring of the edges of a Kn, the complete graph on n vertices, which doesn't contain a copy of C contains a monochromatic clique on n[epsilon] vertices. Hajnal generalized this conjecture to more than 2 colors and asked in particular about the case when the number of colors is 3 and C is a rainbow triangle (a K3 where each edge is a different color); we prove Hajnal's conjecture for rainbow triangles. One may also wonder what would happen if we wish to cover all of the vertices with monochromatic copies of graphs. Let F = {F₁, F₂, . . .} be a sequence of graphs such that Fn is a graph on n vertices with maximum degree at most [delta]. If each Fn is bipartite, then the vertices of any 2-edge-colored complete graph can be partitioned into at most 2C[delta] vertex disjoint monochromatic copies of graphs from F, where C is an absolute constant. This result is best possible, up to the constant C.
by Andrey Vadim Grinshpun.
Ph. D.
24
Pappone, Francesco. "Graph neural networks: theory and applications." Bachelor's thesis, Alma Mater Studiorum - Università di Bologna, 2021. http://amslaurea.unibo.it/23893/.
Full textAbstract:
Le reti neurali artificiali hanno visto, negli ultimi anni, una crescita vertiginosa nelle loro applicazioni e nelle architetture dei modelli impiegati. In questa tesi introduciamo le reti neurali su domini euclidei, in particolare mostrando l’importanza dell’equivarianza di traslazione nelle reti convoluzionali, e introduciamo, per analogia, un’estensione della convoluzione a dati strutturati come grafi. Inoltre presentiamo le architetture dei principali Graph Neural Network ed esponiamo, per ognuna delle tre architetture proposte (Spectral graph Convolutional Network, Graph Convolutional Network, Graph Attention neTwork) un’applicazione che ne mostri sia il funzionamento che l’importanza. Discutiamo, ulteriormente, l’implementazione di un algoritmo di classificazione basato su due varianti dell’architettura Graph Convolutional Network, addestrato e testato sul dataset PROTEINS, capace di classificare le proteine del dataset in due categorie: enzimi e non enzimi.
25
Parks, David J. "Graph theory in America, 1876-1950." Thesis, Open University, 2012. http://oro.open.ac.uk/54663/.
Full textAbstract:
This narrative is a history of the contributions made to graph theory in the United States of America by American mathematicians and others who supported the growth of scholarship in that country, between the years 1876 and 1950. The beginning of this period coincided with the opening of the first research university in the United States of America, The Johns Hopkins University (although undergraduates were also taught), providing the facilities and impetus for the development of new ideas. The hiring, from England, of one of the foremost mathematicians of the time provided the necessary motivation for research and development for a new generation of American scholars. In addition, it was at this time that home-grown research mathematicians were first coming to prominence. At the beginning of the twentieth century European interest in graph theory, and to some extent the four-colour problem, began to wane. Over three decades, American mathematicians took up this field of study - notably, Oswald Veblen, George Birkhoff, Philip Franklin, and Hassler Whitney. It is necessary to stress that these four mathematicians and all the other scholars mentioned in this history were not just graph theorists but worked in many other disciplines. Indeed, they not only made significant contributions to diverse fields but, in some cases, they created those fields themselves and set the standards for others to follow. Moreover, whilst they made considerable contributions to graph theory in general, two of them developed important ideas in connection with the four-colour problem. Grounded in a paper by Alfred Bray Kempe that was notorious for its fallacious 'proof' of the four-colour theorem, these ideas were the concepts of an unavoidable set and a reducible configuration. To place the story of these scholars within the history of mathematics, America, and graph theory, brief accounts are presented of the early years of graph theory, the early years of mathematics and graph theory in the USA, and the effects of the founding of the first institute for postgraduate study in America. Additionally, information has been included on other influences by such global events as the two world wars, the depression, the influx of European scholars into the United States of America, mainly during the 1930s, and the parallel development of graph theory in Europe. Until the end of the nineteenth century, graph theory had been almost entirely the prerogative of European mathematicians. Perhaps the first work in graph theory carried out in America was by Charles Sanders Peirce, arguably America's greatest logician and philosopher at the time. In the 1860s, he studied the four-colour conjecture and claimed to have written at least two papers on the subject during that decade, but unfortunately neither of these has survived. William Edward Story entered the field in 1879, with unfortunate consequences, but it was not until 1897 that an American mathematician presented a lecture on the subject, albeit only to have the paper disappear. Paul Wernicke presented a lecture on the four-colour problem to the American Mathematician Society, but again the paper has not survived. However, his 1904 paper has survived and added to the story of graph theory, and particularly the four-colour conjecture. The year 1912 saw the real beginning of American graph theory with Veblen and Birkhoff publishing major contributions to the subject. It was around this time that European mathematicians appeared to lose interest in graph theory. In the period 1912 to 1950 much of the progress made in the subject was from America and by 1950 not only had the United States of America become the foremost country for mathematics, it was the leading centre for graph theory.
26
Schuerger, Houston S. "Contributions to Geometry and Graph Theory." Thesis, University of North Texas, 2020. https://digital.library.unt.edu/ark:/67531/metadc1707341/.
Full textAbstract:
In geometry we will consider n-dimensional generalizations of the Power of a Point Theorem and of Pascal's Hexagon Theorem. In generalizing the Power of a Point Theorem, we will consider collections of cones determined by the intersections of an (n-1)-sphere and a pair of hyperplanes. We will then use these constructions to produce an n-dimensional generalization of Pascal's Hexagon Theorem, a classical plane geometry result which states that "Given a hexagon inscribed in a conic section, the three pairs of continuations of opposite sides meet on a straight line." Our generalization of this theorem will consider a pair of n-simplices intersecting an (n-1)-sphere, and will conclude with the intersections of corresponding faces lying in a hyperplane. In graph theory we will explore the interaction between zero forcing and cut-sets. The color change rule which lies at the center of zero forcing says "Suppose that each of the vertices of a graph are colored either blue or white. If u is a blue vertex and v is its only white neighbor, then u can force v to change to blue." The concept of zero forcing was introduced by the AIM Minimum Rank - Special Graphs Work Group in 2007 as a way of determining bounds on the minimum rank of graphs. Later, Darren Row established results concerning the zero forcing numbers of graphs with a cut-vertex. We will extend his work by considering graphs with arbitrarily large cut-sets, and the collections of components they yield, to determine results for the zero forcing numbers of these graphs.
27
Weaver, Robert Wooddell. "Some problems in structural graph theory /." The Ohio State University, 1986. http://rave.ohiolink.edu/etdc/view?acc_num=osu1487268021746449.
Full text
28
Florkowski, Stanley F. "Spectral graph theory of the Hypercube." Thesis, Monterey, Calif. : Naval Postgraduate School, 2008. http://edocs.nps.edu/npspubs/scholarly/theses/2008/Dec/08Dec%5FFlorkowski.pdf.
Full textAbstract:
Thesis (M.S. in Applied Mathematics)--Naval Postgraduate School, December 2008.Thesis Advisor(s): Rasmussen, Craig W. "December 2008." Description based on title screen as viewed on January 29, 2009. Includes bibliographical references (p. 51-52). Also available in print.
29
Han, Lin. "Graph generative models from information theory." Thesis, University of York, 2012. http://etheses.whiterose.ac.uk/3726/.
Full textAbstract:
Generative models are commonly used in statistical pattern recognition to describe the probability distributions of patterns in a vector space. In recent years, sustained by the wide range of mathematical tools available in vector space, many algorithms for constructing generative models have been developed. Compared with the advanced development of the generative model for vectors, the development of a generative model for graphs has had less progress. In this thesis, we aim to solve the problem of constructing the generative model for graphs using information theory. Given a set of sample graphs, the generative model for the graphs we aim to construct should be able to not only capture the structural variation of the sample graphs, but to also allow new graphs which share similar properties with the original graphs to be generated. In this thesis, we pose the problem of constructing a generative model for graphs as that of constructing a supergraph structure for the graphs. In Chapter 3, we describe a method of constructing a supergraph-based generative model given a set of sample graphs. By adopting the a posteriori probability developed in a graph matching problem, we obtain a probabilistic framework which measures the likelihood of the sample graphs, given the structure of the supergraph and the correspondence information between the nodes of the sample graphs and those of the supergraph. The supergraph we aim to obtain is one which maximizes the likelihood of the sample graphs. The supergraph is represented here by its adjacency matrix, and we develop a variant of the EM algorithm to locate the adjacency matrix that maximizes the likelihood of the sample graphs. Experimental evaluations demonstrate that the constructed supergraph performs well on classifying graphs. In Chapter 4, we aim to develop graph characterizations that can be used to measure the complexity of graphs. The first graph characterization developed is the von Neumann entropy of a graph associated with its normalized Laplacian matrix. This graph characterization is defined by the eigenvalues of the normalized Laplacian matrix, therefore it is a member of the graph invariant characterization. By applying some transformations, we also develop a simplified form of the von Neumann entropy, which can be expressed in terms of the node degree statistics of the graphs. Experimental results reveal that effectiveness of the two graph characterizations. Our third contribution is presented in Chapter 5, where we use the graph characterization developed in Chapter 4 to measure the supergraph complexity and we develop a novel framework for learning a supergraph using the minimum description length criterion. We combine the Jensen-Shanon kernel with our supergraph construction and this provides us with a way of measuring graph similarity. Moreover, we also develop a method of sampling new graphs from the supergraph. The supergraph we present in this chapter is a generative model which can fulfil the tasks of graph classification, graph clustering, and of generating new graphs. We experiment with both the COIL and “Toy” datasets to illustrate the utility of our generative model. Finally, in Chapter 6, we propose a method of selecting prototype graphs of the most appropriate size from candidate prototypes. The method works by partitioning the sample graphs into two parts and approximating their hypothesis space using the partition functions. From the partition functions, the mutual information between the two sets is defined. The prototype which gives the highest mutual information is selected.
30
Robinson, Laura Ann. "Graph Theory for the Middle School." Digital Commons @ East Tennessee State University, 2006. https://dc.etsu.edu/etd/2226.
Full textAbstract:
After being introduced to graph theory and realizing how it can be utilized to solve real-world problems, the author decided to create modules of study on graph theory appropriate for middle school students. In this thesis, four modules were developed in the area of graph theory: an Introduction to Terms and Definitions, Graph Families, Graph Operations, and Graph Coloring. It is written as a guide for middle school teachers to prepare teaching units on graph theory.
31
Loveland, Susan M. "The Reconstruction Conjecture in Graph Theory." DigitalCommons@USU, 1985. https://digitalcommons.usu.edu/etd/7022.
Full textAbstract:
In this paper we show that specific classes of graphs are reconstructible; we explore the relationship between the. reconstruction and edge-reconstruction conjectures; we prove that several classes of graphs are actually Harary to the reconstructible; and we give counterexamples reconstruction and edge-reconstruction conjectures for infinite graphs.
32
Yi, Peipei. "Graph query autocompletion." HKBU Institutional Repository, 2018. https://repository.hkbu.edu.hk/etd_oa/557.
Full textAbstract:
The prevalence of graph-structured data in modern real-world applications has led to a rejuvenation of research on graph data management and analytics. Several database query languages have been proposed for textually querying graph databases. Unfortunately, formulating a graph query using any of these query languages often demands considerable cognitive effort and requires "programming" skill at least similar to programming in SQL. Yet, in a wide spectrum of graph applications consumers need to query graph data but are not proficient query writers. Hence, it is important to devise intuitive techniques that can alleviate the burden of query formulation and thus increase the usability of graph databases. In this dissertation, we take the first step to study the graph query autocompletion problem. We provide techniques that take a user's graph query as input and generate top-k query suggestions as output, to help to alleviate the verbose and error-prone graph query formulation process in a visual environment. Firstly, we study visual query autocompletion for graph databases. Techniques for query autocompletion have been proposed for web search and XML search. However, a corresponding capability for graph query engine is in its infancy. We propose a novel framework for graph query autocompletion (called AutoG). The novelties of AutoG are as follows: First, we formalize query composition that specifies how query suggestions are formed. Second, we propose to increment a query with the logical units called c-prime features, that are (i) frequent subgraphs and (ii) constructed from smaller c-prime features in no more than c ways. Third, we propose algorithms to rank candidate suggestions. Fourth, we propose a novel index called feature DAG (FDAG) to further optimize the ranking. Secondly, we propose user focus-based graph query autocompletion. AutoG provides suggestions that are formed by adding subgraph increments to arbitrary places of an existing user query. However, humans can only interact with a small number of recent software artifacts in hand. Hence, many such suggestions could be irrelevant. We present the GFocus framework that exploits a novel notion of user focus of graph query formulation. Intuitively, the focus is the subgraph that a user is working on. We formulate locality principles to automatically identify and maintain the focus. We propose novel monotone submodular ranking functions for generating popular and comprehensive query suggestions only at the focus. We propose efficient algorithms and an index for ranking the suggestions. Thirdly, we propose graph query autocompletion for large graphs. Graph features that have been exploited in AutoG are either absent or rare in large graphs. To address this, we present Flexible graph query autocompletion for LArge Graphs, called FLAG. We propose wildcard label for query graph and query suggestions. In particular, FLAG allows augmenting users' queries using subgraph increments with wildcard labels, which summarize query suggestions that have similar increment structures but different labels. We propose an efficient ranking algorithm and a novel index, called Suggestion Summarization DAG (SSDAG), to optimize the online suggestion ranking. Detailed problem analysis and extensive experimental studies consistently demonstrate the effectiveness and robustness of our proposed techniques in a broad range of settings.
33
Lopez, Christian P. "On the relationship between a graph and the cycle graph of its complement." Thesis, Edith Cowan University, Research Online, Perth, Western Australia, 1995. https://ro.ecu.edu.au/theses/1184.
Full textAbstract:
From an arbitrary graph G, another graph called the cycle graph of G and denoted by C(G) can be derived. The cycle graph C(G) of G has as its vertices the chordless cycles of G and two vertices in C(G) are adjacent if and only if the corresponding chordless cycles have at least one edge in common.
34
Hegde, Rajneesh. "New Tools and Results in Graph Structure Theory." Diss., Georgia Institute of Technology, 2006. http://hdl.handle.net/1853/10481.
Full textAbstract:
We first prove a ``non-embeddable extensions' theorem for polyhedral graph embeddings. Let G be a ``weakly 4-connected' planar graph. We describe a set of constructions that produce a finite list of non-planar graphs, each having a minor isomorphic to G, such that every non-planar weakly 4-connected graph H that has a minor isomorphic to G has a minor isomorphic to one of the graphs in the list. The theorem is more general and applies in particular to polyhedral embeddings in any surface.
We discuss an approach to proving Jorgensen's conjecture, which states that if G is a 6-connected graph with no K_6 minor, then it is apex, that is, it has a vertex v such that deleting v yields a planar graph. We relax the condition of 6-connectivity, and prove Jorgensen's conjecture for a certain sub-class of these graphs.
We prove that every graph embedded in the Klein bottle with representativity at least 4 has a K_6 minor. Also, we prove that every ``locally 5-connected' triangulation of the torus, with one exception, has a K_6 minor. (Local 5-connectivity is a natural notion of local connectivity for a surface embedding.) The above theorem uses a locally 5-connected version of the well-known splitter theorem for triangulations of any surface.
We conclude with a theoretically optimal algorithm for the following graph connectivity problem. A shredder in an undirected graph is a set of vertices whose removal results in at least three components. A 3-shredder is a shredder of size three. We present an algorithm that, given a 3-connected graph, finds its 3-shredders in time proportional to the number of vertices and edges, when implemented on a RAM (random access machine).
35
Morisi, Rita. "Graph–based techniques and spectral graph theory in control and machine learning." Thesis, IMT Alti Studi Lucca, 2016. http://e-theses.imtlucca.it/188/1/Morisi_phdthesis.pdf.
Full textAbstract:
Graphs are powerful data structure for representing objects
and their relationships. They are extremely useful in the study
of dynamical systems, evaluating how different agents interact
among each other and behave. An example is represented
by the consensus problem where a graph models a
set of agents that locally interact and exchange their opinions
with the aim of reaching a common opinion (consensus
state). At the same time, many learning techniques rely
on graphs exploiting their potentialities in modeling the relationships
between data and determining additional features
related to the data similarities. To study both the consensus
problem and specific machine learning applications based on
graphs, the study of the spectral properties of graphs reveals
fundamental. In the consensus problem, the convergence rate
to the consensus state strictly depends on the spectral properties
of the transition probability matrix associated to the
agents network. Whereas graphs and their spectral properties
are fundamental in determining learning algorithms able
to capture the structure of a dataset. We propose a theoretical
and numerical study of the spectral properties of a network
of agents that interact with the aim of increasing the rate of
convergence to the consensus state keeping as sparse as possible
the graph involved. Experimental results demonstrate
the capability of the proposed approach in reaching the consensus
state faster than a classical approach. We then investigate
the potentialities of graphs when applied in classification
problems. The results achieved highlight the importance
of graphs and their spectral properties handling with both
semi–supervised and supervised learning problems.
36
Hoang, Chinh T. "Perfect graphs." Thesis, McGill University, 1985. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=74011.
Full text
37
Hayward, Ryan B. "Two classes of perfect graphs." Thesis, McGill University, 1986. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=74025.
Full text
38
Olariu, Stephan. "Results on perfect graphs." Thesis, McGill University, 1986. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=73997.
Full text
39
Weinstein, Lee. "Empirical study of graph properties with particular interest towards random graphs." Diss., Connect to the thesis, 2005. http://hdl.handle.net/10066/1485.
Full text
40
Waterhouse, Mary Alexandra Paula Royston Hastilow. "Coloured graph decompositions /." [St. Lucia, Qld.], 2005. http://www.library.uq.edu.au/pdfserve.php?image=thesisabs/absthe18769.pdf.
Full text
41
Narayanan, Bhargav. "Problems in Ramsey theory, probabilistic combinatorics and extremal graph theory." Thesis, University of Cambridge, 2015. https://www.repository.cam.ac.uk/handle/1810/252850.
Full text
42
Fiala, Nick C. "Some topics in combinatorial design theory and algebraic graph theory /." The Ohio State University, 2002. http://rave.ohiolink.edu/etdc/view?acc_num=osu1486402957198077.
Full text
43
Burns, Jonathan. "Recursive Methods in Number Theory, Combinatorial Graph Theory, and Probability." Scholar Commons, 2014. https://scholarcommons.usf.edu/etd/5193.
Full textAbstract:
Recursion is a fundamental tool of mathematics used to define, construct, and analyze mathematical objects. This work employs induction, sieving, inversion, and other recursive methods to solve a variety of problems in the areas of algebraic number theory, topological and combinatorial graph theory, and analytic probability and statistics. A common theme of recursively defined functions, weighted sums, and cross-referencing sequences arises in all three contexts, and supplemented by sieving methods, generating functions, asymptotics, and heuristic algorithms.
In the area of number theory, this work generalizes the sieve of Eratosthenes to a sequence of polynomial values called polynomial-value sieving. In the case of quadratics, the method of polynomial-value sieving may be characterized briefly as a product presentation of two binary quadratic forms. Polynomials for which the polynomial-value sieving yields all possible integer factorizations of the polynomial values are called recursively-factorable. The Euler and Legendre prime producing polynomials of the form n2+n+p and 2n2+p, respectively, and Landau's n2+1 are shown to be recursively-factorable. Integer factorizations realized by the polynomial-value sieving method, applied to quadratic functions, are in direct correspondence with the lattice point solutions (X,Y) of the conic sections aX2+bXY +cY2+X-nY=0. The factorization structure of the underlying quadratic polynomial is shown to have geometric properties in the space of the associated lattice point solutions of these conic sections.
In the area of combinatorial graph theory, this work considers two topological structures that are used to model the process of homologous genetic recombination: assembly graphs and chord diagrams. The result of a homologous recombination can be recorded as a sequence of signed permutations called a micronuclear arrangement. In the assembly graph model, each micronuclear arrangement corresponds to a directed Hamiltonian polygonal path within a directed assembly graph. Starting from a given assembly graph, we construct all the associated micronuclear arrangements. Another way of modeling genetic rearrangement is to represent precursor and product genes as a sequence of blocks which form arcs of a circle. Associating matching blocks in the precursor and product gene with chords produces a chord diagram. The braid index of a chord diagram can be used to measure the scope of interaction between the crossings of the chords. We augment the brute force algorithm for computing the braid index to utilize a divide and conquer strategy. Both assembly graphs and chord diagrams are closely associated with double occurrence words, so we classify and enumerate the double occurrence words based on several notions of irreducibility. In the area of analytic probability, moments abstractly describe the shape of a probability distribution. Over the years, numerous varieties of moments such as central moments, factorial moments, and cumulants have been developed to assist in statistical analysis. We use inversion formulas to compute high order moments of various types for common probability distributions, and show how the successive ratios of moments can be used for distribution and parameter fitting. We consider examples for both simulated binomial data and the probability distribution affiliated with the braid index counting sequence. Finally we consider a sequence of multiparameter binomial sums which shares similar properties with the moment sequences generated by the binomial and beta-binomial distributions. This sequence of sums behaves asymptotically like the high order moments of the beta distribution, and has completely monotonic properties.
44
Turner, Bethany. "Embeddings of Product Graphs Where One Factor is a Hypercube." VCU Scholars Compass, 2011. http://scholarscompass.vcu.edu/etd/2455.
Full textAbstract:
Voltage graph theory can be used to describe embeddings of product graphs if one factor is a Cayley graph. We use voltage graphs to explore embeddings of various products where one factor is a hypercube, describing some minimal and symmetrical embeddings. We then define a graph product, the weak symmetric difference, and illustrate a voltage graph construction useful for obtaining an embedding of the weak symmetric difference of an arbitrary graph with a hypercube.
45
Srikanthan, T. "Bond graph analysis." Thesis, Coventry University, 1986. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.373896.
Full text
46
Chen, Xujin, and 陳旭瑾. "Graph partitions and integer flows." Thesis, The University of Hong Kong (Pokfulam, Hong Kong), 2004. http://hub.hku.hk/bib/B30286256.
Full text
47
Vella, Antoine. "A Fundamentally Topological Perspective on Graph Theory." Thesis, University of Waterloo, 2005. http://hdl.handle.net/10012/1033.
Full textAbstract:
We adopt a novel topological approach for graphs, in which edges are modelled as points as opposed to arcs. The model of classical topologized graphs translates graph isomorphism into topological homeomorphism, so that all combinatorial concepts are expressible in purely topological language. This allows us to extrapolate concepts from finite graphs to infinite graphs equipped with a compatible topology, which, dropping the classical requirement, need not be unique. We bring standard concepts from general topology to bear upon questions of a combinatorial inspiration, in an infinite setting.
We show how (possibly finite) graph-theoretic paths are, without any technical subterfuges, a subclass of a broad category of topological spaces, namely paths, that includes Hausdorff arcs, the real line and all connected orderable spaces (of arbitrary cardinality). We show that all paths, and the topological generalizations of cycles, are topologized graphs. We use feeble regularity to explore relationships between the topologies on the vertex set and the whole space. We employ compactness and weak normality to prove the existence of our analogues for minimal spanning sets and fundamental cycles. In this framework, we generalize theorems from finite graph theory to a broad class of topological structures, including the facts that fundamental cycles are a basis for the cycle space, and the orthogonality between bond spaces and cycle spaces. We show that this can be accomplished in a setup where the set of edges of a cycle has a loose relationship with the cycle itself. It turns out that, in our model, feeble regularity excludes several pathologies, including one identified previously by Diestel and Kuehn, in a very different approach which addresses the same issues. Moreover, the spaces surgically constructed by the same authors are feebly regular and, if the original graph is 2-connected, compact. We consider an attractive relaxation of the T1 separation axiom, namely the S1 axiom, which leads to a topological universe parallel to the usual one in mainstream topology. We use local connectedness to unify graph-theoretic trees with the dendrites of continuum theory and a more general class of well behaved dendritic spaces, within the class of ferns.
We generalize results of Whyburn and others concerning dendritic spaces to ferns, and show how cycles and ferns, in particular paths, are naturally S1 spaces, and hence may be viewed as topologized hypergraphs. We use topological separation properties with a distinct combinatorial flavour to unify the theory of cycles, paths and ferns. This we also do via a setup involving total orders, cyclic orders and partial orders. The results on partial orders are similar to results of Ward and Muenzenberger and Smithson in the more restrictive setting of Hausdorff dendritic spaces. Our approach is quite different and, we believe, lays the ground for an appropriate notion of completion which links Freudenthal ends of ferns simultaneously with the work of Polat for non-locally-finite graphs and the paper of Allen which recognizes the unique dendritic compactification of a rim-compact dendritic space as its Freudenthal compactification.
48
Douma, Femke. "Counting and averaging problems in graph theory." Thesis, Durham University, 2010. http://etheses.dur.ac.uk/272/.
Full textAbstract:
Paul Gunther (1966), proved the following result: Given a continuous function f on a compact surface M of constant curvature -1 and its periodic lift g to the universal covering, the hyperbolic plane, then the averages of the lift g over increasing spheres converge to the average of the function f over the surface M. Heinz Huber (1956) considered the following problem on the hyperbolic plane H: Consider a strictly hyperbolic subgroup of automorphisms on H with compact quotient, and choose a conjugacy class in this group. Count the number of vertices inside an increasing ball, which are images of a fixed point x in H under automorphisms in the chosen conjugacy class, and describe the asymptotic behaviour of this number as the size of the ball goes to infinity. In this thesis, we use a well-known analogy between the hyperbolic plane and the regular tree to solve the above problems, and some related ones, on a tree. We deal mainly with regular trees, however some results incorporate more general graphs.
49
Al-Shimary, Abbas. "Applications of graph theory to quantum computation." Thesis, University of Leeds, 2013. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.608359.
Full textAbstract:
Systems with topologically ordered ground states are considered to be promising candidates for quantum memories. These systems are characterised by a degenerate ground eigenspace separated by an energy gap from the rest of the spectrum. Consequently, topologically ordered systems are resilient to local noise since local errors are suppressed by the gap. Often, knowledge of the gap is not available and a direct approach to the problem is impractical. The first half of this thesis considers the problem of estimating the energy gap of a general class of Hamiltonians in the thermodynamical limit. In particular, we consider a remarkable result from spectral graph theory known as Cheeger inequalities. Cheeger inequalities give an upper and lower bound on the spectral gap of discrete Laplaeians defined on a graph in terms of the geometric characteristics of the graph. We generalise this approach and we employ it to determine if a given discrete Hamiltonian is gapped or not in the thermodynamic limit. A large class of 2D topologically ordered systems, including the Kitaev toric code, were proven to be unstable against thermal fluctuations. There systems can store information for a finite time known as the memory lifetime. The second half of this thesis will be devoted to investigating possible theoretical ways to extend the lifetime of thc 2D toric code. Firstly, we investigate the effect lattice geometry has on the lifetime of the qubit toric code. Importantly, we demonstrate how lattice geometries can be employed to enhance topological systems with intrinsically biased couplings due to physical implementation. Secondly, we improve the error correction properties and lifetime of the generalised 2D toric code by using charge-modifying domain walls. Specifically, we show that we can inhibit the propagation of anyons by introducing domain walls, provided the masses of the anyon types of the model are imbalanced.
50
Yilma, Zelealem Belaineh. "Results in Extremal Graph and Hypergraph Theory." Research Showcase @ CMU, 2011. http://repository.cmu.edu/dissertations/49.
Full textAbstract:
In graph theory, as in many fields of mathematics, one is often interested in finding the maxima or minima of certain functions and identifying the points of optimality. We consider a variety of functions on graphs and hypegraphs and determine the structures that optimize them.
A central problem in extremal (hyper)graph theory is that of finding the maximum number of edges in a (hyper)graph that does not contain a specified forbidden substructure. Given an integer n, we consider hypergraphs on n vertices that do not contain a strong simplex, a structure closely related to and containing a simplex. We determine that, for n sufficiently large, the number of edges is maximized by a star.
We denote by F(G, r, k) the number of edge r-colorings of a graph G that do not contain a monochromatic clique of size k. Given an integer n, we consider the problem of maximizing this function over all graphs on n vertices. We determine that, for large n, the optimal structures are (k − 1)2-partite Turán graphs when r = 4 and k ∈ {3, 4} are fixed.
We call a graph F color-critical if it contains an edge whose deletion reduces the chromatic number of F and denote by F(H) the number of copies of the specified color-critical graph F that a graph H contains. Given integers n and m, we consider the minimum of F(H) over all graphs H on n vertices and m edges. The Turán number of F, denoted ex(n, F), is the largest m for which the minimum of F(H) is zero. We determine that the optimal structures are supergraphs of Tur´an graphs when n is large and ex(n, F) ≤ m ≤ ex(n, F)+cn for some c > 0.