To see the other types of publications on this topic, follow the link: Graphs.
Dissertations / Theses on the topic 'Graphs'
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 'Graphs.'
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
Hearon, Sean M. "PLANAR GRAPHS, BIPLANAR GRAPHS AND GRAPH THICKNESS." CSUSB ScholarWorks, 2016. https://scholarworks.lib.csusb.edu/etd/427.
Full textAbstract:
A graph is planar if it can be drawn on a piece of paper such that no two edges cross. The smallest complete and complete bipartite graphs that are not planar are K5 and K{3,3}. A biplanar graph is a graph whose edges can be colored using red and blue such that the red edges induce a planar subgraph and the blue edges induce a planar subgraph. In this thesis, we determine the smallest complete and complete bipartite graphs that are not biplanar.
2
Duffy, Christopher. "Homomorphisms of (j, k)-mixed graphs." Thesis, Bordeaux, 2015. http://hdl.handle.net/1828/6601.
Full textAbstract:
A mixed graph is a simple graph in which a subset of the edges have been assigned directions to form arcs. For non-negative integers j and k, a (j, k)−mixed graph is a mixed graph with j types of arcs and k types of edges. The collection of (j, k)−mixed graphs contains simple graphs ((0,1)−mixed graphs), oriented graphs ((1,0)-mixed graphs) and k−edge-coloured graphs ((0, k)−mixed graphs).
A homomorphism is a vertex mapping from one (j,k)−mixed graph to another in which edge type is preserved, and arc type and direction are preserved. An m−colouring of a (j, k)−mixed graph is a homomorphism from that graph to a target with m vertices. The (j, k)−chromatic number of a (j, k)−mixed graph is the least m such that an m−colouring exists. When (j, k) = (0, 1), we see that these definitions are consistent with the usual definitions of graph homomorphism and graph colouring. Similarly, when (j, k) = (1, 0) and (j, k) = (0, k) these definitions are consistent with the usual definitions of homomorphism and colouring for oriented graphs and k−edge-coloured graphs, respectively.
In this thesis we study the (j, k)−chromatic number and related parameters for different families of graphs, focussing particularly on the (1, 0)−chromatic number, more commonly called the oriented chromatic number, and the (0, k)−chromatic number.
In examining oriented graphs, we provide improvements to the upper and lower bounds for the oriented chromatic number of the families of oriented graphs with maximum degree 3 and 4. We generalise the work of Sherk and MacGillivray on the 2−dipath chromatic number, to consider colourings in which vertices at the ends of
iii
a directed path of length at most k must receive different colours. We examine the implications of the work of Smolikova on simple colourings to study of the oriented chromatic number of the family of oriented planar graphs.
In examining k−edge-coloured graphs we provide improvements to the upper and lower bounds for the family of 2−edge-coloured graphs with maximum degree 3. In doing so, we define the alternating 2−path chromatic number of k−edge-coloured graphs, a parameter similar in spirit to the 2−dipath chromatic number for oriented graphs. We also consider a notion of simple colouring for k−edge-coloured graphs, and show that the methods employed by Smolikova ́ for simple colourings of oriented graphs may be adapted to k−edge-coloured graphs.
In addition to considering vertex colourings, we also consider incidence colourings of both graphs and digraphs. Using systems of distinct representatives, we provide a new characterisation of the incidence chromatic number. We define the oriented incidence chromatic number and find, by way of digraph homomorphism, a connection between the oriented incidence chromatic number and the chromatic number of the underlying graph. This connection motivates our study of the oriented incidence chromatic number of symmetric complete digraphs.Graduate
3
Yang, Weihua. "Supereulerian graphs, Hamiltonicity of graphes and several extremal problems in graphs." Phd thesis, Université Paris Sud - Paris XI, 2013. http://tel.archives-ouvertes.fr/tel-00877793.
Full textAbstract:
In this thesis, we focus on the following topics: supereulerian graphs, hamiltonian line graphs, fault-tolerant Hamiltonian laceability of Cayley graphs generated by transposition trees, and several extremal problems on the (minimum and/or maximum) size of graphs under a given graph property. The thesis includes six chapters. The first one is to introduce definitions and summary the main results of the thesis, and in the last chapter we introduce the furture research of the thesis. The main studies in Chapters 2 - 5 are as follows. In Chapter 2, we explore conditions for a graph to be supereulerian.In Section 1 of Chapter 2, we characterize the graphs with minimum degree at least 2 and matching number at most 3. By using the characterization, we strengthen the result in [93] and we also address a conjecture in the paper.In Section 2 of Chapter 2, we prove that if $d(x)+d(y)\geq n-1-p(n)$ for any edge $xy\in E(G)$, then $G$ is collapsible except for several special graphs, where $p(n)=0$ for $n$ even and $p(n)=1$ for $n$ odd. As a corollary, a characterization for graphs satisfying $d(x)+d(y)\geq n-1-p(n)$ for any edge $xy\in E(G)$ to be supereulerian is obtained. This result extends the result in [21].In Section 3 of Chapter 2, we focus on a conjecture posed by Chen and Lai [Conjecture~8.6 of [33]] that every 3-edge connected and essentially 6-edge connected graph is collapsible. We find a kind of sufficient conditions for a 3-edge connected graph to be collapsible.In Chapter 3, we mainly consider the hamiltonicity of 3-connected line graphs.In the first section of Chapter 3, we give several conditions for a line graph to be hamiltonian, especially we show that every 3-connected, essentially 11-connected line graph is hamilton- connected which strengthens the result in [91].In the second section of Chapter 3, we show that every 3-connected, essentially 10-connected line graph is hamiltonian-connected.In the third section of Chapter 3, we show that 3-connected, essentially 4-connected line graph of a graph with at most 9 vertices of degree 3 is hamiltonian. Moreover, if $G$ has 10 vertices of degree 3 and its line graph is not hamiltonian, then $G$ can be contractible to the Petersen graph.In Chapter 4, we consider edge fault-tolerant hamiltonicity of Cayley graphs generated by transposition trees. We first show that for any $F\subseteq E(Cay(B:S_{n}))$, if $|F|\leq n-3$ and $n\geq4$, then there exists a hamiltonian path in $Cay(B:S_{n})-F$ between every pair of vertices which are in different partite sets. Furthermore, we strengthen the above result in the second section by showing that $Cay(S_n,B)-F$ is bipancyclic if $Cay(S_n,B)$ is not a star graph, $n\geq4$ and $|F|\leq n-3$.In Chapter 5, we consider several extremal problems on the size of graphs.In Section 1 of Chapter 5, we bounds the size of the subgraph induced by $m$ vertices of hypercubes. We show that a subgraph induced by $m$ (denote $m$ by $\sum\limits_{i=0}^ {s}2^{t_i}$, $t_0=[\log_2m]$ and $t_i= [\log_2({m-\sum\limits_{r=0}^{i-1}2 ^{t_r}})]$ for $i\geq1$) vertices of an $n$-cube (hypercube) has at most $\sum\limits_{i=0}^{s}t_i2^{t_i-1} +\sum\limits_{i=0}^{s} i\cdot2^{t_i}$ edges. As its applications, we determine the $m$-extra edge-connectivity of hypercubes for $m\leq2^{[\frac{n}2]}$ and $g$-extra edge-connectivity of the folded hypercube for $g\leq n$.In Section 2 of Chapter 5, we partially study the minimum size of graphs with a given minimum degree and a given edge degree. As an application, we characterize some kinds of minimumrestricted edge connected graphs.In Section 3 of Chapter 5, we consider the minimum size of graphs satisfying Ore-condition.
4
Badaoui, Mohamad. "G-graphs and Expander graphs." Thesis, Normandie, 2018. http://www.theses.fr/2018NORMC207/document.
Full textAbstract:
L’utilisation de l’algèbre pour résoudre des problèmes de graphes a conduit au développement de trois branches : théorie spectrale des graphes, géométrie et combinatoire des groupes et études des invariants de graphes. La notion de graphe d’expansions (invariant de graphes) est relativement récente, elle a été développée afin d’étudier la robustesse des réseaux de télécommunication. Il s’avère que la construction de familles infinies de graphes expanseurs est un problème difficile. Cette thèse traite principalement de la construction de nouvelles familles de tels graphes. Les graphes expanseurs possèdent des nombreuses applications en informatique, notamment dans la construction de certains algorithmes, en théorie de la complexité, sur les marches aléatoires (random walk), etc. En informatique théorique, ils sont utilisés pour construire des familles de codes correcteurs d’erreur. Comme nous l’avons déjà vu les familles d’expanseurs sont difficiles à construire. La plupart des constructions s'appuient sur des techniques algébriques complexes, principalement en utilisant des graphes de Cayley et des produit Zig-Zag. Dans cette thèse, nous présentons une nouvelle méthode de construction de familles infinies d’expanseurs en utilisant les G-graphes. Ceux-ci sont en quelque sorte une généralisation des graphes de Cayley. Plusieurs nouvelles familles infinies d’expanseurs sont construites, notamment la première famille d’expanseurs irréguliersApplying algebraic and combinatorics techniques to solve graph problems leads to the birthof algebraic and combinatorial graph theory. This thesis deals mainly with a crossroads questbetween the two theories, that is, the problem of constructing infinite families of expandergraphs.From a combinatorial point of view, expander graphs are sparse graphs that have strongconnectivity properties. Expanders constructions have found extensive applications in bothpure and applied mathematics. Although expanders exist in great abundance, yet their explicitconstructions, which are very desirable for applications, are in general a hard task. Mostconstructions use deep algebraic and combinatorial approaches. Following the huge amountof research published in this direction, mainly through Cayley graphs and the Zig-Zagproduct, we choose to investigate this problem from a new perspective; namely by usingG-graphs theory and spectral hypergraph theory as well as some other techniques. G-graphsare like Cayley graphs defined from groups, but they correspond to an alternative construction.The reason that stands behind our choice is first a notable identifiable link between thesetwo classes of graphs that we prove. This relation is employed significantly to get many newresults. Another reason is the general form of G-graphs, that gives us the intuition that theymust have in many cases such as the relatively high connectivity property.The adopted methodology in this thesis leads to the identification of various approaches forconstructing an infinite family of expander graphs. The effectiveness of our techniques isillustrated by presenting new infinite expander families of Cayley and G-graphs on certaingroups. Also, since expanders stand in no single stem of graph theory, this brings us toinvestigate several closely related threads from a new angle. For instance, we obtain newresults concerning the computation of spectra of certain Cayley and G-graphs, and theconstruction of several new infinite classes of integral and Hamiltonian Cayley graphs
5
Ramos, Garrido Lander. "Graph enumeration and random graphs." Doctoral thesis, Universitat Politècnica de Catalunya, 2017. http://hdl.handle.net/10803/405943.
Full textAbstract:
In this thesis we use analytic combinatorics to deal with two related problems: graph enumeration and random graphs from constrained classes of graphs. We are interested in drawing a general picture of some graph families by determining, first, how many elements are there of a given possible size (graph enumeration), and secondly, what is the typical behaviour of an element of fixed size chosen uniformly at random, when the size tends to infinity (random graphs). The problems concern graphs subject to global conditions, such as being planar and/or with restrictions on the degrees of the vertices.
In Chapter 2 we analyse random planar graphs with minimum degree two and three. Using techniques from analytic combinatorics and the concepts of core and kernel of a graph, we obtain precise asymptotic estimates and analyse relevant parameters for random graphs, such as the number of edges or the size of the core, where we obtain Gaussian limit laws. More challenging is the extremal parameter equal to the size of the largest tree attached to the core. In this case we obtain a logarithmic estimate for the expected value together with a concentration result.
In Chapter 3 we study the number of subgraphs isomorphic to a fixed graph in subcritical classes of graphs. We obtain Gaussian limit laws with linear expectation and variance when the fixed graph is 2-connected. The main tool is the analysis of infinite systems of equations by Drmota, Gittenberger and Morgenbesser, using the theory of compact operators. Computing the exact constants for the first estimates of the moments is in general out of reach. For the class of series-parallel graphs we are able to compute them in some particular interesting cases.
In Chapter 4 we enumerate (arbitrary) graphs where the degree of every vertex belongs to a fixed subset of the natural numbers. In this case the associated generating functions are divergent and our analysis uses instead the so-called configuration model. We obtain precise asymptotic estimates for the number of graphs with given number of vertices and edges and subject to the degree restriction. Our results generalize widely previous special cases, such as d-regular graphs or graphs with minimum degree at least d.En aquesta tesi utilitzem l'analítica combinatòria per treballar amb dos problemes relacionats: enumeració de grafs i grafs aleatoris de classes de grafs amb restriccions. En particular ens interessa esbossar un dibuix general de determinades famílies de grafs determinant, en primer lloc, quants grafs hi ha de cada mida possible (enumeració de grafs), i, en segon lloc, quin és el comportament típic d'un element de mida fixa triat a l'atzar uniformement, quan aquesta mida tendeix a infinit (grafs aleatoris). Els problemes en què treballem tracten amb grafs que satisfan condicions globals, com ara ésser planars, o bé tenir restriccions en el grau dels vèrtexs. En el Capítol 2 analitzem grafs planar aleatoris amb grau mínim dos i tres. Mitjançant tècniques de combinatòria analítica i els conceptes de nucli i kernel d'un graf, obtenim estimacions asimptòtiques precises i analitzem paràmetres rellevants de grafs aleatoris, com ara el nombre d'arestes o la mida del nucli, on obtenim lleis límit gaussianes. També treballem amb un paràmetre que suposa un repte més important: el paràmetre extremal que es correspon amb la mida de l'arbre més gran que penja del nucli. En aquest cas obtenim una estimació logarítmica per al seu valor esperat, juntament amb un resultat sobre la seva concentració. En el Capítol 3 estudiem el nombre de subgrafs isomorfs a un graf fix en classes de grafs subcrítiques. Quan el graf fix és biconnex, obtenim lleis límit gaussianes amb esperança i variància lineals. L'eina principal és l'anàlisi de sistemes infinits d'equacions donada per Drmota, Gittenberger i Morgenbesser, que utilitza la teoria d'operadors compactes. El càlcul de les constants exactes de la primera estimació dels moments en general es troba fora del nostre abast. Per a la classe de grafs sèrie-paral·lels podem calcular les constants en alguns casos particulars interessants. En el Capítol 4 enumerem grafs (arbitraris) el grau de cada vèrtex dels quals pertany a un subconjunt fix dels nombres naturals. En aquest cas les funcions generatrius associades són divergents i la nostra anàlisi utilitza l'anomenat model de configuració. El nostre resultat consisteix a obtenir estimacions asimptòtiques precises per al nombre de grafs amb un nombre de vèrtexs i arestes donat, amb la restricció dels graus. Aquest resultat generalitza àmpliament casos particulars existents, com ara grafs d-regulars, o grafs amb grau mínim com a mínim d.
6
Khouzam, Nelly. "A new class of brittle graphs /." Thesis, McGill University, 1986. http://digitool.Library.McGill.CA:80/R/?func=dbin-jump-full&object_id=66048.
Full text
7
Medrano, Archie T. "Super-Euclidean graphs and super-Heisenberg graphs : their spectral and graph-theoretic properties /." Diss., Connect to a 24 p. preview or request complete full text in PDF format. Access restricted to UC campuses, 1998. http://wwwlib.umi.com/cr/ucsd/fullcit?p9901440.
Full text
8
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.
9
Dusart, Jérémie. "Graph searches with applications to cocomparability graphs." Paris 7, 2014. http://www.theses.fr/2014PA077048.
Full textAbstract:
Un parcours de graphe est un mécanisme pour visiter de manière itérative les sommets d'un graphe. Cela a été une technique fondamentale dans la conception des algorithmes de graphe depuis les débuts de l'informatique. Bon nombre des premiers parcours étaient basées sur le parcours en largeur(BFS) ou en profondeur (DFS) et cela a donné des algorithmes efficaces pour les problèmes pratiques tels que la distance entre deux sommets, le diamètre, la connectivité, les problèmes de flot et la reconnaissance des graphes planaires. Le but de cette thèse est d'étudier les parcours de graphe Dans cette thèse, nous présentons des résultats généraux sur les parcours de graphe dans les graphes de cocomparabilité, mais aussi une nouvelle caractérisation des graphes de cocomparabilité et des applications des parcours de graphe pour résoudre le problème d'orientation transitive, de sous-graphe triangulé maximal, de clique séparatrice et de sommets simpliciaux. Un modèle simple et général est aussi présenté pour capturer la plupart des parcours de grapheA graph search is a mechanism for systematically visiting the vertices of a graph. It has been a fundamental technique in the design of graph algorithms since the eraarly days of computer science. Many of the early search methods were based on Breadth First Search (BFS) or Depth First Search (DFS) and resulted in efficient algorithms for practical problems such as the distance between two vertices, diameter, connectivity, network flows and the recognition of planar graphs. The purpose of this thesis is to studied the graph search. In this thesis, we present general result about graph search in cocomparability grapj, but also a new charactrization of cocomparability graph and apllications of graph search to solve the problem of transitive orientation, maximal chordal subgraph, clique perator and simplicial vertices. A simple and general framework is also presented to capture most of the well known graph search
10
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
11
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
12
Henry, Tyson Rombauer. "Interactive graph layout: The exploration of large graphs." Diss., The University of Arizona, 1992. http://hdl.handle.net/10150/185833.
Full textAbstract:
Directed and undirected graphs provide a natural notation for describing many fundamental structures of computer science. Unfortunately graphs are hard to draw in an easy to read fashion. Traditional graph layout algorithms have focused on creating good layouts for the entire graph. This approach works well with smaller graphs, but often cannot produce readable layouts for large graphs. This dissertation presents a novel methodology for viewing large graphs. The basic concept is to allow the user to interactively navigate through large graphs, learning about them in appropriately small and concise pieces. The motivation of this approach is that large graphs contain too much information to be conveyed by a single canonical layout. For a user to be able to understand the data encoded in the graph she must be able to carve up the graph into manageable pieces and then create custom layouts that match her current interests. An architecture is presented that supports graph exploration. It contains three new concepts for supporting interactive graph layout: interactive decomposition of large graphs, end-user specified layout algorithms, and parameterized layout algorithms. The mechanism for creating custom layout algorithms provides the non-programming end-user with the power to create custom layouts that are well suited for the graph at hand. New layout algorithms are created by combining existing algorithms in a hierarchical structure. This method allows the user to create layouts that accurately reflect the current data set and her current interests. In order to explore a large graph, the user must be able to break the graph into small, more manageable pieces. A methodology is presented that allows the user to apply graph traversal algorithms to large graphs to carve out reasonably sized pieces. Graph traversal algorithms can be combined using a visual programming language. This provides the user with the control to select subgraphs that are of particular interest to her. The ability to Parameterize layout algorithms provides the user with control over the layout process. The user can customize the generated layout by changing parameters to the layout algorithm. Layout algorithm parameterization is placed into an interactive framework that allows the user to iteratively fine tune the generated layout. As a proof of concept, examples are drawn from a working prototype that incorporates this methodology.
13
Macon, Lisa. "ALMOST REGULAR GRAPHS AND EDGE FACE COLORINGS OF PLANE GRAPHS." Doctoral diss., University of Central Florida, 2009. http://digital.library.ucf.edu/cdm/ref/collection/ETD/id/2480.
Full textAbstract:
Regular graphs are graphs in which all vertices have the same degree. Many properties of these graphs are known. Such graphs play an important role in modeling network configurations where equipment limitations impose a restriction on the maximum number of links emanating from a node. These limitations do not enforce strict regularity, and it becomes interesting to investigate nonregular graphs that are in some sense close to regular. This dissertation explores a particular class of almost regular graphs in detail and defines generalizations on this class. A linear-time algorithm for the creation of arbitrarily large graphs of the discussed class is provided, and a polynomial-time algorithm for recognizing graphs in the class is given. Several invariants for the class are discussed. The edge-face chromatic number χef of a plane graph G is the minimum number of colors that must be assigned to the edges and faces of G such that no edge or face of G receives the same color as an edge or face with which it is incident or adjacent. A well-known result for the upper bound of χef exists for graphs with maximum degree Δ ≥ 10. We present a tight upper bound for plane graphs with Δ = 9.Ph.D.
Department of Mathematics
Sciences
Mathematics PhD
14
Tanasescu, Mihaela-Cerasela. "Graphes, Partitions et Classes : G-graphs et leurs applications." Thesis, Antilles-Guyane, 2014. http://www.theses.fr/2014AGUY0787/document.
Full textAbstract:
Les graphes définis à partir de structures algébriques possèdent d’excellentes propriétés de symétries particulièrement intéressantes. L’exemple le plus flagrant est la notion de graphe de Cayley qui s’est révélée très riche non seulement du point de vue théorique mais aussi pratique par ses applications à de nombreux domaines incluant l’architecture des réseaux ou les machines parallèles. Néanmoins, la régularité des graphes de Cayley se révèle parfois être une limite étant donné qu’ils sont toujours sommet-transitifs et donc en particulier non pertinents pour générer des réseaux semiréguliers.Cette observation a motivé, en 2005, la définition d’une nouvelle classe de graphes définis à partir d’un groupe, appelés G-graphes. Ils possèdent aussi de nombreuses propriétés de régularité mais de manière moins restrictive.Cette thèse propose un nouveau regard sur cette classe de graphes par une approche plutôt orientée recherche opérationnelle alors que la grande majorité des études précédentes est dominée par des approches essentiellement algébriques. Nous-nous sommes alors intéressés à plusieurs questions :— La caractérisation des G-graphes : nous proposons des améliorations par rapport aux précédents résultats.— Identifier des classes de graphes comme des G-graphes grâce à des isomorphismes ou en utilisant le théorème de caractérisation.— Etudier la structure et les propriétés de ces graphes, en particulier pour de possibles applications aux réseaux : colorations semi-régulières, symétries et robustesse.— Une approche algorithmique pour la reconnaissance de cette classe avec notamment un premier exemple de cas polynomial lorsque le groupe est abélienInteractions between graph theory and group theory have already led to interesting results for both domains. Graphs defined from algebraic groups have highly symmetrical structure giving birth to interesting properties. The most famous example is Cayley graphs, which revealed to be particularly interesting both from a theoretical and a practical point of view due to their applications in several domains including network architecture or parallel machines. Nevertheless, the regularity of Cayley graphs is also a limit as they are always vertex-transitive and therefore not relevant to generate semi-regular networks. This observation motivated the definition, in 2005, of a new family of graphs defined from a group, called G-graphs. They also have many regular properties but are less restrictive. These graphs are in particular semi-regular k-partite, with a chromatic number k directly given in the group representation and they can be either transitive or not.This thesis proposes a new insight into this class of graphs using an approach based on operational research while most of previous studies have been so far dominated by algebraic approaches. Then, the thesis addresses different kind of questions:— Characterizing G-graphs: we propose improvements of previous results.— Identifying some classes of graphs as G-graphs through isomorphism or using the characterization theorem.— Studying the structure and properties of these graphs, in particular for possible applications to networks: semi-regular coloring, symmetries and robustness.— Algorithmic approach for recognizing this class with a first example of polynomial case when the group is abelian
15
Sen, Sagnik. "A contribution to the theory of graph homomorphisms and colorings." Phd thesis, Bordeaux, 2014. http://tel.archives-ouvertes.fr/tel-00960893.
Full textAbstract:
Dans cette thèse, nous considérons des questions relatives aux homomorphismes de quatre types distincts de graphes : les graphes orientés, les graphes orientables, les graphes 2-arête colorés et les graphes signés. Pour chacun des ces quatre types, nous cherchons à déterminer le nombre chromatique, le nombre de clique relatif et le nombre de clique absolu pour différentes familles de graphes planaires : les graphes planaires extérieurs, les graphes planaires extérieurs de maille fixée, les graphes planaires et les graphes planaires de maille fixée. Nous étudions également les étiquetages "2-dipath" et "L(p,q)" des graphes orientés et considérons les catégories des graphes orientables et des graphes signés. Nous étudions enfin les différentes relations pouvant exister entre ces quatre types d'homomorphismes de graphes.
16
Larsson, Patrik. "Analyzing and adapting graph algorithms for large persistent graphs." Thesis, Linköping University, Department of Computer and Information Science, 2008. http://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-15422.
Full textAbstract:
In this work, the graph database Neo4j developed by Neo Technology is presented together with some of it's functionality when it comes to accessing data as a graph. This type of data access brings the possibility to implement common graph algorithms on top of Neo4j. Examples of such algorithms are presented together with their theoretical backgrounds. These are mainly algorithms for finding shortest paths and algorithms for different graph measures such as centrality measures. The implementations that have been made are presented, as well as complexity analysis and the performance measures performed on them. The conclusions include that Neo4j is well suited for these types of implementations.
17
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.
18
Ghrab, Amine. "Graph Data Warehousing: Database and Multidimensional Modeling of Graphs." Doctoral thesis, Universite Libre de Bruxelles, 2020. https://dipot.ulb.ac.be/dspace/bitstream/2013/313535/3/ToC.pdf.
Full textAbstract:
Over the last decade, we have witnessed the emergence of networks in a wide spectrum of application domains, ranging from social and information networks to biological and transportation networks.Graphs provide a solid theoretical foundation for modeling complex networks and revealing valuable insights from both the network structure and the data embedded within its entities.As the business and social environments are getting increasingly complex and interconnected, graphs became a widespread abstraction at the core of the information infrastructure supporting those environments. Modern information systems consist of a large number of sophisticated and interacting business entities that naturally form graphs. In particular, integrating graphs into data warehouse systems received a lot of interest from both academia and industry. Indeed, data warehouses are the central enterprise's information repository and are critical for proper decision support and future planning. Graph warehousing is emerging as the field that extends current information systems with graph management and analytics capabilities. Many approaches were proposed to address the graph data warehousing challenge. These efforts laid the foundation for multidimensional modeling and analysis of graphs. However, most of the proposed approaches partially tackle the graph warehousing problem by being restricted to simple abstractions such as homogeneous graphs or ignoring important topics such as multidimensional integrity constraints and dimension hierarchies.In this dissertation, we conduct a systematic study of the graph data warehousing topic and address the key challenges of database and multidimensional modeling of graphs.We first propose GRAD, a new graph database model tailored for graph warehousing and OLAP analytics. GRAD aims to provide analysts with a set of simple, well-defined, and adaptable conceptual components to support rich semantics and perform complex analysis on graphs.Then, we define the multidimensional concepts for heterogeneous attributed graphs and highlight the new types of measures that could be derived. We project this multidimensional model on property graphs and explore how to extract the candidate multidimensional concepts and build graph cubes. Then, we extend the multidimensional model by integrating GRAD and show how GRAD facilitates multidimensional graph modeling, and enables supporting dimension hierarchies and building new types of OLAP cubes on graphs.Afterward, we present TopoGraph, a graph data warehousing framework that extends current graph warehousing models with new types of cubes and queries combining graph-oriented and OLAP querying. TopoGraph goes beyond traditional OLAP cubes, which process value-based grouping of tables, by considering also the topological properties of the graph elements. And it goes beyond current graph warehousing models by proposing new types of graph cubes. These cubes embed a rich repertoire of measures that could be represented with numerical values, with entire graphs, or as a combination of them.Finally, we propose an architecture of the graph data warehouse and describe its main building blocks and the remaining gaps. The various components of the graph warehousing framework can be effectively leveraged as a foundation for designing and building industry-grade graph data warehouses.We believe that our research in this thesis brings us a step closer towards a better understanding of graph warehousing. Yet, the models and framework we proposed are the tip of the iceberg. The marriage of graph and warehousing technologies will bring many exciting research opportunities, which we briefly discuss at the end of the thesis.Doctorat en Sciences de l'ingénieur et technologie
info:eu-repo/semantics/nonPublished
19
Zhang, Shijie. "Index-based Graph Querying and Matching in Large Graphs." Cleveland, Ohio : Case Western Reserve University, 2010. http://rave.ohiolink.edu/etdc/view?acc_num=case1263256028.
Full textAbstract:
Thesis(Ph.D.)--Case Western Reserve University, 2010Title from PDF (viewed on 2010-04-12) Department of Electrical Engineering and Computer Science (EECS) Includes abstract Includes bibliographical references and appendices Available online via the OhioLINK ETD Center
20
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
21
Neggaz, Mohammed Yessin. "Automatic classification of dynamic graphs." Thesis, Bordeaux, 2016. http://www.theses.fr/2016BORD0169/document.
Full textAbstract:
Les réseaux dynamiques sont constitués d’entités établissant des contacts les unes avec les autres dans le temps. Un défi majeur dans les réseaux dynamiques est de prédire les modèles de mobilité et de décider si l’évolution de la topologie satisfait aux exigences du succès d’un algorithme donné. Les types de dynamique résultant de ces réseaux sont variés en échelle et en nature. Par exemple,certains de ces réseaux restent connexes tout le temps; d’autres sont toujours déconnectés mais offrent toujours une sorte de connexité dans le temps et dans l’espace(connexité temporelle); d’autres sont connexes de manière récurrente, périodique,etc. Tous ces contextes peuvent être représentés sous forme de classes de graphes dynamiques correspondant à des conditions nécessaires et/ou suffisantes pour des problèmes ou algorithmes distribués donnés. Étant donné un graphe dynamique,une question naturelle est de savoir à quelles classes appartient ce graphe. Dans ce travail, nous apportons une contribution à l’automatisation de la classification de graphes dynamiques. Nous proposons des stratégies pour tester l’appartenance d’un graphe dynamique à une classe donnée et nous définissons un cadre générique pour le test de propriétés dans les graphes dynamiques. Nous explorons également le cas où aucune propriété sur le graphe n’est garantie, à travers l’étude du problème de maintien d’une forêt d’arbres couvrants dans un graphe dynamiqueDynamic networks consist of entities making contact over time with one another. A major challenge in dynamic networks is to predict mobility patterns and decide whether the evolution of the topology satisfies requirements for the successof a given algorithm. The types of dynamics resulting from these networks are varied in scale and nature. For instance, some of these networks remain connected at all times; others are always disconnected but still offer some kind of connectivity over time and space (temporal connectivity); others are recurrently connected,periodic, etc. All of these contexts can be represented as dynamic graph classes corresponding to necessary or sufficient conditions for given distributed problems or algorithms. Given a dynamic graph, a natural question to ask is to which of the classes this graph belongs. In this work we provide a contribution to the automation of dynamic graphs classification. We provide strategies for testing membership of a dynamic graph to a given class and a generic framework to test properties in dynamic graphs. We also attempt to understand what can still be done in a context where no property on the graph is guaranteed through the distributed problem of maintaining a spanning forest in highly dynamic graphs
22
Kumwenda, Khumbo. "Codes, graphs and designs related to iterated line graphs of complete graphs." Thesis, University of the Western Cape, 2011. http://etd.uwc.ac.za/index.php?module=etd&action=viewtitle&id=gen8Srv25Nme4_1742_1320645699.
Full textAbstract:
In this thesis, we describe linear codes over prime fields obtained from incidence designs of iterated line graphs of complete graphs Li(Kn) where i = 1, 2. In the binary case, results are extended to codes from neighbourhood designs of the line graphs Li+1(Kn) using certain elementary relations. Codes from incidence designs of complete graphs, Kn, and neighbourhood designs of their line graphs, L1(Kn) (the so-called triangular graphs), have been considered elsewhere by others. We consider codes from incidence designs of L1(Kn) and L2(Kn), and neighbourhood designs of L2(Kn) and L3(Kn). In each case, basic parameters of the codes are determined. Further, we introduce a family of vertex-transitive graphs ôn that are embeddable into the strong product L1(Kn) â K2, of triangular graphs and K2, a class which at first sight may seem unnatural but, on closer look, is a repository of graphs rich with combinatorial structures. For instance, unlike most regular graphs considered here and elsewhere that only come with incidence and neighbourhood designs, ôn also has what we have termed as 6-cycle designs. These are designs in which the point set contains vertices of the graph and every block contains vertices of a 6-cycle in the graph. Also, binary codes from incidence matrices of these graphs have other minimum words in addition to incidence vectors of the blocks. In addition, these graphs have induced subgraphs isomorphic to the family Hn of complete porcupines (see Definition 4.11). We describe codes from incidence matrices of ôn and Hn and determine their parameters.
23
Le, Ngoc Khang. "Detecting and Coloring some Graph Classes." Thesis, Lyon, 2018. http://www.theses.fr/2018LYSEN021/document.
Full textAbstract:
Les graphes sont des structures mathématiques utilisées pour modéliser les relations par paires entre objets. Malgré leur structure simple, les graphes ont des applications dans divers domaines tels que l'informatique, la physique, la biologie et la sociologie. L'objectif principal de ce travail est de continuer l'étude des problèmes de coloration et de détection dans le cadre de classes de graphes fermées par sous-graphes induits (que nous appelons classes de graphes héréditaires).La première classe que nous considérons est graphes sans ISK4 - les graphes qui ne contiennent aucune subdivision de en tant que sous-graphe induit. Nous montrons que le nombre chromatique de cette classe est limité à 24, une amélioration considérable par rapport à la borne existant précédemment. Nous donnons également une bien meilleure limite dans le cas sans triangle. De plus, nous prouvons qu'il existe un algorithme de complexité pour détecter cette classe, ce qui répond à une question de Chudnovsky et al. et Lévêque et al.La deuxième classe que nous étudions est celle des graphes sans trou pair et sans étoile d’articulation. Cela est motivé par l'utilisation de la technique de décomposition pour résoudre certains problèmes d'optimisation. Nous garantissons la fonction χ-bounding optimale pour cette classe. Nous montrons que la classe a rank-width bornée, ce qui implique l'existence d'un algorithme de coloration en temps polynomial. Enfin, la coloration gloutonne connexe dans les graphes sans griffes est considérée. Une façon naturelle de colorier un graphe est d'avoir un ordre de ses sommets et d'affecter pour chaque sommet la première couleur disponible. Beaucoup de recherches ont été faites pour des ordres généraux. Cependant, nous connaissons très peu de choses sur la caractérisation des bons graphes par rapport aux ordres connexes. Un graphe est bon si pour chaque sous-graphe induit connexe de , chaque ordre connexe donne à une coloration optimale. Nous donnons la caractérisation complète de bons graphes sans griffes en termes de sous-graphes induits minimaux interditsGraphs are mathematical structures used to model pairwise relations between objects. Despite their simple structures, graphs have applications in various areas like computer science, physics, biology and sociology. The main focus of this work is to continue the study of the coloring and detecting problems in the setting of graph classes closed under taking induced subgraphs (which we call hereditary graph classes). The first class we consider is ISK4-free graphs - the graphs that do not contain any subdivision of K4 as an induced subgraph. We prove that the chromatic number of this class is bounded by 24, a huge improvement compared to the best-known bound. We also give a much better bound in the triangle-free case. Furthermore, we prove that there exists an O(n 9) algorithm for detecting this class, which answers a question by Chudnovsky et al. and Lévêque et al. The second class we study is even-hole-free graphs with no star cutset. This was motivated by the use of decomposition technique in solving some optimization problems. We prove the optimal χ -bounding function for this class and show that it has bounded rank-width, which implies the existence of a polynomial-time coloring algorithm.Finally, the connected greedy coloring in claw-free graphs is considered. A natural way to color a graph is to have an order of its vertices and assign for each vertex the first available color. A lot of researches have been done for general orders. However, we know very little about the characterization of good graphs with respect to connected orders. A graph G is good if for every connected induced subgraph H of G, every connected order gives H an optimal coloring. We give the complete characterization of good claw-free graphs in terms of minimal forbidden induced subgraphs
24
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
25
Seierstad, Taral Guldahl. "The phase transition in random graphs and random graph processes." Doctoral thesis, [S.l.] : [s.n.], 2007. http://deposit.ddb.de/cgi-bin/dokserv?idn=985760044.
Full text
26
Busatto, Giorgio. "An abstract model of hierarchical graphs and hierarchical graph transformation." Oldenburg : Univ., Fachbereich Informatik, 2002. http://deposit.ddb.de/cgi-bin/dokserv?idn=967851955.
Full text
27
Irniger, Christophe-André. "Graph matching filtering databases of graphs using machine learning techniques." Berlin Aka, 2005. http://deposit.ddb.de/cgi-bin/dokserv?id=2677754&prov=M&dok_var=1&dok_ext=htm.
Full text
28
Crinion, Tim. "Chamber graphs of some geometries related to the Petersen graph." Thesis, University of Manchester, 2013. https://www.research.manchester.ac.uk/portal/en/theses/chamber-graphs-of-some-geometries-related-to-the-petersen-graph(f481f0af-7c39-4728-8928-571495d1217a).html.
Full textAbstract:
In this thesis we study the chamber graphs of the geometries ΓpA2nΓ1q, Γp3A7q, ΓpL2p11qq and ΓpL2p25qq which are related to the Petersen graph [4, 13]. In Chapter 2 we look at the chamber graph of ΓpA2nΓ1q and see what minimal paths between chambers look like. Chapter 3 finds and proves the diameter of these chamber graphs and we see what two chambers might look like if they are as far apart as possible. We discover the full automorphism group of the chamber graph. Chapters 4, 5 and 6 focus on the chamber graphs of ΓpL2p11qq,ΓpL2p25qq and Γp3A7q respectively. We ask questions such as what two chambers look like if they are as far apart as possible, and we find the automorphism groups of the chamber graphs.
29
Deering, Jessie. "Uphill & Downhill Domination in Graphs and Related Graph Parameters." Digital Commons @ East Tennessee State University, 2013. https://dc.etsu.edu/honors/103.
Full textAbstract:
Placing degree constraints on the vertices of a path allows the definitions of uphill and downhill paths. Specifically, we say that a path π = v1, v2,...vk+1 is a downhill path if for every i, 1 ≤ i ≤ k, deg(vi) ≥ deg(vi+1). Conversely, a path π = u1, u2,...uk+1 is an uphill path if for every i, 1 ≤ i ≤ k, deg(ui) ≤ deg(ui+1). We investigate graphical parameters related to downhill and uphill paths in graphs. For example, a downhill path set is a set P of vertex disjoint downhill paths such that every vertex v ∈ V belongs to at least one path in P, and the downhill path number is the minimum cardinality of a downhill path set of G. For another example, the downhill domination number of a graph G is defined to be the minimum cardinality of a set S of vertices such that every vertex in V lies on a downhill path from some vertex in S. The uphill domination number is defined as expected. We determine relationships among these invariants and other graphical parameters related to downhill and uphill paths. We also give a polynomial time algorithm to find a minimum downhill dominating set and a minimum uphill dominating set for any graph.
30
Musco, Vincenzo. "Propagation Analysis based on Software Graphs and Synthetic Data." Thesis, Lille 3, 2016. http://www.theses.fr/2016LIL30053/document.
Full textAbstract:
Les programmes sont partout dans notre vie quotidienne : les ordinateurs et les téléphones, mais aussi les frigo, les avions et ainsi de suite. L'acteur principal dans la création de ces programmes est humain les êtres. Aussi minutie qu'ils peuvent être, les humains sont connus pour faire des erreurs involontaires sans leur conscience. Ainsi, une fois une phase déjà difficile d'écriture d'un programme, ils doivent faire face à la phase de maintenance sur laquelle ils doivent faire face aux erreurs qu'ils ont eu précédemment réalisé. Toute la durée de leur tâche de développement, les développeurs doivent faire face continuellement leurs erreurs (ou leurs collègues). Cette observation clé soulève la nécessité d'aider les développeurs dans leurs tâches de développement / maintenancePrograms are everywhere in our daily life: computers and phones but also fridges, planes and so on. The main actor in the process of creating these programs is human beings. As thorough as they can be, humans are known to make involuntary errors without their awareness. Thus, once finished an already hard phase of writing a program. they have to face the maintenance phase on which they have to deal with errors they had previously made. All long their development task, developers have to continuously face their (or their colleagues) errors. This key observation arises the need of aiding developers in their development/maintenance tasks
31
Iturriaga-Velazquez, Claudia C. "Intersection graphs, fraternally orientable graphs and hamiltonian cycles." Thesis, University of Ottawa (Canada), 1994. http://hdl.handle.net/10393/6808.
Full textAbstract:
Consider a graph G(V, E), where V and E denote the vertex and edge sets of G(V, E), respectively. An orientation $\vec G$ of G(V, E) is the result of giving an orientation to the edges of G. A directed graph is fraternally oriented if for every three vertices u, v, w, the existence of the edges $u\to w$ and $v\to w$ implies that $u\to v$ or $v\to u$. A graph G is fraternally orientable if there exists an orientation $\vec G$ that is fraternally oriented. In this thesis we study some properties of fraternally orientable graphs, and we describe an algorithm to find a hamiltonian cycle in strongly connected fraternally oriented graphs $\vec G$.
32
Zhang, Weijian. "Evolving graphs and similarity-based graphs with applications." Thesis, University of Manchester, 2018. https://www.research.manchester.ac.uk/portal/en/theses/evolving-graphs-and-similaritybased-graphs-with-applications(66a23d3d-1ad0-454b-9ba0-175b566af95d).html.
Full textAbstract:
A graph is a mathematical structure for modelling the pairwise relations between objects. This thesis studies two types of graphs, namely, similarity-based graphs and evolving graphs. We look at ways to traverse an evolving graph. In particular, we examine the influence of temporal information on node centrality. In the process, we develop EvolvingGraphs.jl, a software package for analyzing time-dependent networks. We develop Etymo, a search system for discovering interesting research papers. Etymo utilizes both similarity-based graphs and evolving graphs to build a knowledge graph of research articles in order to help users to track the development of ideas. We construct content similarity-based graphs using the full text of research papers. And we extract key concepts from research papers and exploit the temporal information in research papers to construct a concepts evolving graph.
33
Townsend, Timothy Duncan. "Extremal problems on graphs, directed graphs and hypergraphs." Thesis, University of Birmingham, 2016. http://etheses.bham.ac.uk//id/eprint/6453/.
Full textAbstract:
This thesis is concerned with extremal problems on graphs and similar structures. We first study degree conditions in uniform hypergraphs that force matchings of various sizes. Our main result in this area improves bounds of Markstrom and Rucinski on the minimum d-degree which forces a perfect matching in a k-uniform hypergraph on n vertices. We then study connectivity conditions in tournaments that ensure the existence of partitions of the vertex set that satisfy various properties. In 1982 Thomassen asked whether every sufficiently strongly connected tournament T admits a partition of its vertex set into t vertex classes such that the subtournament induced on T by each class is strongly k-connected. Our main result in this area implies an affirmative answer to this question. Finally we investigate the typical structure of graphs and directed graphs with some forbidden subgraphs. We answer a question of Cherlin by finding the typical structure of triangle-free oriented graphs. Moreover, our results generalise to forbidden transitive tournaments and forbidden oriented cycles of any order, and also apply to digraphs. We also determine, for all k > 5, the typical structure of graphs that do not contain an induced 2k-cycle. This verifies a conjecture of Balogh and Butterfield.
34
Sivaraman, Vaidyanathan. "Some Topics concerning Graphs, Signed Graphs and Matroids." The Ohio State University, 2012. http://rave.ohiolink.edu/etdc/view?acc_num=osu1354645035.
Full text
35
Ross, Christopher Jon. "Properties of Random Threshold and Bipartite Graphs." The Ohio State University, 2011. http://rave.ohiolink.edu/etdc/view?acc_num=osu1306296991.
Full text
36
Yerger, Carl Roger Jr. "Color-critical graphs on surfaces." Diss., Georgia Institute of Technology, 2010. http://hdl.handle.net/1853/37197.
Full textAbstract:
A graph is (t+1)-critical if it is not t-colorable, but every proper subgraph is. In this thesis, we study the structure of critical graphs on higher surfaces. One major result in this area is Carsten Thomassen's proof that there are finitely many 6-critical graphs on a fixed surface. This proof involves a structural theorem about a precolored cycle C of length q. In general terms, he proves that a coloring, c, of C, can be extended inside the cycle, or there exists a subgraph H with at most a number of vertices exponential in q such that c can not be extended to a 5-coloring of H. In Chapter 2, we proved an alternative proof that reduces the number of vertices in H to be cubic in q. In Chapter 3, we find the nine 6-critical graphs among all graphs embeddable on the Klein bottle. In Chapter 4, we prove a result concerning critical graphs related to an analogue of Steinberg's conjecture for higher surfaces. We show that if G is a 4-critical graph embedded on surface S, with Euler genus g and has no cycles of length four through ten, then G has at most 2442g + 37 vertices.
37
Le, Tien Nam. "Patterns in Large Graphs." Thesis, Lyon, 2018. http://www.theses.fr/2018LYSEN079/document.
Full textAbstract:
Un graphe est un ensemble de noeuds, ensemble de liens reliant des paires de noeuds. Avec la quantité accumulée de données collectées, il existe un intérêt croissant pour la compréhension des structures et du comportement de très grands graphes. Néanmoins, l’augmentation rapide de la taille des grands graphes rend l’étude de tous les graphes de moins en moins efficace. Ainsi, il existe une demande impérieuse pour des méthodes plus efficaces pour étudier de grands graphes sans nécessiter la connaissance de tous les graphes. Une méthode prometteuse pour comprendre le comportement de grands graphes consiste à exploiter des propriétés spécifiques de structures locales, telles que la taille des grappes ou la présence locale d’un motif spécifique, c’est-à-dire un graphe donné (généralement petit). Un exemple classique de la théorie des graphes (cas avérés de la conjecture d'Erdos-Hajnal) est que, si un graphe de grande taille ne contient pas de motif spécifique, il doit alors avoir un ensemble de noeuds liés par paires ou non liés, de taille exponentiellement plus grande que prévue. Cette thèse abordera certains aspects de deux questions fondamentales de la théorie des graphes concernant la présence, en abondance ou à peine, d’un motif donné dans un grand graphe : - Le grand graphe peut-il être partitionné en copies du motif ? - Le grand graphe contient-il une copie du motif ? Nous discuterons de certaines des conjectures les plus connues de la théorie des graphes sur ce sujet: les conjectures de Tutte sur les flots dans les graphes et la conjecture d'Erdos-Hajnal mentionnée ci-dessus, et présenterons des preuves pour plusieurs conjectures connexes - y compris la conjecture de Barát-Thomassen, une conjecture de Haggkvist et Krissell, un cas particulier de la conjecture de Jaeger-Linial-Payan-Tarsi, une conjecture de Berger et al, et une autre d'Albouker et alA graph is a set of nodes, together links connecting pairs of nodes. With the accumulating amount of data collected, there is a growing interest in understanding the structures and behavior of very large graphs. Nevertheless, the rapid increasing in size of large graphs makes studying the entire graphs becomes less and less efficient. Thus, there is a compelling demand for more effective methods to study large graphs without requiring the knowledge of the graphs in whole. One promising method to understand the behavior of large graphs is via exploiting specific properties of local structures, such as the size of clusters or the presence locally of some specific pattern, i.e. a given (usually small) graph. A classical example from Graph Theory (proven cases of the Erdos-Hajnal conjecture) is that if a large graph does not contain some specific pattern, then it must have a set of nodes pairwise linked or not linked of size exponentially larger than expected. This thesis will address some aspects of two fundamental questions in Graph Theory about the presence, abundantly or scarcely, of a given pattern in some large graph: - Can the large graph be partitioned into copies of the pattern? - Does the large graph contain any copy of the pattern?We will discuss some of the most well-known conjectures in Graph Theory on this topic: the Tutte's flow conjectures on flows in graphs and the Erdos-Hajnal conjecture mentioned above, and present proofs for several related conjectures -- including the Barát-Thomassen conjecture, a conjecture of Haggkvist and Krissell, a special case of Jaeger-Linial-Payan-Tarsi's conjecture, a conjecture of Berger et al, and another one by Albouker et al
38
Muntaner, Batlle Francesc Antoni. "Magic graphs." Doctoral thesis, Universitat Politècnica de Catalunya, 2001. http://hdl.handle.net/10803/7017.
Full textAbstract:
DE LA TESISSi un graf G admet un etiquetament super edge magic, aleshores G es diu que és un graf super edge màgic. La tesis està principalment enfocada a l'estudi del conjunt de grafs que admeten etiquetaments super edge magic així com també a desenvolupar relacions entre aquest tipus d'etiquetaments i altres etiquetaments molt estudiats com ara els etiquetaments graciosos i armònics, entre d'altres. De fet, els etiquetaments super edge magic serveixen com nexe d'unió entre diferents tipus d'etiquetaments, i per tant moltes relacions entre etiquetaments poden ser obtingudes d'aquesta forma.
A la tesis també es proposa una nova manera de pensar en la ja famosa conjectura que afirma que tots els arbres admeten un etiquetament super edge magic. Això és, per a cada arbre T trobam un arbre super edge magic T' que conté a T com a subgraf, i l'ordre de T'no és massa gran quan el comparam amb l'ordre de T .
Un problema de naturalesa similar al problema anterior, en el sentit que intentam trobar un graf super edge magic lo més petit possible i que contengui a cert tipus de grafs, i que ha estat completament resolt a la tesis es pot enunciar com segueix.
Problema: Quin és un graf conexe G super edge magic d'ordre més petit que conté al graf complet
Kn com a subgraf?.
La solució d'aquest problema és prou interessant ja que relaciona els etiquetaments super edge magic amb un concepte clàssic de la teoria aditiva de nombres com són els conjunts de Sidon dèbils, també coneguts com well spread sets.De fet, aquesta no és la única vegada que el concepte de conjunt de Sidon apareix a la tesis. També quan a la tesis es tracta el tema de la deficiència , els conjunts de Sidon són d'una gran utilitat. La deficiencia super edge magic d'un graf és una manera de mesurar quan d'aprop està un graf de ser super edge magic. Tècnicament parlant, la deficiència super edge magic d'un graf
G es defineix com el mínim número de vèrtexs aillats amb els que hem d'unir
G perque el graf resultant sigui super edge magic. Si d'aquesta manera no aconseguim mai que el graf resultant sigui super edge magic, aleshores deim que la deficiència del graf és infinita. A la tesis, calculam la deficiència super edge magic de moltes families importants de grafs, i a més donam alguns resultats generals, sobre aquest concepte.
Per acabar aquest document, simplement diré que al llarg de la tesis molts d'exemples que completen la tesis, i que fan la seva lectura més agradable i entenible han estat introduits.
OF THESIS
If a graph G admits a super edge magic labeling, then G is called a super edge magic graph. The thesis is mainly devoted to study the set of graphs which admit super edge magic labelings as well as to stablish and study relations with other well known labelings.
For instance, graceful and harmonic labelings, among others, since many relations among labelings can be obtained using super edge magic labelings as the link.
In the thesis we also provide a new approach to the already famous conjecture that claims that every tree is super edge magic. We attack this problem by finding for any given tree T a super edge magic tree T' that contains T as a subgraph, and the order of T'is not too large if we compare it with the order of T .
A similar problem to this one, in the sense of finding small host super edge magic graphs for certain type of graphs, which is completely solved in the thesis, is the following one.
Problem: Find the smallest order of a connected super edge magic graph G that contains the complete graph Kn as a subgraph.
The solution of this problem has particular interest since it relates super edge magic labelings with the additive number theoretical concept of weak Sidon set, also known as well spread set. In fact , this is not the only time that this concept appears in the thesis.
Also when studying the super edge magic deficiency, additive number theory and in particular well spread sets have proven to be very useful. The super edge magic deficiency of graph is a way of measuring how close is graph to be super edge magic.
Properly speaking, the super edge magic deficiency of a graph G is defined to be the minimum number of isolated vertices that we have to union G with, so that the resulting graph is super edge magic. If no matter how many isolated vertices we union G with, the resulting graph is never super edge magic, then the super edge magic deficiency is defined to be infinity. In the thesis, we compute the super edge magic deficiency of may important families of graphs and we also provide some general results, involving this concept.
Finally, and in order to bring this document to its end, I will just mention that many examples that improve the clarity of the thesis and makes it easy to read, can be found along the hole work.
39
Schreyer, Jens. "Olique graphs." [S.l.] : [s.n.], 2005. http://deposit.ddb.de/cgi-bin/dokserv?idn=981044115.
Full text
40
Lloyd, Philip. "Phantom Graphs." Saechsische Landesbibliothek- Staats- und Universitaetsbibliothek Dresden, 2012. http://nbn-resolving.de/urn:nbn:de:bsz:14-qucosa-82682.
Full text
41
Rakow, Matthew Allen. "Quilted Graphs." NCSU, 2010. http://www.lib.ncsu.edu/theses/available/etd-12212009-170407/.
Full textAbstract:
Layered graphs find use in many applications today, including flow charts, business processes, and genealogical diagrams. Traditional means of depicting this data are similar to depictions of unlayered node-link graphs, with each layer's nodes grouped into a line. This type of diagram becomes increasingly difficult to use as the number of nodes and links increases, presenting a scalability issue. We suggest quilted graphs as a better scaling alternative to traditional depictions. Quilted graphs draw on the strengths of matrix-style depictions already in use for unlayered graphs to reduce the impact of graph size on graph legibility. By combining positional encoding from matrix-style depictions with other means of link encoding, they can also be made more compact than matrix depictions. We have developed prototype software to create these graphs, and interactive behavior has been added to enhance their usability. Several applications of quilted graphs are suggested and demonstrated in place of existing diagrams including SAS's activity-based management (ABM) data, online analytical processing (OLAP) hierarchies, and genealogical diagrams.
42
StehliÌk, MateÌŒj. "Critical graphs." Thesis, Imperial College London, 2003. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.401887.
Full text
43
Al-Tarimshawy, Ali Sltan Ali. "Singular graphs." Thesis, University of East Anglia, 2018. https://ueaeprints.uea.ac.uk/68916/.
Full textAbstract:
Let Γ be a simple graph on a finite vertex set V and let A be its adjacency matrix. Then Γ is said to be singular if and only if 0 is an eigenvalue of A. The nullity (singularity) of Γ, denoted by null(Γ), is the algebraic multiplicity of the eigenvalue 0 in the spectrum of Γ. In 1957, Collatz and Sinogowitz [57] posed the problem of characterizing singular graphs. Singular graphs have important applications in mathematics and science. In chemistry the importance of singular graphs lies in the fact that a singular molecular graph, with vertices formed by atoms, edges corresponding to bonds between the atoms in the molecule, often is associated to compounds that are more reactive or unstable. By this reason, the chemists have a great interest in this problem. The general problem of characterising singular graphs is easy to state but it seems too difficult at this time. In this work, we investigate this problem for graphs in general and graphs with a vertex transitive group G of automorphisms. In some cases we determine the nullity of such graphs. We characterize singular Cayley graphs over cyclic groups. We show that vertex transitive graphs where |V| is prime are non-singular. The relationship between the irreducible representations of G and the eigenspaces of Γ is studied.
44
Reese, Tyler Michael. "Kirchhoff Graphs." Digital WPI, 2018. https://digitalcommons.wpi.edu/etd-dissertations/72.
Full textAbstract:
Kirchhoff's laws are well-studied for electrical networks with voltage and current sources, and edges marked by resistors. Kirchhoff's voltage law states that the sum of voltages around any circuit of the network graph is zero, while Kirchhoff's current law states that the sum of the currents along any cutset of the network graph is zero. Given a network, these requirements may be encoded by the circuit matrix and cutset matrix of the network graph. The columns of these matrices are indexed by the edges of the network graph, and their row spaces are orthogonal complements. For (chemical or electrochemical) reaction networks, one must naturally study the opposite problem, beginning with the stoichiometric matrix rather than the network graph. This leads to the following question: given such a matrix, what is a suitable graphic rendering of a network that properly visualizes the underlying chemical reactions? Although we can not expect uniqueness, the goal is to prove existence of such a graph for any matrix. Specifically, we study Kirchhoff graphs, originally introduced by Fehribach. Mathematically, Kirchhoff graphs represent the orthocomplementarity of the row space and null space of integer-valued matrices. After introducing the definition of Kirchhoff graphs, we will survey Kirchhoff graphs in the context of several diverse branches of mathematics. Beginning with combinatorial group theory, we consider Cayley graphs of the additive group of vector spaces, and resolve the existence problem for matrices over finite fields. Moving to linear algebra, we draw a number of conclusions based on a purely matrix-theoretic definition of Kirchhoff graphs, specifically regarding the number of vector edges. Next we observe a geometric approach, reviewing James Clerk Maxwell's theory of reciprocal figures, and presenting a number of results on Kirchhoff duality. We then turn to algebraic combinatorics, where we study equitable partitions, quotients, and graph automorphisms. In addition to classifying the matrices that are the quotient of an equitable partition, we demonstrate that many Kirchhoff graphs arise from equitable edge-partitions of directed graphs. Finally we study matroids, where we review Tutte's algorithm for determining when a binary matroid is graphic, and extend this method to show that every binary matroid is Kirchhoff. The underlying theme throughout each of these investigations is determining new ways to both recognize and construct Kirchhoff graphs.
45
Kahale, Nabil. "Expander graphs." Thesis, Massachusetts Institute of Technology, 1993. http://hdl.handle.net/1721.1/12511.
Full text
46
Wehmuth, Klaus. "Multiaspect graphs." Laboratório Nacional de Computação Científica, 2016. https://tede.lncc.br/handle/tede/244.
Full textAbstract:
Submitted by Maria Cristina (library@lncc.br) on 2017-04-06T18:25:05Z
No. of bitstreams: 1
Klaus_Thesis.pdf: 4909850 bytes, checksum: cd68a30c3bae22dc6ea75b6cb4dc6368 (MD5)Approved for entry into archive by Maria Cristina (library@lncc.br) on 2017-04-06T18:25:18Z (GMT) No. of bitstreams: 1 Klaus_Thesis.pdf: 4909850 bytes, checksum: cd68a30c3bae22dc6ea75b6cb4dc6368 (MD5)
Made available in DSpace on 2017-04-06T18:25:28Z (GMT). No. of bitstreams: 1 Klaus_Thesis.pdf: 4909850 bytes, checksum: cd68a30c3bae22dc6ea75b6cb4dc6368 (MD5) Previous issue date: 2016-06-22
Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq)
Different graph generalizations have been recently used in an ad hoc manner to represent time-varying complex networks, i.e. networks in which vertices and edges may vary in time. Similar constructions have also been used to represent multilayer networks, i.e. systems formed by distinct interdependent layers where each layer can be seen as a complex network. In this thesis, we introduce the concept of MultiAspect Graph (MAG). We show that a MAG is isomorphic to a directed graph, which is an important theoretical result because this allows the use of the isomorphic directed graph as a tool to analyze both the properties of a MAG and the behavior of dynamic processes over a MAG. In our proposal, the set of vertices, layers, time instants, or any other independent feature of the system being modelled is considered as an aspect of the MAG. For instance, a MAG is able to represent multilayer or time-varying networks, while both concepts can also be combined to represent a multilayer time-varying network. Since the MAG structure admits an arbitrary (finite) number of aspects, it hence introduces a powerful modelling abstraction for networked complex systems. Further, we present algebraic representations and basic algorithms for MAGs, constructed from well-known graph algorithms, such as degree computing, Breadth First Search (BFS), and Depth First Search (DFS). These algorithms adapted to the MAG context can be used as primitives for building other more sophisticated MAG algorithms. Building upon the basic MAG concept, we also present derived applications, such as a MAG-based unifying model for time-varying graphs as well as MAG-based centrality notions.
Recentemente, várias generalizações de grafos têm sido propostas para tratar problemas específicos envolvendo redes complexas variantes no tempo e redes complexas multi-camadas. Essas representações são propostas de maneira adequada para resolver problemas específicos, mas não são adequadas para uso geral e muitas vezes são incompatíveis entre si. Nesta tese apresentamos o conceito de Grafo Multi-Aspectos (MAG), que é uma generalização de grafos capaz de representar redes variantes no tempo, redes multi-camadas e redes simultaneamente multi-camadas e variantes no tempo. Mostramos que todo MAG é isomorfo a um grafo direcionado, o que é um importante resultado teórico. Com base nesse resultado é possível utilizar o conhecimento previamente obtido em teoria de grafos para problemas envolvendo MAGs. Dessa maneira, torna-se possível criar representações algébricas para MAGs com características semelhantes às encontradas nas representações para grafos orientados. Além disso, pode-se construir algoritmos básicos para MAGs através da adaptação de algoritmos conhecidos para grafos. Esses algoritmos básicos podem servir como modelo para criação de outros algoritmos para MAGs, bem como serem utilizados como primitivas para construção de novos algoritmos. Utilizando essas primitivas, introduzimos o conceito de centralidades em MAGs, bem como construimos algoritmos apropriadas para calcular essas centralidades.
47
Akrida, E. "Temporal graphs." Thesis, University of Liverpool, 2016. http://livrepository.liverpool.ac.uk/3004504/.
Full textAbstract:
This thesis studies Temporal Graphs, also called Temporal Networks. More specifically, the project aimed to carry out research on the properties of Temporal Graphs, both in general and in specific classes of the model, as well as examine and develop algorithms for solving problems in temporal graph theory. Temporal graphs are graphs that change -often dramatically- as time progresses, however maintaining a fixed number of vertices. We investigate a range of different temporal graph models depending on the way these changes occur, e.g., in a deterministic or probabilistic fashion, in a discrete-time or continuous-time context, etc. In particular, we examine connectivity matters in a model of temporal graphs where changes happen at random discrete moments in time. Within this framework, we also investigated a model of continuous time and developed algorithms that solve connectivity problems in that model. Furthermore, we study temporal network design issues for the discrete-time model of temporal graphs, both in cases where changes happen deterministically and in cases where changes happen at random discrete-time moments. We also introduce and investigate temporal network flows, where we define the problem of computing a maximum flow in a given temporal network and discuss efficient ways of solving it.
48
Al-Kaseasbeh, Saba Zakariya. "Ideal Graphs." Diss., North Dakota State University, 2014. https://hdl.handle.net/10365/27268.
Full textAbstract:
In this dissertation, we explore various types of graphs that can be associated to a commutative ring with identity. In particular, if R is a commutative ring with identity, we consider a number of graphs with the vertex set being the set of proper ideals; various edge sets defined via different ideal theoretic conditions give visual insights and structure theorems pertaining to the multiplicative ideal theory of R. We characterize the interplay between the ideal theory and various properties of these graphs including diameter and connectivity.
49
Traxl, Dominik. "Deep graphs." Doctoral thesis, Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät, 2017. http://dx.doi.org/10.18452/17785.
Full textAbstract:
Netzwerk Theorie hat sich als besonders zweckdienlich in der Darstellung von Systemen herausgestellt. Jedoch fehlen in der Netzwerkdarstellung von Systemen noch immer essentielle Bausteine um diese generell zur Datenanalyse heranzuziehen zu können. Allen voran fehlt es an einer expliziten Assoziation von Informationen mit den Knoten und Kanten eines Netzwerks und einer schlüssigen Darstellung von Gruppen von Knoten und deren Relationen auf verschiedenen Skalen. Das Hauptaugenmerk dieser Dissertation ist der Einbindung dieser Bausteine in eine verallgemeinerte Rahmenstruktur gewidmet. Diese Rahmenstruktur - Deep Graphs - ist in der Lage als Bindeglied zwischen einer vereinheitlichten und generalisierten Netzwerkdarstellung von Systemen und den Methoden der Statistik und des maschinellen Lernens zu fungieren (Software: https://github.com/deepgraph/deepgraph). Anwendungen meiner Rahmenstruktur werden dargestellt. Ich konstruiere einen Regenfall Deep Graph und analysiere raumzeitliche Extrem-Regenfallcluster. Auf Grundlage dieses Graphs liefere ich einen statistischen Beleg, dass die Größenverteilung dieser Cluster einem exponentiell gedämpften Potenzgesetz folgt. Mit Hilfe eines generativen Sturm-Modells zeige ich, dass die exponentielle Dämpfung der beobachteten Größenverteilung durch das Vorhandensein von Landmasse auf unserem Planeten zustande kommen könnte. Dann verknüpfe ich zwei hochauflösende Satelliten-Produkte um raumzeitliche Cluster von Feuer-betroffenen Gebieten im brasilianischen Amazonas zu identifizieren und deren Brandeigenschaften zu charakterisieren. Zuletzt untersuche ich den Einfluss von weißem Rauschen und der globalen Kopplungsstärke auf die maximale Synchronisierbarkeit von Oszillatoren-Netzwerken für eine Vielzahl von Oszillatoren-Modellen, welche durch ein breites Spektrum an Netzwerktopologien gekoppelt sind. Ich finde ein allgemeingültiges sigmoidales Skalierungsverhalten, und validiere dieses mit einem geeignetem Regressionsmodell.Network theory has proven to be a powerful instrument in the representation of complex systems. Yet, even in its latest and most general form (i.e., multilayer networks), it is still lacking essential qualities to serve as a general data analysis framework. These include, most importantly, an explicit association of information with the nodes and edges of a network, and a conclusive representation of groups of nodes and their respective interrelations on different scales. The implementation of these qualities into a generalized framework is the primary contribution of this dissertation. By doing so, I show how my framework - deep graphs - is capable of acting as a go-between, joining a unified and generalized network representation of systems with the tools and methods developed in statistics and machine learning. A software package accompanies this dissertation, see https://github.com/deepgraph/deepgraph. A number of applications of my framework are demonstrated. I construct a rainfall deep graph and conduct an analysis of spatio-temporal extreme rainfall clusters. Based on the constructed deep graph, I provide statistical evidence that the size distribution of these clusters is best approximated by an exponentially truncated powerlaw. By means of a generative storm-track model, I argue that the exponential truncation of the observed distribution could be caused by the presence of land masses. Then, I combine two high-resolution satellite products to identify spatio-temporal clusters of fire-affected areas in the Brazilian Amazon and characterize their land use specific burning conditions. Finally, I investigate the effects of white noise and global coupling strength on the maximum degree of synchronization for a variety of oscillator models coupled according to a broad spectrum of network topologies. I find a general sigmoidal scaling and validate it with a suitable regression model.
50
Yang, Joyce C. "Interval Graphs." Scholarship @ Claremont, 2016. https://scholarship.claremont.edu/hmc_theses/83.
Full textAbstract:
We examine the problem of counting interval graphs. We answer the question posed by Hanlon, of whether the formal power series generating function of the number of interval graphs on n vertices has a positive radius of convergence. We have found that it is zero. We have obtained a lower bound and an upper bound on the number of interval graphs on n vertices. We also study the application of interval graphs to the dynamic storage allocation problem. Dynamic storage allocation has been shown to be NP-complete by Stockmeyer. Coloring interval graphs on-line has applications to dynamic storage allocation. The most colors used by Kierstead's algorithm is 3 ω -2, where ω is the size of the largest clique in the graph. We determine a lower bound on the colors used. One such lower bound is 2 ω -1.