To see the other types of publications on this topic, follow the link: Digraph.
Dissertations / Theses on the topic 'Digraph'
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 'Digraph.'
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
Moura, Phablo Fernando Soares. "Graph colorings and digraph subdivisions." Universidade de São Paulo, 2017. http://www.teses.usp.br/teses/disponiveis/45/45134/tde-23052017-100619/.
Full textAbstract:
The vertex coloring problem is a classic problem in graph theory that asks for a partition of the vertex set into a minimum number of stable sets. This thesis presents our studies on three vertex (re)coloring problems on graphs and on a problem related to a long-standing conjecture on subdivision of digraphs. Firstly, we address the convex recoloring problem in which an arbitrarily colored graph G is given and one wishes to find a minimum weight recoloring such that each color class induces a connected subgraph of G. We show inapproximability results, introduce an integer linear programming (ILP) formulation that models the problem and present some computational experiments using a column generation approach. The k-fold coloring problem is a generalization of the classic vertex coloring problem and consists in covering the vertex set of a graph by a minimum number of stable sets in such a way that every vertex is covered by at least k (possibly identical) stable sets. We present an ILP formulation for this problem and show a detailed polyhedral study of the polytope associated with this formulation. The last coloring problem studied in this thesis is the proper orientation problem. It consists in orienting the edge set of a given graph so that adjacent vertices have different in-degrees and the maximum in-degree is minimized. Clearly, the in-degrees induce a partition of the vertex set into stable sets, that is, a coloring (in the conventional sense) of the vertices. Our contributions in this problem are on hardness and upper bounds for bipartite graphs. Finally, we study a problem related to a conjecture of Mader from the eighties on subdivision of digraphs. This conjecture states that, for every acyclic digraph H, there exists an integer f(H) such that every digraph with minimum out-degree at least f(H) contains a subdivision of H as a subdigraph. We show evidences for this conjecture by proving that it holds for some particular classes of acyclic digraphs.O problema de coloração de grafos é um problema clássico em teoria dos grafos cujo objetivo é particionar o conjunto de vértices em um número mínimo de conjuntos estáveis. Nesta tese apresentamos nossas contribuições sobre três problemas de coloração de grafos e um problema relacionado a uma antiga conjectura sobre subdivisão de digrafos. Primeiramente, abordamos o problema de recoloração convexa no qual é dado um grafo arbitrariamente colorido G e deseja-se encontrar uma recoloração de peso mínimo tal que cada classe de cor induza um subgrafo conexo de G. Mostramos resultados sobre inaproximabilidade, introduzimos uma formulação linear inteira que modela esse problema, e apresentamos alguns resultados computacionais usando uma abordagem de geração de colunas. O problema de k-upla coloração é uma generalização do problema clássico de coloração de vértices e consiste em cobrir o conjunto de vértices de um grafo com uma quantidade mínima de conjuntos estáveis de tal forma que cada vértice seja coberto por pelo menos k conjuntos estáveis (possivelmente idênticos). Apresentamos uma formulação linear inteira para esse problema e fazemos um estudo detalhado do politopo associado a essa formulação. O último problema de coloração estudado nesta tese é o problema de orientação própria. Ele consiste em orientar o conjunto de arestas de um dado grafo de tal forma que vértices adjacentes possuam graus de entrada distintos e o maior grau de entrada seja minimizado. Claramente, os graus de entrada induzem uma partição do conjunto de vértices em conjuntos estáveis, ou seja, induzem uma coloração (no sentido convencional) dos vértices. Nossas contribuições nesse problema são em complexidade computacional e limitantes superiores para grafos bipartidos. Finalmente, estudamos um problema relacionado a uma conjectura de Mader, dos anos oitenta, sobre subdivisão de digrafos. Esta conjectura afirma que, para cada digrafo acíclico H, existe um inteiro f(H) tal que todo digrafo com grau mínimo de saída pelo menos f(H) contém uma subdivisão de H como subdigrafo. Damos evidências para essa conjectura mostrando que ela é válida para classes particulares de digrafos acíclicos.
2
Kim, Eun Jung. "Parameterized algorithms on digraph and constraint satisfaction problems." Thesis, Royal Holloway, University of London, 2010. http://repository.royalholloway.ac.uk/items/4e3a1971-6e98-97a9-8e4f-9e1fdc76066a/9/.
Full textAbstract:
While polynomial-time approximation algorithms remain a dominant notion in tackling computationally hard problems, the framework of parameterized complexity has been emerging rapidly in recent years. Roughly speaking, the analytic framework of parameterized complexity attempts to grasp the difference between problems which admit O(c^k . poly(n))-time algorithms such as Vertex Cover, and problems like Dominating Set for which essentially brute-force O(n^k)-algorithms are best possible until now. Problems of the former type is said to be fixed-parameter tractable (FPT) and those of the latter type are regarded intractable. In this thesis, we investigate some problems on directed graphs and a number of constraint satisfaction problems (CSPs) from the parameterized perspective. We develop fixed-parameter algorithms for some digraph problems. In particular, we focus on the basic problem of finding a tree with certain property embedded in a given digraph. New or improved fpt-algorthms are presented for finding an out-branching with many or few leaves (Directed Maximum Leaf, Directed Minimum Leaf problems). For acyclic digraphs, Directed Maximum Leaf is shown to allow a kernel with linear number of vertices. We suggest a kernel for Directed Minimum Leaf with quadratic number of vertices. An improved fpt-algorithm for finding k-Out-Tree is presented and this algorithm is incorporated as a subroutine to obtain a better algorithm for Directed Minimum Leaf. In the second part of this thesis, we concentrate on several CSPs in which we want to maximize the number of satisfied constraints and consider parameterization "above tight lower bound" for these problems. To deal with this type of parameterization, we present a new method called SABEM using probabilistic approach and applying harmonic analysis on pseudo-boolean functions. Using SABEM we show that a number of CSPs admit polynomial kernels, thus being fixed-parameter tractable. Moreover, we suggest some problem-specific combinatorial approaches to Max-2-Sat and a wide special class of Max-Lin2, which lead to a kernel of smaller size than what can be obtained using SABEM for respective problems.
3
Montalva, Medel Marco. "Problèmes type "Feedback Set" et comportement dynamique des réseaux de régulation." Phd thesis, Université de Grenoble, 2011. http://tel.archives-ouvertes.fr/tel-00629549.
Full textAbstract:
Dans la nature existent de nomreux exemples de systèmes dynamiques complexes: systèmes neuronaux, communautés, écosystèmes, réseaux de régulation génétiques, etc. Ces derniers, en particulier, sont de notre intérêt et sont souvent modélisés par des réseaux booléens. Un réseau booléenne peut être considérée comme un digraphe, où les sommets correspondent à des gènes ou de produits de gènes, tandis que les arcs indiquent les interactions entre eux. Une niveau d'expression des gènes est modélisé par des valeurs binaires, 0 ou 1, indiquant deux états de la transcription, soit activité, soit inactivité, respectivement, et ce niveau change dans le temps selon certains fonction locaux d'activation qui dépend des états d'un ensemble de nœuds (les gènes). L'effet conjoint des fonctions d'activation locale définit une fonction de transition globale: ainsi, le autre élément nécessaire dans la description du modèle est fonction de mise à jour, qui détermine quand chaque nœud doit être mis à jour, et donc, comme les fonctions local se combinent dans une fonction globale (en d'autres termes, il doit décrire les temps relative de les activités régulatoires). Comme un réseau booléen avec n sommets a 2 ^ n états globaux, à partir d'un état de départ, et dans un nombre fini de mises à jour, le réseau atteindra un fixe point ou un cycle limite, appelée attracteurs qui sont souvent associées à des phénotypes distincts (états-cellulaire) définis par les patrons d'activité des gènes. Un réseau de régulation Booléenne (REBN) est un réseau Booléen où chaque interaction entre les éléments de la réseau correspond soit à une interaction positif ou d'une interaction négative. Ainsi, le digraphe interaction associée à une REBN est un digraphe signé où un circuit est appelé positif (négatif) si le nombre de ses arcs négative est pair (impair). Dans ce contexte, il y a diverses études sur l'importance du les circuits positif et négatifs dans le comportement dynamique de différents systèmes en Biologie. En effet le point de départ de cette thèse est basée sur un résultat en disant que le nombre maximal de points fixes d'une REBN dépend d'un ensemble de cardinalité minimale qu'intersecte tous les cycles positifs (également dénommés positive feedback vertex set) du digraphe signé associé. D'autre part, un autre aspect important de circuits est leur rôle dans la robustesse des réseaux booléens par rapport différents types de mise à jour déterministe. Dans ce contexte, un élément clé mathématique est le update digraphe qui est un digraphe étiqueté associé à la réseau dont les étiquettes sur les arcs sont définies comme suit: un arc (u,v) est dit être positif si l'état de sommet u est mis à jour en même temps ou après que celle de v, et négative sinon. Ainsi, un cycle dans le digraphe étiqueté est dite positive (négative) si tous ses arcs sont positifs (négatifs). Cela laisse en évidence que parler de "positif" et "négatif" a des significations différentes selon le contex: digraphes signé ou digraphes étiquetés. Ainsi, nous allons voir dans cette thèse, les relations entre les feedback sets et la dynamique des réseaux Booléens à travers l'étude analytique de ces deux fondamentaux objets mathématiques: le digraphe (de connexion) signé et l'update digraphe.
4
Oliveira, Ana Karolinna Maia de. "Subdivisions de digraphes." Thesis, Nice, 2014. http://www.theses.fr/2014NICE4084/document.
Full textAbstract:
Dans ce travail, nous considérons le problème suivant : étant donné un graphe orienté D, contient-il une subdivision d’un digraphe fixé F ? Nous pensons qu’il existe une dichotomie entre les instances polynomiales et NP-complètes. Nous donnons plusieurs exemples pour les deux cas. En particulier, sauf pour cinq instances, nous sommes capable de classer tous les digraphes d’ordre 4. Alors que toutes les preuves NP-complétude sont faites par réduction de une version du problème 2-linkage en digraphes, nous utilisons différents outils algorithmiques pour prouver la solvabilité en temps polynomial de certains cas, certains d’entre eux impliquant des algorithmes relativement complexes. Les techniques varient des simples algorithmes de force brute, aux algorithmes basés sur des calculs maximale de flot, et aux décompositions en anses des digraphes fortement connexes, entre autres. Pour terminer, nous traitons le cas particulier où F étant une union disjointe de cycles dirigés. En particulier, nous montrons que les cycles dirigés de longueur au moins 3 possède la Propriété d’Erdos-Pósa : pour tout n, il existe un entier tn tel que pour tout digraphe D, soit D a n cycles dirigés disjoints de longueur au moins 3, soit il y a un ensemble T d’au plus tn sommets qui intersecte tous les cycles dirigés de longueur au moins 3. De ce résultat, nous déduisons que si F est l’union disjointe de cycles dirigés de longueur au plus 3, alors on peut décider en temps polynomial si un digraphe contient une subdivision de FIn this work, we consider the following problem: Given a directed graph D, does it contain a subdivision of a prescribed digraph F? We believe that there is a dichotomy between NP-complete and polynomial-time solvable instances of this problem. We present many examples of both cases. In particular, except for five instances, we are able to classify all the digraphs F of order 4.While all NP-hardness proofs are made by reduction from some version of the 2-linkage problem in digraphs, we use different algorithmic tools for proving polynomial-time solvability of certain instances, some of them involving relatively complicated algorithms. The techniques vary from easy brute force algorithms, algorithms based on maximum-flow calculations, handle decompositions of strongly connected digraphs, among others. Finally, we treat the very special case of F being the disjoint union of directed cycles. In particular, we show that the directed cycles of length at least 3 have the Erdos-Pósa Property: for every n, there exists an integer tn such that for every digraph D, either D contains n disjoint directed cycles of length at least 3, or there is a set T of tn vertices that meets every directed cycle of length at least 3. From this result, we deduce that if F is the disjoint union of directed cycles of length at most 3, then one can decide in polynomial time if a digraph contains a subdivision of F
5
Li, Ruijuan. "k-ordered graphs & out-arc pancyclicity on digraphs." Aachen Mainz, 2009. http://d-nb.info/994128894/04.
Full text
6
Bajo, Calderon Erica. "An Exploration on the Hamiltonicity of Cayley Digraphs." Youngstown State University / OhioLINK, 2021. http://rave.ohiolink.edu/etdc/view?acc_num=ysu161982054497591.
Full text
7
Kutz, Martin. "The Angel problem, positional games, and digraph roots strategies and complexity /." [S.l. : s.n.], 2004. http://www.diss.fu-berlin.de/2004/250/index.html.
Full text
8
Kelly, Emma Marie. "Application of a digraph model-based approach to system fault diagnostics." Thesis, Loughborough University, 2007. https://dspace.lboro.ac.uk/2134/34430.
Full textAbstract:
The issue of fault diagnostics is a dominant factor concerning current engineering systems. Information regarding possible failures is required in order to minimise disruption caused to functionality. A method proposed in this research utilises digraphs to model the information flow within an application system. Digraphs are comprised from a set of nodes representing system process variables or component failure modes. The nodes are connected by signed edges thus illustrating the influence, be it positive or negative, one node has on another. System fault diagnostics is conducted through a procedure of back-tracing in the digraph from a known deviating variable. A computational method has been developed to conduct this process. Comparisons are made between retrieved transmitter readings and those expected whilst the system is in a known operating mode. Any noted deviations are assumed to indicate the presence of a failure. The digraph diagnostic method is applied to three systems of increasing complexity; a simple water tank, an industrial based test stand of an aircraft fuel system and the Boeing 777-200 fuel system. This research includes transient system effects; the rate of change of a parameter is taken into consideration as a means of monitoring the system dynamically. The validity of the results achieved are evaluated, along with the development of a 'honing-in' strategy to highlight the most probable fault cause for a given abnormal scenario. Finally, the effectiveness and scalability issues associated with the application of the digraph method in system fault diagnostics are addressed.
9
Ghazal, Salman. "Étude de la conjecture de Seymour sur le second voisinage." Phd thesis, Université Claude Bernard - Lyon I, 2011. http://tel.archives-ouvertes.fr/tel-00744560.
Full textAbstract:
Soit D un digraphe simple (sans cycle orienté de longueur 2 ). En 1990, P. Seymour a conjecturé que D a un sommet v avec un second voisinage extérieur au moins aussi grand que son (premier) voisinage extérieur [1]. Cette conjecture est connue sous le nom de la conjecture du second voisinage du Seymour (SNC). Cette conjecture, si elle est vraie, impliquerait, un cas spécial plus faible (mais important) de la conjecture de Caccetta et Häggkvist [2] proposé en 1978 : tout digraphe D avec un degré extérieur minimum au moins égale à jV (D)j=k a un cycle orienté de longueur au plus k. Le cas particulier est k = 3, et le cas faible exige les deux : le degré extérieur minimum et le degré intérieur minimum de D sont au moins égaux à jV (D)j=k. La conjecture de Seymour restreinte au tournoi est connue sous le nom de conjecture de Dean [1]. En 1996, Fisher [3] a prouvé la conjecture de Dean en utilisant un argument de probabilité. En 2003, Chen, Shen et Yuster [4] ont démontré que tout digraphe a un sommet v tel que d+(v) _ d++(v) où =0.657298..... est l'unique racine de l'équation 2x3 + x2 - 1 = 0. En 2000, Havet et Thomassé [5] ont donné une preuve combinatoire de la conjecture de Dean, en utilisant un outil appelé l'ordre médian. Ils ont démontré que le dernier sommet d'un tel ordre a toujours un second voisinage extérieur au moins aussi grand que son voisinage extérieur. En 2007, Fidler et Yuster [6] ont utilisé l'ordre médian et un autre outil qui s'appelle le digraphe de dépendance afin de prouver la conjecture de Seymour pour tout digraphe D ayant un degré minimum jV (D)j 2. Ils l'ont montré pour tout tournoi où manque un autre sous-tournoi. El Sahili a conjecturé que pour tout D, il existe un completion T de D et un ordre médian de T tel que le denier sommet a un second voisinage extérieur au moins aussi grand que son voisinage extérieur (EC). Il est clair que, EC implique SNC. Cependant, EC propose une méthode afin de résoudre la SNC. En général, on oriente les non arcs de D de manière appropriée, afin d'obtenir un tournoi T et on essaie de trouver un sommet particulier (le denier sommet d'un ordre médian) avec la propriété désirée. Clairement, grâce aux résultats de [5] et [6], la EC est valable pour tournoi, et tout tournoi où manque un autre sous-tournoi. Nous allons vérifier EC pour tout digraphe D ayant un degré minimum jV (D)j 2. Alors, EC est vraie pour tout digraphe où la SNC est déjà connue d'être vraie non trivialement. Nous sommes aussi intéressés à la version pondérée de SNC et EC. En réalité, Fidler et Yuster [6] ont utilisé les digraphes de dépendance comme un outil supplémentaire et le fait que la SNC pondérée est vraie pour les tournois afin de prouver la SNC pour tout digraphe D ayant un degré minimum1 jV (D)j 2. Nous allons définir le digraphe de dépendance de façon plus générale et qui convient à n'importe quel digraphe. Nous allons utiliser le digraphe de dépendance et l'ordre médian comme des outils dans nos contributions à cette conjecture. Suivant la méthode proposée par la EC, nous démontrons la version pondérée de EC, et par conséquent la SNC, pour les classes des digraphes suivants : Digraphes où manque une étoile généralisée, soleil, étoile, ou un graphe complété. En outre, nous prouvons la EC, et par conséquent la SNC, pour digraphes où manque un peigne et digraphe où manque un graphe complet moins 2 arêtes indépendantes ou moins les arêtes d'une cycle de longueur 5. Par ailleurs, nous prouvons la EC, et par conséquent la SNC, pour les digraphes où manque n étoiles disjointes, sous certaines conditions sur les deux degrés minimum du digraphe de dépendance. Des conditions plus faible sont exigées dans le cas n = 1; 2; 3. Dans certains cas, on trouve au moins deux sommets avec la propriété désirée.
10
Smith, Heather Christina. "Zero Divisors among Digraphs." VCU Scholars Compass, 2010. http://scholarscompass.vcu.edu/etd/2120.
Full textAbstract:
This thesis generalizes to digraphs certain recent results about graphs. There are special digraphs C such that AxC is isomorphic to BxC for some pair of distinct digraphs A and B. Lovasz named these digraphs C zero-divisors and completely characterized their structure. Knowing that all directed cycles are zero-divisors, we focus on the following problem: Given any directed cycle D and any digraph A, enumerate all digraphs B such that AxD is isomorphic to BxD. From our result for cycles, we generalize to an arbitrary zero-divisor C, developing upper and lower bounds for the collection of digraphs B satisfying AxC isomorphic to BxC.
11
Seidler, Steffen. "Über Minoren gerichteter Graphen." Master's thesis, Saechsische Landesbibliothek- Staats- und Universitaetsbibliothek Dresden, 2011. http://nbn-resolving.de/urn:nbn:de:bsz:14-qucosa-68153.
Full textAbstract:
Seit 1983 begründet die Publikationsreihe "Graph Minors" von N. Robertson und P.D. Seymour im Wesentlichen die Minorentheorie mit mächtigen Hilfsmitteln wie der Baumzerlegung und weitreichenden Resultaten wie dem Minorensatz. Für gerichtete Graphen existiert allerdings noch keine einheitliche Minorentheorie und verschiedene Ansätze werden in dieser Arbeit systematisiert.
Einige gerichtete Versionen der Baumzerlegung (gerichtete Baumzerlegung nach B. Reed, arboreale, D- und DAG-Zerlegung) werden unter einheitlichen Aspekten untersucht. Die D-Weite ist dabei besonders vielversprechend. Enge Verbindungen zu zwei gerichteten Räuber-und-Gendarmen-Spielen werden unter analogen Aspekten betrachtet und sind wichtige Hilfsmittel.
Der zentrale Begriff des Minoren ist im Wesentlichen für ungerichtete Graphen definiert und eine gerichtete Version wirft einige Probleme auf, welche untersucht werden. In \"Directed Tree-Width\" schlugen T. Johnson, N. Robertson, P.D. Seymour und R. Thomas 2001 einen Kompromiss vor. Durch Einschränkung der möglichen Kontraktionen soll der gewonnen Minorenbegriff mit einigen fundamentalen Anforderungen vereinbar sein und trotzdem ein mächtiges Werkzeug darstellen. Dieser Ansatz wird mit einer Anforderungsliste systematisch verfolgt und schrittweise Einschränkungen betrachtet. Die gerichtete Version topologischer Minoren ist dabei besonders vielversprechend.
Die Minorentheorie gerichteter Graphen wird auf reduzible Flussgraphen angewandt. Wesentliche Resultate sind Konstruktionen arborealer und D-Zerlegungen mit Weite <2, sowie Gegenbeispiele für die Beschränktheit der DAG-Weite. Analoge Resultate folgen für die jeweiligen gerichteten Räuber-und-Gendarmen-Spiele.
12
Manion, Kendall. "A Lexicographic Product Cancellation Property for Digraphs." VCU Scholars Compass, 2012. http://scholarscompass.vcu.edu/etd/2932.
Full textAbstract:
There are four prominent product graphs in graph theory: Cartesian, strong, direct, and lexicographic. Of these four product graphs, the lexicographic product graph is the least studied. Lexicographic products are not commutative but still have some interesting properties. This paper begins with basic definitions of graph theory, including the definition of a graph, that are needed to understand theorems and proofs that come later. The paper then discusses the lexicographic product of digraphs, denoted $G \circ H$, for some digraphs $G$ and $H$. The paper concludes by proving a cancellation property for the lexicographic product of digraphs $G$, $H$, $A$, and $B$: if $G \circ H \cong A \circ B$ and $|V(G)| = |V(A)|$, then $G \cong A$. It also proves additional cancellation properties for lexicographic product digraphs and the author hopes the final result will provide further insight into tournaments.
13
Conde, Colom Josep. "Contribucions a l'estudi dels grafs i digrafs propers als de Moore." Doctoral thesis, Universitat de Lleida, 2013. http://hdl.handle.net/10803/110573.
Full textAbstract:
El principal objectiu d'aquesta tesi és el de contribuir a l'estudi de l'existència i classificació dels
grafs i digrafs que puguin admetre el màxim nombre de vèrtexs sota determinades condicions
donats el grau i el diàmetre. Aquest estudi consta de tres parts ben diferenciades, una sobre
digrafs i dos sobre grafs.
En el treball relacionat amb els digrafs demostrem que els digrafs quasi de Moore de diàmetre k =
3 i qualsevol grau no existeixen. Així mateix provem la no existència dels digrafs quasi de Moore
de diàmetre 4 i qualsevol grau assumint la irreductibilitat en Q[x] de certs polinomis.
En quan als grafs ens hem centrat en l'existència dels de grau d, diàmetre 2 i defecte 2, anomenats
(d,2,2)-grafs i assumint la irreductibilitat en Q[x] de certs polinomis provem que no existeixen
per a cap grau. A més provem que no existeixen per a graus entre 4 i 50.
Finalment estudiem els grafs radials de Moore de grau d i radi k. Proposem diferents mesures per
classificar-los d'acord a la proximitat de les seves propietats a les d'un graf de Moore i ordenem
segons aquestes mesures tots els grafs radials de Moore en els casos (d,k) = {(3,2), (3,3), (4,2)}.El principal objetivo de esta tesis es el de contribuir al estudio de la existencia y clasificación de los grafos y digrafos que puedan admitir el máximo número de vértices bajo determinadas condiciones dados el grado y el diámetro. Este estudio consta de tres partes bien diferenciadas, una sobre digrafos y dos sobre grafos. En el trabajo relacionado con los digrafos demostramos que los digrafos casi de Moore de diámetro k = 3 y cualquier grado no existen. Asimismo probamos la no existencia de los digrafos casi de Moore de diámetro 4 y cualquier grado suponiendo la irreducibilidad en Q[x] de ciertos polinomios. En cuanto a los grafos nos hemos centrado en la existencia de los de grado d, diámetro 2 y defecto 2, llamados (d,2,2)-grafos y suponiendo la irreducibilidad en Q[x] de ciertos polinomios probamos que no existen para ningún grado. Además probamos que no existen para grados entre 4 y 50. Finalmente estudiamos los grafos radiales de Moore de grado d y radio k. Proponemos diferentes medidas para clasificarlos de acuerdo a la proximidad de sus propiedades a las de un grafo de Moore y ordenamos según estas medidas todos los grafos radiales de Moore en los casos (d, k) = {(3,2), (3,3), (4,2)}.
The main goal of this thesis is to contribute to the study of the existence and classification of graphs and digraphs that can achieve the maximum number of vertices under certain conditions given the degree and the diameter. This study consists of three differenciated parts, one on digraphs and two on graphs. The work on digraphs focuses on almost Moore digraphs. We prove that they do not exist for diameter 3 and any degree. Besides, we prove the non-existence of almost Moore digraphs of diameter 4 assuming the irreducibility in Q[x] of certain polynomials. Concerning graphs, we discuss the existence of graphs of degree d, diameter 2 and defect 2. Assuming the irreducibility in Q[x] of certain polynomials we prove their non existence. We also show they do not exist for degrees between 4 and 50. Finally we study radial Moore graphs of degree d and radius k. We propose different measures for classifying them in terms of their proximity to extremal properties of a Moore graph. By means of our measures, we are able to enumerate all radial Moore graphs for the cases (d, k) = {(3.2), (3.3), (4.2)}.
14
Peterson, Nicholas Richard. "On Random k-Out Graphs with Preferential Attachment." The Ohio State University, 2013. http://rave.ohiolink.edu/etdc/view?acc_num=osu1370527839.
Full text
15
de, Oliveira Oliveira Mateus. "Combinatorial Slice Theory." Doctoral thesis, KTH, Teoretisk datalogi, TCS, 2013. http://urn.kb.se/resolve?urn=urn:nbn:se:kth:diva-134211.
Full textAbstract:
Slices are digraphs that can be composed together to form larger digraphs.In this thesis we introduce the foundations of a theory whose aim is to provide ways of defining and manipulating infinite families of combinatorial objects such as graphs, partial orders, logical equations etc. We give special attentionto objects that can be represented as sequences of slices. We have successfully applied our theory to obtain novel results in three fields: concurrency theory,combinatorics and logic. Some notable results are: Concurrency Theory: We prove that inclusion and emptiness of intersection of the causalbehavior of bounded Petri nets are decidable. These problems had been open for almost two decades. We introduce an algorithm to transitively reduce infinite familiesof DAGs. This algorithm allows us to operate with partial order languages defined via distinct formalisms, such as, Mazurkiewicztrace languages and message sequence chart languages. Combinatorics: For each constant z ∈ N, we define the notion of z-topological or-der for digraphs, and use it as a point of connection between the monadic second order logic of graphs and directed width measures, such as directed path-width and cycle-rank. Through this connection we establish the polynomial time solvability of a large numberof natural counting problems on digraphs admitting z-topological orderings. Logic: We introduce an ordered version of equational logic. We show thatthe validity problem for this logic is fixed parameter tractable withrespect to the depth of the proof DAG, and solvable in polynomial time with respect to several notions of width of the equations being proved. In this way we establish the polynomial time provability of equations that can be out of reach of techniques based on completion and heuristic search.QC 20131120
16
Mullican, Cristina. "Characterizing Cancellation Graphs." VCU Scholars Compass, 2014. http://scholarscompass.vcu.edu/etd/3412.
Full textAbstract:
A cancellation graph G is one for which given any graph C, we have G\times C\cong X\times C implies G\cong X. In this thesis, we characterize all bipartite cancellation graphs. In addition, we characterize all solutions X to G\times C\cong X\times C for bipartite G. A characterization of non-bipartite cancellation graphs is yet to be found. We present some examples of solutions X to G\times C\cong X\times C for non-bipartite G, an example of a non-bipartite cancellation graph, and a conjecture regarding non-bipartite cancellation graphs.
17
Martínez, Barona Berenice. "(1, ≤ ℓ)-identifying codes in digraphs and graphs." Doctoral thesis, Universitat Politècnica de Catalunya, 2020. http://hdl.handle.net/10803/669726.
Full textAbstract:
The main subject of this PhD thesis is the study of (1,=l)-identifying codes in digraphs. The results presented in this work are divided into three parts. The first one focusses on the structural properties of digraphs admitting a (1,=l)-identifying code for l=2. In the second part, we deal with the study of (1,=l)-identifying codes in line digraphs. Finally, in the third part we approach the problem from an algebraic perspective.A (1,=l)-identifying code in a digraph D is a dominating subset C of vertices of D such that all distinct subsets of vertices of cardinality at most l have distinct closed in-neighbourhoods within C. In the first part of the results, we prove that if D is a digraph admitting a (1,=l)-identifying code, then l is at most the minimum in-degree of the digraph plus one. Once this upper bound is established, we give some sufficient conditions for a digraph D, with minimum in-degree at least one, to admit a (1,=l)-identifying code for l equal to the minimum in-degree of the digraph or the minimum in-degree plus one. As a corollary, a result by Laihonen published in 2008 (that states that a k-regular graph with girth at least 7 admits a (1,=k)-identifying code) is extended to any graph of minimum degree k at least 2 and girth at least 7. Moreover, we show that every 1-in-regular digraph has a (1,=2)-identifying code if and only if the girth of the digraph is at least 5. We also characterise all the 2-in-regular digraphs admitting a (1,=l)-identifying code for l=2,3.In the second part, we prove that every line digraph of minimum in-degree 1 does not admit a (1,=l)-identifying code for l=3. Then, we give a characterisation of a line digraph of a digraph different from a directed cycle of length 4 and minimum in-degree 1 admitting a (1,=2)-identifying code. The identifying number of a digraph D, is the minimum size among all the identifying codes of D. We establish for digraphs without digons (symmetric arcs) with both vertices of in-degree 1 that the identifying number of its line digraph, is lower bounded by the number of arcs of D minus the number of vertices with out-degree at least one. Thus, we show that the identifying number of the line digraph of a digraph D attains the equality when Dhavea 1-factor with minimum in-degree 2 and without digons with both vertices of in-degree 2. We conclude by giving an algorithm to provide identifying codes in oriented digraphs with minimum in-degree at least 2 and minimum out-degree at least 1.In the third part, we give some sufficient algebraic and combinatorial conditions for a 2-in-regular digraph to admit a (1,=l)-identifying code for l=2, and for l=3 by combining the results of the first part of this thesis with some algebraic results. As far as we know, it is the first time that the spectral graph theory has been applied to the identifying codes. We present a new method to obtain an upper bound on l for digraphs by considering the positive and negative entries of eigenvectors associated with a negative eigenvalue of the adjacency matrix of the digraph. Likewise, we analyse the possible scope of using the eigenvalue zero for the same purpose. The results obtained in the directed case can also be applied to graphs.El principal tema de esta tesis doctoral es el estudio de los (1,=l)-códigos identificadores en digrafos. Los resultados presentados en este trabajo están divididos en tres partes. La primera se centra en las propiedades estructurales de los digrafos que admiten un (1,=l)-código identificador para l=2. En la segunda parte, nos enfocamos en el estudio de (1,=l)-códigos identificadores en digrafos línea. Finalmente, en la tercera parte abordamos el problema desde una perspectiva algebraica.Un (1,=l)-código identificador en un digrafo Des un subconjunto Cde vértices dominante en D tal que todos los subconjuntos de vértices de cardinalidad como máximo l tienen distinta in-vecindad cerrada dentro de C. En la primera parte de los resultados, probamos que si D es un digrafo que admite un (1,=l)-código identificador, entonces l es como máximo el mínimo in-grado del digrafo más uno. Una vez que esta cota superior quedaestablecida, damos algunas condiciones suficientes para que un digrafo D, conmínimo in-grado al menos 1, admita un (1,=l)-código indentificador paral igual al mínimo in-grado y para l igual al mínimo in-grado más uno. Como corolario, un resultado de Laihonen publicado en 2008 (que establece que un grafo k-regular con cintura al menos 7 admite un (1,=k)-código identificador) es extendido a cualquier grafo con mínimo grado al menos k=2y cintura al menos 7. Más aún, probamos que todo digrafo 1-in-regular tiene un (1,=2)-código identificador si y sólo si su cintura es al menos 5. Así mismo, caracterizamos todos los digrafos 2-in-regulares que admiten un (1,=l)-código identificador para l=2,3.En la segunda parte, probamos que todo digrafo línea de mínimo in-grado 1 no admite un (1,=l)-código identificador para l=3. También, damos una caracterización de los digrafos línea de un digrafo distinto de un ciclo dirigido de longitud 4 y mínimo in-grado 1, que admiten un (1,=2)-código identificador. El número de identificación de un digrafo D es el mínimo cardinal entre todos los códigos identificadores de D. Establecemos para digrafos sin dígonos (arcos simétricos) con ambos vértices de in-grado 1 queel número de identificación de su digrafo líneaestá acotado inferiormente por el número de arcos del digrafo originalmenos el número de vértices con ex-grado al menos uno. Por lo tanto, demostramos que el número de identificacióndel digrafo línea de un digrafo alcanza la igualdad cuando el digrafo originaltiene un 1-factor con mínimo in-grado 2 y no tienedígonos con ambos vértices de in-grado 2. Concluímos dando un algoritmo para construir códigos identificadores en digrafos orientados con mínimo in-grado al menos 2 y mínimo ex-grado al menos 1.En la tercera parte, damos algunas condiciones suficientes tanto algebraicas como combinatorias para que un digrafo 2-in-regular admita un (1,=l)-código identificador para l=2,3, combinando los resultados de la primera parte de esta tesis con algunos resultados algebraicos. Hasta donde sabemos, es la primera vez que la teoría espectral de grafos se ha aplicado al estudio de los códigos identificadores. Presentamos un nuevo método para obtener una cota superior de lpara digrafos, considerando las entradas positivas y negativas de los vectores propios asociados aun valor propio negativo de la matriz de adyacencia del digrafo. Del mismo modo, analizamos el posible alcance del uso del valor propio cero para el mismo propósito. Los resultados obtenidosen el caso dirigido también pueden aplicarse a grafos
18
Meyer, Marie. "Polytopes Associated to Graph Laplacians." UKnowledge, 2018. https://uknowledge.uky.edu/math_etds/54.
Full textAbstract:
Graphs provide interesting ways to generate families of lattice polytopes. In particular, one can use matrices encoding the information of a finite graph to define vertices of a polytope. This dissertation initiates the study of the Laplacian simplex, PG, obtained from a finite graph G by taking the convex hull of the columns of the Laplacian matrix for G. The Laplacian simplex is extended through the use of a parallel construction with a finite digraph D to obtain the Laplacian polytope, PD.
Basic properties of both families of simplices, PG and PD, are established using techniques from Ehrhart theory. Motivated by a well-known conjecture in the field, our investigation focuses on reflexivity, the integer decomposition property, and unimodality of Ehrhart h*-vectors of these polytopes. A systematic investigation of PG for trees, cycles, and complete graphs is provided, which is enhanced by an investigation of PD for cyclic digraphs. We form intriguing connections with other families of simplices and produce G and D such that the h*-vectors of PG and PD exhibit extremal behavior.
19
COUTO, Maria Socorro Duarte da Silva. "Modelagem matemática para seleção de áreas prioritárias para conservação [manuscrito]: métodos, cenários e contribuições para a gestão territorial em Goiás." Universidade Federal de Goiás, 2009. http://repositorio.bc.ufg.br/tede/handle/tde/339.
Full textAbstract:
Made available in DSpace on 2014-07-29T12:05:38Z (GMT). No. of bitstreams: 1
Tese_Maria_Socorro.pdf: 6409428 bytes, checksum: a9c7fda760fff59683cd1cc07cf49788 (MD5)
Previous issue date: 2009-03-22Item withdrawn by Carla Ferreira (carlaferreira66@gmail.com) on 2014-07-29T13:37:22Z Item was in collections: Doutorado em Ciências Ambientais (PRPG) (ID: 53) No. of bitstreams: 1 Tese_Maria_Socorro.pdf: 6409428 bytes, checksum: a9c7fda760fff59683cd1cc07cf49788 (MD5)
Item reinstated by Carla Ferreira (carlaferreira66@gmail.com) on 2014-07-29T13:40:12Z Item was in collections: Doutorado em Ciências Ambientais (PRPG) (ID: 53) No. of bitstreams: 1 Tese_Maria_Socorro.pdf: 6409428 bytes, checksum: a9c7fda760fff59683cd1cc07cf49788 (MD5)
The efforts to minimize the growing loss of habitats and threatens to biodiversity are increasingly based on objective criteria, which allow prioritize areas and species in need of preservation, taking into account the limitations in both natural and economic resources. These criteria are fundamental for the reserve selection and design, mainly at regions severely affected by land use intensification. In particular, the use of mathematical modeling, enabling the identification of more efficient alternatives, is an important subsidy to conservation challenge. Specifically, in this dissertation we present a new approach for the selection of priority areas for conservation, which considers both the quality and ecological feasibility of the remnant vegetation in the Cerrado areas of the State of Goiás, as well as the practical and legal aspects regarding the use of watersheds for territorial management. This proposal, based on a non-linear mathematical model, allows the parameters to vary according to the socialeconomical and environmental interests, thus generating distinct solutions and scenarios. Among the possible outcomes, we highlight as an "optimum" solution, the one with a large number remnant vegetation areas within riparian environments, which serves the purpose of strengthening spatial connectivity and natural corridors. In fact, this model can be used either to promote the conservation of large remnant vegetation patches, as well as to optimize the restoration of degraded areas, mainly in riparian environments, through the generation of alternative spatial patterns aiming at a more efficient connectivity in highly converted areas
Os esforços para amenizar a crescente perda da biodiversidade e de habitats estão sendo baseados, cada vez mais, na adoção de critérios objetivos, os quais permitem priorizar áreas e/ou espécies a serem preservadas, levando em consideração a limitação de recursos naturais e econômicos. Estes critérios são fundamentais para a seleção de reservas, principalmente para as regiões onde ocorre maior intensificação do uso do solo. Em particular, o uso de modelagem matemática, ao possibilitar a identificação de alternativas mais eficazes, constituise em importante subsídio aos problemas de conservação. Especificamente, nesta tese, apresentamos um modelo matemático não-linear de seleção de áreas prioritárias para conservação, que considerou tanto a qualidade e viabilidade ecológica das áreas de vegetação remanescente do Cerrado goiano a partir do uso de dados e critérios ambientais por meio da paisagem, quanto à praticidade e a legalidade do uso de bacias hidrográficas para gestão. Este modelo permite variar parâmetros de acordo com os interesses sócio-econômicos e ambientais, gerando distintas soluções e cenários. Entre estas soluções, destacamos uma solução ótima que prioriza as áreas de vegetação remanescente com elevada porcentagem de ambientes ripários, valorizando a vizinhança e a conectividade entre elas, formando corredores naturais ou viabilizando sua formação. O modelo proposto pode contribuir tanto para valorização das áreas de vegetação remanescente em propostas de conservação, quanto otimizar a restauração de áreas degradadas, principalmente de ambientes ripários, que favorecem a sua interligação
20
Gwellem, Chrys. "Decompositions, Packings, and Coverings of Complete Directed Gaphs with a 3-Circuit and a Pendent Arc." Digital Commons @ East Tennessee State University, 2007. https://dc.etsu.edu/etd/2029.
Full textAbstract:
In the study of Graph theory, there are eight orientations of the complete graph on three vertices with a pendant edge, K3 ∪ {e}. Two of these are the 3-circuit with a pendant arc and the other six are transitive triples with a pendant arc. Necessary and sufficient conditions are given for decompositions, packings, and coverings of the complete digraph with the two 3-circuit with a pendant arc orientations.
21
Oikawa, Márcio Katsumi. "Geração de expressões algébricas para processos de negócio usando reduções de digrafos série-paralelo." Universidade de São Paulo, 2008. http://www.teses.usp.br/teses/disponiveis/45/45134/tde-27102008-100359/.
Full textAbstract:
Modelagem e controle de execução são duas abordagens do gerenciamento de processos de negócio que, embora complementares, têm se desenvolvido independentemente. Por um lado, a modelagem é normalmente conduzida por especialistas de negócio e explora aspectos semânticos do processo. Por outro lado, o controle de execução estuda mecanismos consistentes e eficientes de implementação. Este trabalho apresenta um método algorítmico que relaciona modelagem e controle de execução, por meio da geração de expressões algébricas a partir de digrafos acíclicos. Por hipótese, assumimos que modelos de processos de negócio são formados por estruturas baseadas em grafos, e mecanismos de controle de execução são baseados na interpretação de expressões de álgebra de processos. Para a geração de expressões algébricas, esta tese apresenta as propriedades topológicas de digrafos série-paralelo e define um sistema de transformação baseado em redução de digrafos. Além disso, um algoritmo de identificação de digrafos série-paralelo e geração de expressões algébricas é apresentado. O texto também discute o tratamento de digrafos que não são série-paralelo e apresenta, para alguns desses casos, soluções baseadas em mudanças topológicas. Finalmente, o algoritmo é ilustrado com o estudo de caso de uma aplicação real.Modeling and execution control are complementary approaches of business process management that have been developed independently. On one hand, modeling is usually performed by business specialists and explores semantical aspects of the business process. On other hand, execution control studies consistent and efficient mechanisms for implementation. This work presents an algorithmic method which joins modeling and execution control through algebraic expression generation from acyclic digraphs. By hypothesis, we assume that business process models are defined by graph structures, and execution control mechanisms are based on interpretation of process algebra expressions. For algebraic expression generation, this thesis presents the topological properties of series-parallel digraphs and defines a transformation system based on digraph reduction. Therefore, we present an algorithm for identification of series-parallel digraphs and generation of algebraic expressions. This work also discusses the treatment of non-series-parallel digraphs and presents solutions based on topological changing for some cases. Finally, the algorithm is illustrated with a case study based on a real system.
22
Franco, Álvaro Junio Pereira. "Algoritmos para junções em digrafos acíclicos e uma aplicação na Antropologia." Universidade de São Paulo, 2013. http://www.teses.usp.br/teses/disponiveis/45/45134/tde-13022014-083516/.
Full textAbstract:
Neste trabalho consideramos um problema da Antropologia. A modelagem de sociedades e casamentos de indivíduos é feita com grafos mistos e encontrar caminhos disjuntos é uma questão central no problema. O problema é NP-completo e, quando visto como um problema parametrizado, ele é W[1]-difícil. Alguns subproblemas que surgem durante o processo de obter uma solução para o problema, envolvem caminhos disjuntos e podem ser resolvidos em tempo polinomial. Implementamos algoritmos polinomiais que são usados em uma ferramenta desenvolvida para solucionar o problema na Antropologia considerado. Nossa solução funcionou bem para as sociedades fornecidas pelos nossos parceiros.In this work we consider a problem from the Anthropology. The model of the societies and the marriages of individuals is done with mixed graphs and to find disjoint paths is a central question in the problem. The problem is NP-complete and W[1]-hard when it is considered a parameterized problem. Some subproblems that arise during the process to obtain a solution for the problem, involve disjoint paths and can be solved in polynomial time. We implemented some polynomial algorithms that are used in a tool developed to solve the problem in the Anthropology considered. Our solution worked well for the societies provided by our partners.
23
Shen, Jian. "Exponents of primitive digraphs." Thesis, National Library of Canada = Bibliothèque nationale du Canada, 1998. http://www.collectionscanada.ca/obj/s4/f2/dsk2/tape15/PQDD_0014/NQ31954.pdf.
Full text
24
Jahanbakht, Nafiseh, and University of Lethbridge Faculty of Arts and Science. "Energy of graphs and digraphs." Thesis, Lethbridge, Alta. : University of Lethbridge, Dept. of Mathematics and Computer Science, c2010, 2010. http://hdl.handle.net/10133/2489.
Full textAbstract:
The energy of a graph is the sum of the absolute values of the eigenvalues
of its adjacency matrix. The concept is related to the energy of a class of
molecules in chemistry and was first brought to mathematics by Gutman
in 1978 ([8]). In this thesis, we do a comprehensive study on the energy
of graphs and digraphs.
In Chapter 3, we review some existing upper and lower bounds for
the energy of a graph. We come up with some new results in this chapter.
A graph with n vertices is hyper-energetic if its energy is greater than
2n−2. Some classes of graphs are proved to be hyper-energetic. We find
a new class of hyper-energetic graphs which is introduced and proved to
be hyper-energetic in Section 3.3.
The energy of a digraph is the sum of the absolute values of the real
part of the eigenvalues of its adjacency matrix. In Chapter 4, we study
the energy of digraphs in a way that Pe˜na and Rada in [19] have defined.
Some known upper and lower bounds for the energy of digraphs are reviewed.
In Section 4.5, we bring examples of some classes of digraphs
in which we find their energy.
Keywords. Energy of a graph, hyper-energetic graph, energy of a digraph.vii, 80 leaves ; 29 cm
25
Young, Andrew Christopher. "Extremal Problems for Dense Digraphs." Thesis, University of Birmingham, 2008. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.522060.
Full text
26
Gleiss, Petra M., Josef Leydold, and Peter F. Stadler. "Circuit Bases of Strongly Connected Digraphs." Department of Statistics and Mathematics, Abt. f. Angewandte Statistik u. Datenverarbeitung, WU Vienna University of Economics and Business, 2001. http://epub.wu.ac.at/178/1/document.pdf.
Full textAbstract:
The cycle space of a strongly connected graph has a basis consisting of directed circuits. The concept of relevant circuits is introduced as a generalization of the relevant cycles in undirected graphs. A polynomial time algorithm for the computation of a minimum weight directed circuit basis is outlined. (author's abstract)Series: Preprint Series / Department of Applied Statistics and Data Processing
27
Bai, Yandong. "Arc colorings and cycles in digraphs." Thesis, Paris 11, 2014. http://www.theses.fr/2014PA112356/document.
Full textAbstract:
Cette thèse étudie la coloration d'arcs et de cycles dans les graphes orientés. Elle se concentre sur les sujets suivants : la coloration propre d'arcs avec des sommet-distingué dans les graphes orientés, les cycles courts dans les graphes orientés avec des sous-graphes interdits, les cycles sommet-disjoints dans dans les tournois bipartis, les cycle-facteurs dans les tournois bipartis régulier et les arcs universels dans les tournois. La thèse est basée sur cinq articles originaux publiés ou présentés dans des journaux. Les principaux résultats sont les suivants. Nous introduisons la coloration propre d'arcs avec des sommet-distingué dans les graphes orientés. Nous avons proposé une conjecture sur le nombre arc-chromatique sommet-distingué et nous avons aussi donné quelque résultats partiels. Nous avons étendu un résultat de Razborov en prouvant que la conjecture de Caccetta-Häggkvist est vraie pour certains graphes orientés avec des sous-graphes interdits. Nous avons montré que chaque tournoi biparti avec degré sortant minimum au moins qr-1 contient r cycles de sommets-disjoints de toutes longueurs possibles. Le cas spécial q=2 confirme le cas du tournoi biparti de la conjecture de Bermond-Thomassen. Nous avons montré que chaque tournoi biparti k-régulier avec k>2 que l'on notera B a deux cycles complémentaires de longueurs 6 et |V(B)-6|, à moins que B soit isomorphe à un graphe spécifique, étayant ainsi une conjecture sur des 2-cycles-facteurs dans les tournois bipartis. En outre, nous montrons que tous les tournois bipartis réguliers ont un k-cycle-facteur. Nous donnons une condition nécessaire et suffisante pour l'existence d'un arc universel dans un tournoi et nous caractérisons tous les tournois où chaque arc est universelIn this thesis, we study arc colorings and cycles in digraphs. The following topics are considered: vertex-distinguishing proper arc colorings in digraphs, short cycles in digraphs with forbidden subgraphs , disjoint cycles in bipartite tournaments, cycle factors in regualr bipartite tournaments and universal arcs in tournaments. The main results are contained in five original articles published or submitted to an international journal. We introduce vertex-distinguishing proper arc colorings of digraphs. A conjecture on the vertex-distinguishing arc-chromatic number is given and some partial results are obtained. We extend a result of Razborov by proving that the Caccetta-Häggkvist conjecture is true for digraphs with certain induced forbidden subgraphs or with certain forbidden subgraphs. We show that every bipartite tournament with minimum outdegree at least qr-1 has r vertex disjoint cycles of any given possible lengths. The special case q=2 of the result verifies the bipartite tournament case of the Bermond-Thomassen conjecture. As a partial support of a conjecture on 2-cycle-factors in bipartite tournaments, we prove that every k-regular bipartite tournament B with k>2 has two complementary cycles of lengths 6 and |V(B)|-6, unless B is isomorphic to a special digraph. Besides, we show that every k-connected regular bipartite tournament has a k-cycle-factor. We also give a sufficient and necessary condition for the existence of a universal arc in a tournament and characterize all the tournaments in which every arc is universal
28
Krahn, Gary William. "Double Eulerian cycles on de Bruijn digraphs." Thesis, Monterey, Calif. : Springfield, Va. : Naval Postgraduate School ; Available from National Technical Information Service, 1994. http://handle.dtic.mil/100.2/ADA283334.
Full textAbstract:
Dissertation (Ph.D. in Applied Mathematics) Naval Postgraduate School, June 1994.Dissertation supervisor(s): Harold Fredricksen. "June 1994" Includes bibliographical references. Also available online.
29
Bessy, Stéphane. "Stabilité et décomposition en circuits d'un digraphe." Lyon 1, 2003. http://www.theses.fr/2003LYO10264.
Full textAbstract:
En 1963, T. Gallai conjectura que les sommets de tout digraphe fortement connexe D peuvent être couverts par au plus alpha(D) circuits, où alpha(D) désigne la stabilité de D. Cette thèse présente une preuve de cette conjecture obtenue conjointement avec S. Thomassé et pour laquelle de nouvelles structures combinatoires sont introduites: les ordres cycliques pour digraphes fortement connexes. Un second résultat est présenté: pour un digraphe fortement connexe D, il existe au plus 2. Alpha(D)-1 circuits couvrant le digraphe D et dont l'union est fortement connexe et possède au plus |D|+2. Alpha(D)-2 arcs. De ce résultat dérive un algorithme d'approximation polynomial pour trouver le sous digraphe couvrant fortement connexe de D ayant un nombre minimal d'arcs. L'aspect algorithmique des décompositions est traité. De plus, deux conjectures sont étudiées sur le rôle que la connectivité du digraphe D pourrait jouer dans l'existence de différentes décompositions en chemins ou circuits.
30
Toman, Katherine. "Cancellation Properties of Direct Products of Digraphs." VCU Scholars Compass, 2009. http://scholarscompass.vcu.edu/etd/1776.
Full textAbstract:
This paper discusses the direct product cancellation of digraphs. We define the exact conditions on G such that GxK=HxK implies G=H. We focus first on simple equations such as GxK_2=HxK_2 where K_2 denotes a single arc and then extend this to the more general situation, GxK = HxK. Our results are achieved by using a “factorial” operation on graphs, which is in some sense analogous to the factorial of an integer.
31
Mihalisin, James Edward. "Polytopal digraphs and non-polytopal facet graphs /." Thesis, Connect to this title online; UW restricted, 2001. http://hdl.handle.net/1773/5760.
Full text
32
Norge, Morgan. "Kings in the Direct Product of Digraphs." VCU Scholars Compass, 2019. https://scholarscompass.vcu.edu/etd/6088.
Full textAbstract:
A k-king in a digraph D is a vertex that can reach every other vertex in D by a directed path of length at most k. A king is a vertex that is a k-king for some k. We will look at kings in the direct product of digraphs and characterize a relationship between kings in the product and kings in the factors. This is a continuation of a project in which a similar characterization is found for the cartesian product of digraphs, the strong product of digraphs, and the lexicographic product of digraphs.
33
Amato, Daniela A. "Descendants in infinite primitive highly arc transitive digraphs." Thesis, University of Oxford, 2006. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.437384.
Full text
34
Megaides, Rodrigo. "Spectral and wave function statistics in quantum digraphs." Thesis, Brunel University, 2012. http://bura.brunel.ac.uk/handle/2438/7252.
Full textAbstract:
Spectral and wave function statistics of the quantum directed graph, QdG, are studied. The crucial feature of this model is that the direction of a bond (arc) corresponds to the direction of the waves propagating along it. We pay special attention to the full Neumann digraph, FNdG, which consists of pairs of antiparallel arcs between every node, and differs from the full Neumann graph, FNG, in that the two arcs have two incommensurate lengths. The spectral statistics of the FNG (with incommensurate bond lengths) is believed to be universal, i.e. to agree with that of the random matrix theory, RMT, in the limit of large graph size. However, the standard perturbative treatment of the field theoretical representation of the 2-point correlation function [1, 2] for a FNG, does not account for this behaviour. The nearest-neighbor spacing distribution of the closely related FNdG is studied numerically. An original, efficient algorithm for the generation of the spectrum of large graphs allows for the observation that the distribution approaches indeed universality at increasing graph size (although the convergence cannot be ascertained), in particular "level repulsion" is confirmed. The numerical technique employs a new secular equation which generalizes the analogous object known for undirected graphs [3, 4], and is based on an adaptation to digraphs of the idea of wave function continuity. In view of the contradiction between the field theory [2] and the strong indications of universality, a non-perturbative approach to analysing the universal limit is presented. The substitution of the FNG by the FNdG results in a field theory with fewer degrees of freedom. Despite this simplification, the attempt is inconclusive. Possible applications of this approach are suggested. Regarding the wave function statistics, a field theoretical representation for the spectral average of the wave intensity on an fixed arc is derived and studied in the universal limit. The procedure originates from the study of wave function statistics on disordered metallic grains [5] and is used in conjunction with the field theory approach pioneered in [2].
35
He, Weihua. "Cycles in graphs and arc colorings in digraphs." Thesis, Paris 11, 2014. http://www.theses.fr/2014PA112352.
Full textAbstract:
Dans cette thèse nous étudions quatre problèmes de théorie des graphes. En particulier,Nous étudions le problème du cycle hamiltonien dans les line graphes, et aussi nous prouvons l’existence de cycles hamiltoniens dans certains sous graphes couvrants d’un line graphe. Notre résultat principal est: Si L(G) est hamiltonien, alors SL(G) est hamiltonien. Grâce à ce résultat nous proposons une conjecture équivalente à des conjectures célèbres. Et nous obtenons deux résultats sur les cycles hamiltoniens disjoints dans les line graphes.Nous considérons alors la bipancyclicité résistante aux pannes des graphes de Cayley engendrés par transposition d’arbres. Nous prouvons que de tels graphes de Cayley excepté le “star graph” ont une bipancyclicité (n − 3)-arête résistante aux pannes.Ensuite nous introduisons la coloration des arcs d’un digraphe sommet distinguant. Nous étudions la relation entre cette notion et la coloration d’arêtes sommet distinguant dans les graphes non orientés. Nous obtenons quelques résultats sur le nombre arc chromatique des graphes orientés (semi-)sommet-distinguant et proposons une conjecture sur ce paramètre. Pour vérifier cette conjecture nous étudions la coloration des arcs d’un digraphe sommet distinguant des graphes orientés réguliers.Finalement nous introduisons la coloration acyclique des arcs d’un graphe orienté. Nous calculons le nombre chromatique acyclique des arcs de quelques familles de graphes orientés et proposons une conjecture sur ce paramètre. Nous considérons les graphes orientés de grande maille et utilisons le Lemme Local de Lovász; d’autre part nous considérons les graphes orientés réguliers aléatoires. Nous prouvons que ces deux classes de graphes vérifient la conjectureIn this thesis, we study four problems in graph theory, the Hamiltonian cycle problem in line graphs, the edge-fault-tolerant bipancyclicity of Cayley graphs generated by transposition trees, the vertex-distinguishing arc colorings in digraph- s and the acyclic arc coloring in digraphs. The first two problems are the classic problem on the cycles in graphs. And the other two arc coloring problems are related to the modern graph theory, in which we use some probabilistic methods. In particular,We first study the Hamiltonian cycle problem in line graphs and find the Hamiltonian cycles in some spanning subgraphs of line graphs SL(G). We prove that: if L(G) is Hamiltonian, then SL(G) is Hamiltonian. Due to this, we propose a conjecture, which is equivalent to some well-known conjectures. And we get two results about the edge-disjoint Hamiltonian cycles in line graphs.Then, we consider the edge-fault-tolerant bipancyclicity of Cayley graphs generated by transposition trees. And we prove that the Cayley graph generated by transposition tree is (n − 3)-edge-fault-tolerant bipancyclic if it is not a star graph.Later, we introduce the vertex-distinguishing arc coloring in digraphs. We study the relationship between the vertex-distinguishing edge coloring in undirected graphs and the vertex-distinguishing arc coloring in digraphs. And we get some results on the (semi-) vertex-distinguishing arc chromatic number for digraphs and also propose a conjecture about it. To verify the conjecture we study the vertex-distinguishing arc coloring for regular digraphs.Finally, we introduce the acyclic arc coloring in digraphs. We calculate the acyclic arc chromatic number for some digraph families and propose a conjecture on the acyclic arc chromatic number. Then we consider the digraphs with high girth by using the Lovász Local Lemma and we also consider the random regular digraphs. And the results of the digraphs with high girth and the random regular digraphs verify the conjecture
36
Shim, Sangho. "Large scale group network optimization." Diss., Atlanta, Ga. : Georgia Institute of Technology, 2009. http://hdl.handle.net/1853/31737.
Full textAbstract:
Thesis (Ph.D)--Industrial and Systems Engineering, Georgia Institute of Technology, 2010.Committee Chair: Ellis L. Johnson; Committee Member: Brady Hunsaker; Committee Member: George Nemhauser; Committee Member: Jozef Siran; Committee Member: Shabbir Ahmed; Committee Member: William Cook. Part of the SMARTech Electronic Thesis and Dissertation Collection.
37
Severini, Simone. "Unitary digraphs : on the combinatorial properties of unitary matrices." Thesis, University of Bristol, 2004. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.409520.
Full text
38
Mohan, Prahu. "Product of digraphs, (super) edge-magic valences and related problems." Doctoral thesis, Universitat Politècnica de Catalunya, 2019. http://hdl.handle.net/10803/667257.
Full textAbstract:
Discrete Mathematics, and in particular Graph Theory, has gained a lot of popularity during the last 7 decades. Among the many branches in Graph Theory, graph labelings has experimented a fast development, in particular during the last decade. One of the very important type of labelings are super edge-magic labelings introduced in 1998 by Enomoto et al. as a particular case of edge-magic labelings, introduced in 1970 by Kotzig and Rosa. An edge-magic labeling is a bijective mapping from the set of vertices and edges to [1, |V(G)|+|E(G)|], such that the sum of the labels of each edge and the incident vertices to it is constant. The constant is called the valence of the labeling. The edge-magic labeling is called super edge-magic if the smallest labels are assigned to the vertices.
In this thesis, we consider three problems related to (super) edge-magic labelings and (di)graph products in which we use a family of super edge-magic digraphs as a second factor of the product. The digraph product we use, the h-product, was introduced by Figueroa-Centeno et al. in 2008. It is a generalization of the Kronecker product of digraphs.
In Chapter 2, we study the super edge-magicness of graphs of equal order and size either by providing super edge-magic labelings of some elements in the family or proving that these labelings do not exist. The negative results are specially interesting since these kind of results are not common in the literature. Furthermore, the few results found in this direction usually meet one of the following reasons: too many vertices compared with the number of edges; too many edges compared with the number of vertices; or parity conditions. In our case, all previous reasons fail.
In Chapter 3, we enlarge the family of perfect (super) edge-magic crowns. A crown is obtained from a cycle by adding the same number of pendant edges to each vertex of the cycle. Intuitively speaking, a (super) edge-magic graphs is perfect (super) edge-magic if all possible theoretical valences occur. The main result of the chapter is that the crowns defined by a cycle of length pq, where p and q are different odd primes, are perfect (super) edge-magic. We also provided lower bounds for the number of edge-magic valences of crowns.
For graphs of equal order and size, the odd and the even labelling construction allows to obtain two edge-magic labelings from a particular super edge-magic labeling. The name refers to the parity of the vertex labels. In Chapter 4, we begin by providing some properties of odd and even labelling construction related to the (super) edge-magic labeling and also with respect to the digraph product. We also get a new application of the h-product by interchanging the role of the factors. This allows us to consider the classical conjecture of Godbold and Slater with respect to valences of cycles with a different point of view than the ones existing.
Finally, we devote Chapter 5 to study the problem of edge-magic valences of crowns, in which even cycles appear, and to establish a relationship between super edge-magic graphs and graph decompositions. Some lower bounds on the number of (super) edge-magic valences are also established.La Matemàtica Discreta, i en particular la Teoria de Grafs, han guanyat molta popularitat durant les últimes set dècades. Entre les moltes branques de la Teoria de Grafs, els etiquetatges de grafs han experimentat un ràpid desenvolupament, especialment durant l'última dècada. Un dels tipus d'etiquetatges més importants són els etiquetatges super branca-màgics introduïts el 1998 per Enomoto et al. com un cas particular d'etiquetatges branca-màgics, introduïts el 1970 per Kotzig i Rosa. Un etiquetatge branca-màgic és una aplicació bijectiva del conjunt de vèrtexs i branques a [1, |V(G)|+|E(G)|], de manera que la suma de les etiquetes de cada branca i els vèrtexs incidents a ella és constant. La constant s'anomena valència de l'etiquetatge. L'etiquetatge branca-màgic s'anomena super branca-màgic si les etiquetes més petites s'assignen als vèrtexs. En aquesta tesi, considerem tres problemes relacionats amb etiquetatges (super) branca-màgic i productes de digrafs, en els que intervé una família de grafs super branca-màgic com a segon factor del producte. El producte de digrafs que usem, el producte h, va ser introduït per Figueroa-Centeno et al. el 2008. És una generalització del producte de Kronecker de digraphs. En el Capítol 2, estudiem el caràcter super branca-màgic de grafs d’ordre igual a mida, ja sigui proporcionant etiquetatges super branca-màgics d'alguns elements de la família o demostrant que aquests tipus d’etiquetatges no existeixen. Els resultats negatius són especialment interessants ja que aquest tipus de resultats no són comuns en la literatura. A més, els pocs resultats trobats en aquesta direcció solen encabir-se en una de les raons següents: massa vèrtexs en comparació amb el nombre de branques; massa branques en comparació amb el nombre de vèrtexs; o condicions de paritat. En el nostre cas, totes les raons anteriors fracassen. En el Capítol 3, ampliem la família de corones (super) branca-màgiques perfectes. Una corona és el graf que s’obté a partir d’un afegint el mateix nombre de branques a cada vèrtex del cicle. Intuïtivament parlant, un graf (super) branca màgic és (super) branca màgic si es donen totes les possibles valències teòriques. El resultat principal del capítol és que les corones definides per un cicle de longitud pq, on p i q són primers senars diferents, són (super) branca màgics perfectes. També proporcionem cotes inferiors per a la quantitat de valències màgiques de corones. Per a grafs d'igual ordre i mida, la construcció de l'etiquetatge senar i parell permet obtenir dos etiquetatges branca-màgics a partir d'un etiquetatge super branca-màgic. El nom fa referència a la paritat de les etiquetes de vèrtex. Al capítol 4, comencem proporcionant algunes propietats de la construcció de l'etiquetatge senar i parell relacionades amb l'etiquetatge (super) branca-màgic del que proven i també al producte h de dígrafs. També obtenim una nova aplicació del producte h intercanviant el paper dels factors. Això ens permet considerar la conjectura de Godbold i Slater respecte a les valències dels cicles des d’un punt de vista diferent a les existents. Finalment, dediquem el Capítol 5 a estudiar el problema de les valències branca-màgiques de les corones, en les que apareixen cicles parells, i a establir una relació entre els grafs super branca-màgic i les descomposicions de grafs. També s'estableixen alguns cotes inferiors del nombre de valències (super) branca-màgiques.
39
Thiebaut, Jocelyn. "Algorithmic and structural results on directed cycles in dense digraphs." Thesis, Montpellier, 2019. http://www.theses.fr/2019MONTS059.
Full textAbstract:
Dans cette thèse, nous nous intéressons à quelques problèmes algorithmiques et structurels du packing de cycles (orientés) dans les graphes orientés denses. Ces problèmes sont notamment motivés par la compréhension de la structure de tels graphes, mais également car de nombreux problèmes algorithmiques sont faciles (résolubles en temps polynomial) sur des graphes orientés acycliques alors qu'il sont NP-difficiles sur les graphes orientés en général.Plus spécifiquement, nous étudions dans un premier temps le packing de cycles et le packing de triangles dans les tournois. Ces problèmes sont les duaux (d'un point de vue programmation linéaire) des problèmes de feedback arc/vertex set qui ont reçu beaucoup d'attention dans la littérature. Nous montrons entre autres qu'il n'y a pas d'algorithme polynomial pour trouver une collection maximale de cycles (respectivement triangles) sommet ou arc-disjointe dans les tournois, sauf si P = NP. Nous nous intéressons également aux algorithmes d'approximations et de complexité paramétrée de ces différents problèmes.Nous étudions ensuite plus en détail ces problèmes dans le cas spécifique où le tournoi admet un feedback arc set qui est un couplage, appelé sparse. Étonnamment, le problème reste difficile dans le cas des triangles sommet-disjoints, mais devient polynomial pour les triangles et cycles arc-disjoints. Ainsi, nous explorons l'approximation et la complexité paramétrée du cas sommet-disjoints dans les tournois sparses.Enfin, nous répondons positivement à une conjecture structurelle sur les bipartis complets k-réguliers par Manoussakis, Song et Zhang datant de 1994. En effet, nous démontrons que tous les digraphes de cette classe non isomorphes à un digraphe particulier possèdent pour tout p pair avec 4 leq p leq |V(D)| - 4 un cycle C de taille p tel que D V(C) est hamiltonienIn this thesis, we are interested in some algorithmic and structural problems of (oriented) cycle packing in dense digraphs. These problems are mainly motivated by understanding the structure of such graphs, but also because many algorithmic problems are easy (i.e. resolvable in polynomial time) on acyclic digraphs while they are NP-difficult in the general case.More specifically, we first study the packing of cycles and the packing of triangles in tournaments. These problems are the two dual problems (from a linear programming point of view) of feedback arc/vertex set that have received a lot of attention in literature. Among other things, we show that there is no polynomial algorithm to find a maximum collection of cycles (respectively triangles) vertex or arc-disjoint in tournaments, unless P = NP. We are also interested in algorithms of approximations and parameterized complexity of these different problems.Then, we study these problems in the specific case where the tournament admits a feedback arc set which is a matching. Such tournaments are said to be sparse. Surprisingly, the problem remains difficult in the case of vertex-disjoint triangles, but the packing of triangles and the packing of arc-disjoint cycles become polynomial. Thus, we explore the approximation and parameterized complexity of the vertex-disjoint case in sparse tournaments.Finally, we answer positively to a structural conjecture on k-regular bipartite tournaments by Manoussakis, Song and Zhang from 1994. Indeed, we show that all digraphs of this non-isomorphic class to a particular digraph have for every p even with 4 leq p leq |V(D)| - 4 a C cycle of size p such that D V(C) is Hamiltonian
40
Thorup, Mikkel. "Topics in computation." Thesis, University of Oxford, 1993. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.357621.
Full text
41
Bell, Edward J. L. "Word-graph theory : on the structural characterisation of word-respectable digraphs." Thesis, Lancaster University, 2012. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.660112.
Full textAbstract:
A word- graph Gw is a simple digraph associated with a finite word w such that the vertex set of Gw is the alphabet of wand the edge-set of Gw is determined by ~on-identical adjacent letter pairs in w. A family of word-graphs can be thought of as a formal language. The novel theory of word- graphs proposed in this thesis is of interest for two reasons: . first, word-graphs have close links with a range of word-based stochastic processes such as language, music, DNA and protein sequences; second, the cross-applicability of proof techniques in graph theory and combinatorics on words has lead to a recent explosion of interest in the literature in the relationship between words and graphs. The focus of this thesis is on developing a theory of word-graphs by formalising how structural word-theoretic properties manifest in digraphs and how structural graphtheoretic properties manifest in words. The analysis starts by looking at the relationship between word and digraph forms and continues by investigating whether or not a given digraph can be represented by a word or a set of words. The main findings include: representational word and digraph structure is intrinsically linked; every finite digraph can be represented by a finite set of words; and the number of words required to represent a digraph is determined by that digraph's edge-contracted subgraphs. Besides the theory's applications in stochastic process analysis, word- graph theory has the potential to be used as a general methodology for digraph and word theoretic analysis.
42
Coulson, Matthew John. "Threshold phenomena involving the connected components of random graphs and digraphs." Doctoral thesis, Universitat Politècnica de Catalunya, 2021. http://hdl.handle.net/10803/673350.
Full textAbstract:
We consider some models of random graphs and directed graphs and investigate their behavior near thresholds for the appearance of certain types of connected components. Firstly, we look at the critical window for the appearance of a giant strongly connected component in binomial random digraphs. We provide bounds on the probability that the largest strongly connected component is very large or very small. Next, we study the configuration model for graphs and show new upper bounds on the size of the largest connected component in the subcritical and barely subcritical regimes. We also show that these bounds are tight in some instances. Finally we look at the configuration model for random digraphs. We investigate the barely sub-critical region and show that this model behaves similarly to the binomial random digraph whose barely sub- and super-critical behaviour was studied by Luczak and Seierstad. Moreover, we show the existence of a threshold for the existence of a giant weak component, as predicted by Kryven.En aquesta tesi considerem diversos models de grafs i graf dirigits aleatoris, i investiguem el seu comportament a prop dels llindars per l'aparició de certs tipus de components connexes. En primer lloc, estudiem la finestra crítica per a l'aparició d'una component fortament connexa en dígrafs aleatoris binomials (o d'Erdos-Rényi). En particular, provem diversos resultats sobre la probabilitat límit que la component fortament connexa sigui sigui molt gran o molt petita. A continuació, estudiem el model de configuració per a grafs no dirigits i mostrem noves cotes superiors per la mida de la component connexa més gran en els règims sub-crítics i quasi-subcrítics. També demostrem que, en general, aquestes cotes no poden ser millorades. Finalment, estudiem el model de configuració per a dígrafs aleatoris. Ens centrem en la regió quasi-subcrítica i demostrem que aquest model es comporta de manera similar al model binomial, el comportament del qual va ser estudiat per Luczak i Seierstad en les regions quasi-subcrítica i quasi-supercrítica. A més a més, demostrem l'existència d'una funció llindar per a l'existència d'una component feble gegant, tal com va predir Kryven.
Matemàtica aplicada
43
Grivelet, Stéphane. "La digraphie : changements et coexistence d'écritures." Montpellier 3, 1999. http://www.theses.fr/1999MON30048.
Full text
44
Grivelet, Stéphane Dumont Pierre. "La digraphie : changements et coexistence d'ecritures /." Lille : Atelier national de reproduction des thèses, 2007. http://catalogue.bnf.fr/ark:/12148/cb411548182.
Full text
45
Jordan, T. R. "In search of the digram." Thesis, University of Reading, 1985. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.356132.
Full text
46
Lichiardopol, Nicolas. "Echange total, diffusion et quelques résultats sur les itérés de line-digraphs." Phd thesis, Université de Nice Sophia-Antipolis, 2003. http://tel.archives-ouvertes.fr/tel-00214261.
Full textAbstract:
Nous nous intéressons à des protocoles de communications globales portant sur les graphes connexes. Dans une première partie, nous considérons le cas de l'échange total. Le Temps Minimum d'Echange Total (T.M.E.T.) est le nombre minimum d'étapes nécessaires pour que tous les sommets reçoivent tous les messages. Nous établissons des nouvelles bornes (inférieures et supérieures) sur le T.M.E.T. Nous déterminons le T.M.E.T des arbres et plus généralement des graphes de degré minimum un. Nous démontrons une conjecture de Bermond, Kodate, Marlin et Perennes sur les points fixes d'une rotation complète de certaines grilles toriques, ce qui permet de déduire l'optimalité de leur T.M.E.T. Nous montrons aussi que le T.M.E.T d'un graphe orienté de de Bruijn est optimal. Dans une seconde partie, nous considérons la problème classique de la diffusion. Nous déterminons une nouvelle borne supérieure sur le temps de diffusion d'in graphe non orienté en fonction de sa connectivité. Nous caractérisons certains graphes dont le numéro de couplage est égal au degré minimum et déterminons leur temps de diffusion. Nous donnons des résultats nouveaux sur la diffusion dans les graphes de de Bruijn. Dans la dernière partie, nous donnons des résultats originaux sur le nombre de stabilité d'un graphe de de Bruijn et plus généralement des graphes représentatifs des arcs. Nous montrons ensuite que la taille minimum d'un graphe de de Bruijn UB est ce qui valide une première conjecture de Bond. Enfin, nous prouvons que le rayon d'un graphe de Kautz est D, ce qui valide une seconde conjecture de Bond. ( d ,D ) d 1, - 2 UK( ,D )
47
Giscard, Pierre-Louis. "A graph theoretic approach to matrix functions and quantum dynamics." Thesis, University of Oxford, 2014. http://ora.ox.ac.uk/objects/uuid:ceef15b0-eed2-4615-a9f2-f9efbef470c9.
Full textAbstract:
Many problems in applied mathematics and physics are formulated most naturally in terms of matrices, and can be solved by computing functions of these matrices. For example, in quantum mechanics, the coherent dynamics of physical systems is described by the matrix exponential of their Hamiltonian. In state of the art experiments, one can now observe such unitary evolution of many-body systems, which is of fundamental interest in the study of many-body quantum phenomena. On the other hand the theoretical simulation of such non-equilibrium many-body dynamics is very challenging. In this thesis, we develop a symbolic approach to matrix functions and quantum dynamics based on a novel algebraic structure we identify for sets of walks on graphs. We begin by establishing the graph theoretic equivalent to the fundamental theorem of arithmetic: all the walks on any finite digraph uniquely factorise into products of prime elements. These are the simple paths and simple cycles, walks forbidden from visiting any vertex more than once. We give an algorithm that efficiently factorises individual walks and obtain a recursive formula to factorise sets of walks. This yields a universal continued fraction representation for the formal series of all walks on digraphs. It only involves simple paths and simple cycles and is thus called a path-sum. In the second part, we recast matrix functions into path-sums. We present explicit results for a matrix raised to a complex power, the matrix exponential, matrix inverse, and matrix logarithm. We introduce generalised matrix powers which extend desirable properties of the Drazin inverse to all powers of a matrix. In the third part, we derive an intermediary form of path-sum, called walk-sum, relying solely on physical considerations. Walk-sum describes the dynamics of a quantum system as resulting from the coherent superposition of its histories, a discrete analogue to the Feynman path-integrals. Using walk-sum we simulate the dynamics of quantum random walks and of Rydberg-excited Mott insulators. Using path-sum, we demonstrate many-body Anderson localisation in an interacting disordered spin system. We give two observable signatures of this phenomenon: localisation of the system magnetisation and of the linear magnetic response function. Lastly we return to the study of sets of walks. We show that one can construct as many representations of series of walks as there are ways to define a walk product such that the factorisation of a walk always exist and is unique. Illustrating this result we briefly present three further methods to evaluate functions of matrices. Regardless of the method used, we show that graphs are uniquely characterised, up to an isomorphism, by the prime walks they sustain.
48
Dalfó, Simó Cristina. "Estudi i disseny de grans xarxes d'interconnexió: modularitat i comunicació." Doctoral thesis, Universitat Politècnica de Catalunya, 2007. http://hdl.handle.net/10803/5849.
Full textAbstract:
Normalment les grans xarxes d'interconnexió o de comunicacions estan dissenyades utilitzant tècniques de la teoria de grafs. Aquest treball presenta algunes contribucions a aquest tema. Concretament, presentem dues noves operacions: el "producte Jeràrquic" de grafs i el "producte Manhattan" de digrafs. El primer és una generalització del producte cartesià de grafs i ens permet construir algunes famílies amb un alt grau de jerarquia, com l'arbre binomial, que és una estructura de dades molt utilitzada en algorísmica. El segon dóna lloc a les conegudes Manhattan Street Networks, les quals han estat extensament estudiades i utilitzades per modelar algunes classes de xarxes òptiques. En el nostre treball, definim formalment i analitzem el cas multidimensional d'aquestes xarxes. Estudiem algunes propietats dels grafs o digrafs obtinguts mitjançant les dues operacions esmentades, especialment: els paràmetres estructurals (les propietats de l'operació, els subdigrafs induïts, la distribució de graus i l'estructura de digraf línia), els paràmetres mètrics (el diàmetre, el radi i la distància mitjana), la simetria (els grups d'automorfismes i els digrafs de Cayley), l'estructura de cicles (els cicles hamiltonians i la descomposició en cicles hamiltonians arc-disjunts) i les propietats espectrals (els valors i vectors propis). En el darrer cas, hem trobat, per exemple, que la família dels arbres binomials tenen tots els seus valors propis diferents, "omplint" tota la recta real. A més a més, mostrem la relació del seu conjunt de vectors propis amb els polinomis de Txebishev de segona espècie. També hem estudiat alguns protocols de comunicació, com els enrutaments locals i els algorismes de difusió. Finalment, presentem alguns models deterministes (com les xarxes Sierpinski i d'altres), els quals presenten algunes propietats pròpies de les xarxes complexes reals (com, per exemple, Internet).Large interconnection or communication networks are usually designed and studied by using techniques from graph theory. This work presents some contributions to this subject. With this aim, two new operations are proposed: the "hierarchical product" of graphs and the "Manhattan product" of digraphs. The former can be seen as a generalization of the Cartesian product of graphs and allows us to construct some interesting families with a high degree of hierarchy, such as the well-know binomial tree, which is a data structure very used in the context of computer science. The latter yields, in particular, the known topologies of Manhattan Street Networks, which has been widely studied and used for modelling some classes of light-wave networks. In this thesis, a multidimensional approach is analyzed. Several properties of the graphs or digraphs obtained by both operations are dealt with, but special attention is paid to the study of their structural parameters (operation properties, induced subdigraphs, degree distribution and line digraph structure), metric parameters (diameter, radius and mean distance), symmetry (automorphism groups and Cayley digraphs), cycle structure (Hamilton cycles and arc-disjoint Hamiltonian decomposition) and spectral properties (eigenvalues and eigenvectors). For instance, with respect to the last issue, it is shown that some families of hypertrees have spectra with all different eigenvalues "filling up" all the real line. Moreover, we show the relationship between its eigenvector set and Chebyshev polynomials of the second kind. Also some protocols of communication, such as local routing and broadcasting algorithms, are addressed. Finally, some deterministic models (Sierpinsky networks and others) having similar properties as some real complex networks, such as the Internet, are presented.
49
Li, Ruijuan [Verfasser]. "k-ordered graphs & out-arc pancyclicity on digraphs / vorgelegt von Ruijuan Li." Aachen : Mainz, 2009. http://d-nb.info/1000114058/34.
Full text
50
Maharaj, Hiren. "Graph and digraph embedding problems." Thesis, 1996. http://hdl.handle.net/10413/5928.
Full textAbstract:
This thesis is a study of the symmetry of graphs and digraphs by considering certain
homogeneous embedding requirements.
Chapter 1 is an introduction to the chapters that follow. In Chapter 2 we present
a brief survey of the main results and some new results in framing number theory.
In Chapter 3, the notions of frames and framing numbers is adapted to digraphs. A
digraph D is homogeneously embedded in a digraph H if for each vertex x of D and
each vertex y of H, there exists an embedding of D in H as an induced subdigraph
with x at y. A digraph F of minimum order in which D can be homogeneously
embedded is called a frame of D and the order of F is called the framing number of
D. We show that that every digraph has at least one frame and, consequently, that
the framing number of a digraph is a well defined concept. Several results involving
the framing number of graphs and digraphs then follow. Analogous problems to those
considered for graphs are considered for digraphs.
In Chapter 4, the notions of edge frames and edge framing numbers are studied.
A nonempty graph G is said to be edge homogeneously embedded in a graph H if for
each edge e of G and each edge f of H, there is an edge isomorphism between G and
a vertex induced subgraph of H which sends e to f. A graph F of minimum size
in which G can be edge homogeneously embedded is called an edge frame of G and
the size of F is called the edge framing number efr(G) of G. We also say that G is
edge framed by F. Several results involving edge frames and edge framing numbers
of graphs are presented.
For graphs G1 and G2 , the framing number fr(G1 , G2 ) (edge framing number
ef r(GI, G2 )) of G1 and G2 is defined as the minimum order (size, respectively) of a
graph F such that Gj (i = 1,2) can be homogeneously embedded in F. In Chapter 5
we study edge framing numbers and framing number for pairs of cycles. We also
investigate the framing number of pairs of directed cycles.Thesis (Ph.D.)-University of Natal, Pietermaritzburg, 1996.