To see the other types of publications on this topic, follow the link: Digraphe.
Dissertations / Theses on the topic 'Digraphe'
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 'Digraphe.'
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
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.
2
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.
3
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
4
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.
5
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
6
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.
7
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
8
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
9
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.
10
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
11
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
12
Grivelet, Stéphane. "La digraphie : changements et coexistence d'écritures." Montpellier 3, 1999. http://www.theses.fr/1999MON30048.
Full text
13
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
14
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.
15
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
16
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.
17
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.
18
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.
19
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
20
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
21
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
22
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].
23
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
24
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
25
Li, Ruijuan. "k-ordered graphs & out-arc pancyclicity on digraphs." Aachen Mainz, 2009. http://d-nb.info/994128894/04.
Full text
26
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.
27
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
28
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.
29
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
30
Thorup, Mikkel. "Topics in computation." Thesis, University of Oxford, 1993. http://ethos.bl.uk/OrderDetails.do?uin=uk.bl.ethos.357621.
Full text
31
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.
32
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
33
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.
34
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 )
35
Phan, Phuong Anh. "L'alphabet et le pinceau : digraphie et calligraphie dans le Việt Nam contemporain." Paris, EHESS, 2005. http://www.theses.fr/2005EHES0184.
Full textAbstract:
Au moment de l’ouverture du Việt Nam, il y a une quinzaine d’années, apparaît la calligraphie du quốc ngữ, – l’alphabet vietnamien issu de l’alphabet latin –, au pinceau chinois. L’emprunt par une écriture alphabétique de l’outil de la calligraphie des idéogrammes chinois illustre une situation de digraphie liée au contexte historique de ce pays qui a connu successivement les deux systèmes d’écriture. La description ethnographique et l’analyse des discours et pratiques des calligraphes de l’alphabet, d’une part, et des usages rituels de leurs productions graphiques, de l’autre, mettent en évidence la concurrence de deux écritures, dans ce qui a longtemps constitué le monopole de l’idéogramme. Ce qui permet de saisir et de caractériser la forte empreinte de l’idéogramme chez les usagers de l’alphabet. Chaque système résulte d’une synthèse particulière de l’image et de la parole et l’utilisation de l’un ou de l’autre par la même communauté linguistique obéit à des règles de répartition dont on peut rendre compte, en interrogeant, au passage, la relation admise entre systèmes graphiques et modes de penserSince Việt Nam initiated its open door policies, about fifteen years ago, there has appeared the calligraphy of quốc ngữ, – the Vietnamese Latinized alphabet –, being done with the Chinese brush. The borrowing by an alphabetical writing system of the calligraphy tool of Chinese ideograms illustrates a situation of digraphia related to the historical context of this country, which successively knew the two writing systems. The ethnographic description and the analysis of the discourse and practices of the calligraphers of the alphabet, on the one hand, and of the ritual usages of their graphic productions, on the other hand, highlight the competition of the two scripts, in what constituted the monopoly of the ideogram for a long time. That makes it possible to grasp and to characterize the strong imprint of the ideogram on the users of the alphabet. Each system results from a particular synthesis of image and language and the use of one or other by the same speech community obeying rules of distribution which we can realize, by questioning, as well, the admitted relation between graphic systems and modes of thinking
36
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
37
Cooper, Melody Elaine. "Packings and Coverings of Various Complete Digraphs with the Orientations of a 4-Cycle." Digital Commons @ East Tennessee State University, 2007. https://dc.etsu.edu/etd/2031.
Full textAbstract:
There are four orientations of cycles on four vertices. Necessary and sufficient conditions are given for covering complete directed digraphs Dv, packing and covering complete bipartite digraphs, Dm,n, and packing and covering the complete digraph on v vertices with hole of size w, D(v,w), with three of the orientations of a 4-cycle, including C4, X, and Y.
38
Holcomb, Trae. "Contributions to a General Theory of Codes." Diss., Texas A&M University, 2003. http://hdl.handle.net/1969.1/80.
Full textAbstract:
In 1997, Drs. G. R. Blakley and I. Borosh published two papers whose stated purpose was to present a general formulation of the notion of a code that depends only upon a code's structure and not its functionality. In doing so, they created a further generalization--the idea of a precode. Recently, Drs. Blakley, Borosh, and A. Klappenecker have worked on interpreting the
structures and results in these pioneering papers within the framework of category theory.
The purpose of this dissertation is to further the above work. In particular, we seek to accomplish the following tasks within the ``general theory of codes.'
1. Rewrite the original two papers in terms of the alternate representations of precodes as bipartite digraphs and Boolean matrices.
2. Count various types of bipartite graphs up to isomorphism, and count various classes of codes and precodes up to isomorphism.
3. Identify many of the classical objects and morphisms from category theory within the categories of codes and precodes.
4. Describe the various ways of constructing a code from a precode by ``splitting' the precode. Identify important properties of these
constructions and their interrelationship. Discuss the properties of the constructed codes with regard to the factorization of homomorphisms through them, and discuss their relationship to the code constructed from the precode by ``smashing.'
5. Define a parametrization of a precode and
give constructions of various parametrizations of a given precode, including a ``minimal' parametrization.
6. Use the computer algebra system, Maple, to represent and display a precode and its companion, opposite, smash, split, bald-split, and various parametrizations. Implement the formulae developed for counting bipartite graphs and precodes up to isomorphism.
39
Knapp, Christopher N. "The complexity of greedoid Tutte polynomials." Thesis, Brunel University, 2018. http://bura.brunel.ac.uk/handle/2438/15891.
Full textAbstract:
We consider the computational complexity of evaluating the Tutte polynomial of three particular classes of greedoid, namely rooted graphs, rooted digraphs and binary greedoids. Furthermore we construct polynomial-time algorithms to evaluate the Tutte polynomial of these classes of greedoid when they're of bounded tree-width. We also construct a Möbius function formulation for the characteristic polynomial of a rooted graph and determine the computational complexity of computing the coefficients of the Tutte polynomial of a rooted graph.
40
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.
41
Gollin, Jochen Pascal [Verfasser], and Reinhard [Akademischer Betreuer] Diestel. "Connectivity and tree structure in infinite graphs and digraphs / Jochen Pascal Gollin ; Betreuer: Reinhard Diestel." Hamburg : Staats- und Universitätsbibliothek Hamburg, 2019. http://d-nb.info/1192913124/34.
Full text
42
Lewenczuk, Janice Gail. "Decomposition, Packings and Coverings of Complete Digraphs with a Transitive-Triple and a Pendant Arc." Digital Commons @ East Tennessee State University, 2007. https://dc.etsu.edu/etd/2053.
Full textAbstract:
In the study of design 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 each of the six transitive triples with a pendant arc.
43
Gollin, Jochen Pascal Verfasser], and Reinhard [Akademischer Betreuer] [Diestel. "Connectivity and tree structure in infinite graphs and digraphs / Jochen Pascal Gollin ; Betreuer: Reinhard Diestel." Hamburg : Staats- und Universitätsbibliothek Hamburg, 2019. http://nbn-resolving.de/urn:nbn:de:gbv:18-99171.
Full text
44
Schweser, Thomas [Verfasser], Michael [Akademischer Betreuer] Stiebitz, Maria Gutachter] Axenovich, and Eckhard [Gutachter] [Steffen. "Colorings of graphs, digraphs, and hypergraphs / Thomas Schweser ; Gutachter: Maria Axenovich, Eckhard Steffen ; Betreuer: Michael Stiebitz." Ilmenau : TU Ilmenau, 2020. http://d-nb.info/1222908964/34.
Full text
45
Lochet, William. "Sous-structures dans les graphes dirigés." Thesis, Université Côte d'Azur (ComUE), 2018. http://www.theses.fr/2018AZUR4052/document.
Full textAbstract:
Le but principal de cette thèse est de présenter des conditions suffisantes pour garantir l'existence de subdivisions dans les graphes dirigés. Bien que ce genre de questions soit assez bien maitrisé dans le cas des graphes non orientés, très peu de résultats sont connus sur le sujet des graphes dirigés. La conjecture la plus célèbre du domaine est sans doute celle attribuée à Mader en 1985 qui dit qu'il existe une fonction f tel que tout graphe dirigé de degré sortant minimal supérieur à f(k) contient le tournoi transitif sur k sommets comme subdivision. Cette question est toujours ouverte pour k=5. Cette thèse présente quelques résultats intermédiaires tendant vers cette conjecture. Il y est d'abords question de montrer l'existence de subdivisions de graphes dirigés autre que les tournois, en particulier les arborescences entrantes. Il y a aussi la preuve que les graphes dirigés de grand degré sortant contiennent des immersions de grand tournois transitifs, question qui avait été posée en 2011 par DeVos et al. En regardant un autre paramètre, on montre aussi qu'un grand nombre chromatique permet de forcer des subdivisions de certains cycles orientés, ainsi que d'autre structures, pour des graphes dirigés fortement connexes. Cette thèse présente également la preuve de la conjecture de Erd\H{o}s-Sands-Sauer-Woodrow qui dit que les tournois dont les arcs peuvent être partitionnés en k graphes dirigés transitifs peuvent être dominé par un ensemble de sommet dont la taille dépend uniquement de k. Pour finir, cette thèse présente la preuve de deux résultats, un sur l'orientation des hypergraphes et l'autre sur la coloration AVD,utilisant la technique de compression d'entropieThe main purpose of the thesis was to exhibit sufficient conditions on digraphs to find subdivisions of complex structures. While this type of question is pretty well understood in the case of (undirected) graphs, few things are known for the case of directed graphs (also called digraphs). The most notorious conjecture is probably the one due to Mader in 1985. He asked if there exists a function f such that every digraph with minimum outdegree at least f(k) contains a subdivision of the transitive tournament on k vertices. The conjecture is still wide open as even the existence of f(5) remains open. This thesis presents some weakening of this conjecture. Among other results, we prove that digraphs with large minimum outdegree contain large in-arborescences. We also prove that digraphs with large minimum outdegree contain large transitive tournaments as immersions, which was conjectured by DeVos et al. in 2011. Changing the parameter, we also prove that large chromatic number can force subdivision of cycles and other structures in strongly connected digraphs. This thesis also presents the proof of the Erd\H{o}s-Sands-Sauer-Woodrow conjecture that states that the domination number of tournaments whose arc set can be partitioned into k transitive digraphs only depends on k. The conjecture, asked in 1982, was still open for k=3. Finally this thesis presents proofs for two results, one about orientation of hypergraphs and the other about AVD colouring using the recently developed probabilistic technique of entropy compression
46
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.
47
Afzali, Borujeni Seyed Hadi [Verfasser], and Reinhard [Akademischer Betreuer] Diestel. "Representability of infinite matroids and the structure of linkages in digraphs / Seyed Hadi Afzali Borujeni. Betreuer: Reinhard Diestel." Hamburg : Staats- und Universitätsbibliothek Hamburg, 2014. http://d-nb.info/106048448X/34.
Full text
48
Holtkamp, Andreas [Verfasser]. "Connectivity in graphs and digraphs : maximizing vertex-, edge- and arc-connectivity with an emphasis on local connectivity properties / Andreas Holtkamp." Aachen : Hochschulbibliothek der Rheinisch-Westfälischen Technischen Hochschule Aachen, 2013. http://d-nb.info/1038598796/34.
Full text
49
Corrêa, Débora Cristina. "Inteligência artificial aplicada à análise de gêneros musicais." Universidade de São Paulo, 2012. http://www.teses.usp.br/teses/disponiveis/76/76132/tde-05032013-090334/.
Full textAbstract:
O crescimento constante dos dados musicais na Internet tem encorajado diversos pesquisadores a desenvolver ferramentas adequadas para a análise e a classificação destes dados. O objetivo principal de tais ferramentas é extrair a informação de forma compacta e representativa ao conteúdo dos bancos de dados. Dentro deste contexto, os gêneros musicais apresentam descrições importantes para o desenvolvimento destas ferramentas. Além dos mesmos serem usados frequentemente para organizar coleções musicais e refletirem a interação ente culturas, resumem características (padrões) comuns entre as peças musicais. Em face ao exposto, a principal motivação deste projeto de pesquisa é propor uma maneira original, e de baixo esforço computacional, para representar os gêneros musicais e investigar a contribuição desta representação em aplicações e estudos que estão inseridos no contexto de pesquisas que envolvem a recuperação da informação musical. A representação proposta refere-se aos padrões rítmicos das músicas, uma vez que o ritmo configura um aspecto musical significante na discriminação dos gêneros. Os padrões rítmicos são estabelecidos pela dependência temporal das notas musicais presentes na percussão, de forma que cada música é representada por um vetor de probabilidades condicionais entre pares e trios de notas computadas pelo uso de cadeias de Markov de primeira e segunda ordem. Os padrões rítmicos de diversos gêneros são explorados em aplicações como: classificação, síntese musical, recomendação musical, humor/emoção em música, e análise de aspectos evolutivos. Constatou-se que estes, como estabelecidos neste estudo, são sensíveis à discriminação dos gêneros, evidenciando sequências de notas que são comuns aos mesmos, e sequências que são distintas e características de cada um. Uma segunda motivação deste projeto é o uso de medidas topológicas de redes e dígrafos de músicas para a análise dos dados. Comunidades obtidas nestas redes proporcionaram a definição de uma abordagem não supervisionada, a qual apresentou taxas de desempenho superiores ao agrupamento hierárquico. A determinação das características rítmicas de cada música motivou o desenvolvimento de estratégias para a composição automática e para a geração de listas de reprodução, assim como para a averiguação da relação destes padrões com aspectos emotivos. Por fim, uma análise estatística da evolução do ritmo de diferentes gêneros é desempenhada, na qual verificou-se a presença de mecanismos de inovação e recuperação. Estes mecanismos parecem ser consequência da competição entre fatores que favorecem a inovação de material musical, e fatores que a previnem, como, por exemplo, a obediência às regras de composição que mantém as características fundamentais de cada gênero.Musical databases have increased in number and size continuously, paving the way to large amounts of online music data, including discographies, biographies and lyrics. The constant growth of data on the Internet has attracted musical research for developing tools to analyze and classify music data. The main objective of such tools is to extract reliable information to adequately represent and compact music content in databases. In this context, musical genres are particularly interesting descriptors, since they have being used for years to organize music collections, reflect interaction between cultures and summarize common features (or patterns) between musical pieces. The main motivation of this study is to propose a original and low cost framework to represent musical genres, as well as investigate the contribution of this representation in applications and studies that are placed in the context of music information retrieval researches. The representation of music content is referred to the rhythmic patterns, since rhythm configures a significant aspect in the discrimination of musical genres. The rhythmic patterns are determined by the temporal dependency of the musical notes present in the percussion, so that each song is represented by a vector of conditional probabilities between pairs and triples of notes, computed by the use of first and second order Markov chains. The rhythm patterns from distinct genres are investigated in applications such as: classification, music synthesis, music recommendation, mood/emotion in music, and analysis of evolutionary aspects. The main finding is that the rhythmic patterns as established in this study are sensitive to the genre discrimination, suggesting that there are sequences of notes common to all genres, and sequences that are distinct and characteristics of each one. A second motivation for this study is the use of topological measures of music networks and music digraphs for the data analysis. Communities obtained from these networks contributed to the definition of an unsupervised approach that provided performance rates superior to the hierarchical clustering. The rhythmic patterns also motivated the development of strategies for automatic composition, for the generation of playlists, and the analysis of the relationship between these patterns and emotional aspects. Finally, a statistical analysis of the rhythm evolution is performed, in which the principal finding is the presence of innovation and retrieval mechanisms for all genres. These mechanisms seems to be the result of the competition between factors that promote the innovation, and factors that prevent it, as, for example, the obedience to composition rules that retains the fundamental characteristics of each genre.
50
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