Relevant bibliographies by topics / Digraph

Contents

  1. Journal articles
  2. Dissertations / Theses
  3. Books
  4. Book chapters
  5. Conference papers
  6. Reports

Academic literature on the topic 'Digraph'

Author: Grafiati
Published: 4 June 2021
Last updated: 18 May 2024

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources 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.

Journal articles on the topic "Digraph"

1

Luo, Mei Jin. "The Upper Bound of Primitive Exponent of a Class of Special Nonnegative Matrix Pairs." Advanced Materials Research 1061-1062 (December 2014): 1100–1103. http://dx.doi.org/10.4028/www.scientific.net/amr.1061-1062.1100.

Full text
Abstract:
There is a one-to-one relationship between nonnegative matrix pairs and two-colored digraph. With the knowledge of graph theory, by studying the associated directed digraph of a class of special nonnegative matrix pairs, that is a class of two-colored digraphs whose uncolored digraph have 3n-1 vertices and consists of one (3n-1)-cycle and one n-cycle are considered. The exponent and characteristic of extreme two-colored digraphs are given.
APA, Harvard, Vancouver, ISO, and other styles
2

RUAN, LU, SHITOU HAN, DEYING LI, HUNG Q. NGO, and SCOTT C. H. HUANG. "TRANSMISSION FAULT-TOLERANCE OF ITERATED LINE DIGRAPHS." Journal of Interconnection Networks 05, no. 04 (December 2004): 475–87. http://dx.doi.org/10.1142/s021926590400126x.

Full text
Abstract:
The main result of this paper states that, if every cyclic modification of a d-regular digraph has super line-connectivity d, then the line digraph also has super line-connectivity d. Since many well-known interconnection network topologies, such as the Kautz digraphs, the de Bruijn digraphs, etc., can be constructed by iterating the line digraph construction, our result leads to several known and new connectivity results for these topologies, as shown later in the paper.
APA, Harvard, Vancouver, ISO, and other styles
3

FERRARA, MICHAEL, MICHAEL JACOBSON, and FLORIAN PFENDER. "Degree Conditions for H-Linked Digraphs." Combinatorics, Probability and Computing 22, no. 5 (August 8, 2013): 684–99. http://dx.doi.org/10.1017/s0963548313000278.

Full text
Abstract:
Given a (multi)digraph H, a digraph D is H-linked if every injective function ι:V(H) → V(D) can be extended to an H-subdivision. In this paper, we give sharp degree conditions that ensure a sufficiently large digraph D is H-linked for arbitrary H. The notion of an H-linked digraph extends the classes of m-linked, m-ordered and strongly m-connected digraphs.First, we give sharp minimum semi-degree conditions for H-linkedness, extending results of Kühn and Osthus on m-linked and m-ordered digraphs. It is known that the minimum degree threshold for an undirected graph to be H-linked depends on a partition of the (undirected) graph H into three parts. Here, we show that the corresponding semi-degree threshold for H-linked digraphs depends on a partition of H into as many as nine parts.We also determine sharp Ore–Woodall-type degree-sum conditions ensuring that a digraph D is H-linked for general H. As a corollary, we obtain (previously undetermined) sharp degree-sum conditions for m-linked and m-ordered digraphs.
APA, Harvard, Vancouver, ISO, and other styles
4

Luo, Mei Jin. "The Primitive Exponent of a Class of Special Nonnegative Matrix Pairs." Advanced Materials Research 915-916 (April 2014): 1296–99. http://dx.doi.org/10.4028/www.scientific.net/amr.915-916.1296.

Full text
Abstract:
There is a one-to-one relationship between nonnegative matrix pairs and two-colored digraph, so the problem of matrices can be changed into that of graphics to be solved. With the knowledge of graph theory, by studying the associated directed digraph of a class of special nonnegative matrix pairs, that is a class of two-colored digraphs whose uncolored digraph have vertices and consists of one-cycle and one-cycle are considered. The exponent and characteristic of extreme two-colored digraphs are given.
APA, Harvard, Vancouver, ISO, and other styles
5

Yang, Xiuliang, and Haobo Yang. "ISOMORPHISMS OF TRANSFORMATION SEMIGROUPS ASSOCIATED WITH SIMPLE DIGRAPHS." Asian-European Journal of Mathematics 02, no. 04 (December 2009): 727–37. http://dx.doi.org/10.1142/s1793557109000601.

Full text
Abstract:
For each simple digraph D, we introduce its associated semigroup S(D) and its widened digraph W(D). We show that, for any two finite simple digraphs D1 and D2, S(D1) and S(D2) are isomorphic as semigroups if and only if W(D1) and W(D2) are isomorphic as digraphs.
APA, Harvard, Vancouver, ISO, and other styles
6

Elmali, Ceren Sultan, Tamer Uğur, and Tuǧçe Kunduraci. "On New Knot Tables." ITM Web of Conferences 22 (2018): 01019. http://dx.doi.org/10.1051/itmconf/20182201019.

Full text
Abstract:
The quasi-pseudo metrics on the vertices of a digraph induces a unique bitopology. In this work, we obtained that a bitopology is associated with any knot km, where k is crossing points of knot and m = 1,2 by using quasi-pseudo metrics on the vertices of a digraph which is called knot digraph by us, when we consider relation between the knot and its graph (knot digraph notation). Also some topological properties of bitopology obtained by using quasipseudo metric and associated with the knot digraphs are investigated.
APA, Harvard, Vancouver, ISO, and other styles
7

Yang, Xiuwen, Xiaogang Liu, and Ligong Wang. "On the sum of the k largest absolute values of Laplacian eigenvalues of digraphs." Electronic Journal of Linear Algebra 39 (July 20, 2023): 409–22. http://dx.doi.org/10.13001/ela.2023.7503.

Full text
Abstract:
Let $L(G)$ be the Laplacian matrix of a digraph $G$ and $S_k(G)$ be the sum of the $k$ largest absolute values of Laplacian eigenvalues of $G$. Let $C_n^+$ be a digraph with $n+1$ vertices obtained from the directed cycle $C_n$ by attaching a pendant arc whose tail is on $C_n$. A digraph is $\mathbb{C}_n^+$-free if it contains no $C_{\ell}^+$ as a subdigraph for any $2\leq \ell \leq n-1$. In this paper, we present lower bounds of $S_n(G)$ of digraphs of order $n$. We provide the exact values of $S_k(G)$ of directed cycles and $\mathbb{C}_n^+$-free unicyclic digraphs. Moreover, we obtain upper bounds of $S_k(G)$ of $\mathbb{C}_n^+$-free digraphs which have vertex-disjoint directed cycles.
APA, Harvard, Vancouver, ISO, and other styles
8

Smerchinskaya, Svetlana O., and Nina P. Yashina. "Preference levels for clusters of alternatives." International Journal of Modeling, Simulation, and Scientific Computing 10, no. 04 (August 2019): 1950019. http://dx.doi.org/10.1142/s1793962319500193.

Full text
Abstract:
In the decision-making tasks for ranking the alternatives and choosing the best ones, procedures on the digraphs are often used. A digraph of the aggregated relation on a set of alternatives for information of experts or criteria is preconstructed. If the digraph does not contain any cycles, then the Demukron algorithm for partitioning the digraph into levels can be used to order the alternatives by preference. This algorithm cannot be applied if there are clusters consisting of equivalent alternatives. In the paper the algorithm for partitioning an arbitrary digraph of into preference levels is proposed. In contrast to the standard procedure, the digraph of the aggregated relation admits the presence of cycles, and, consequently, of equivalent vertexes-alternatives. The vertexes in any cycle of digraph belong to one level of preference.
APA, Harvard, Vancouver, ISO, and other styles
9

Alomari, Omar, Mohammad Abudayah, and Torsten Sander. "The non-negative spectrum of a digraph." Open Mathematics 18, no. 1 (February 19, 2020): 22–35. http://dx.doi.org/10.1515/math-2020-0005.

Full text
Abstract:
Abstract Given the adjacency matrix A of a digraph, the eigenvalues of the matrix AAT constitute the so-called non-negative spectrum of this digraph. We investigate the relation between the structure of digraphs and their non-negative spectra and associated eigenvectors. In particular, it turns out that the non-negative spectrum of a digraph can be derived from the traditional (adjacency) spectrum of certain undirected bipartite graphs.
APA, Harvard, Vancouver, ISO, and other styles
10

Shi, Mei, Weihao Xia, Mingyue Xiao, and Jihui Wang. "The majority coloring of the join and Cartesian product of some digraph." MATEC Web of Conferences 355 (2022): 02004. http://dx.doi.org/10.1051/matecconf/202235502004.

Full text
Abstract:
A majority coloring of a digraph is a vertex coloring such that for every vertex, the number of vertices with the same color in the out-neighborhood does not exceed half of its out-degree. Kreutzer, Oum, Seymour and van der Zyper proved that every digraph is majority 4-colorable and conjecture that every digraph has a majority 3-coloring. This paper mainly studies the majority coloring of the joint and Cartesian product of some special digraphs and proved the conjecture is true for the join graph and the Cartesian product. According to the influence of the number of vertices in digraph, we prove the majority coloring of the joint and Cartesian product of some digraph.
APA, Harvard, Vancouver, ISO, and other styles
More sources

Dissertations / Theses on the topic "Digraph"

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 text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
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 text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
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 text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
4

Oliveira, Ana Karolinna Maia de. "Subdivisions de digraphes." Thesis, Nice, 2014. http://www.theses.fr/2014NICE4084/document.

Full text
Abstract:
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 F
In 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
APA, Harvard, Vancouver, ISO, and other styles
5

Li, Ruijuan. "k-ordered graphs & out-arc pancyclicity on digraphs." Aachen Mainz, 2009. http://d-nb.info/994128894/04.

Full text
APA, Harvard, Vancouver, ISO, and other styles
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
APA, Harvard, Vancouver, ISO, and other styles
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
APA, Harvard, Vancouver, ISO, and other styles
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 text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
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 text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
10

Smith, Heather Christina. "Zero Divisors among Digraphs." VCU Scholars Compass, 2010. http://scholarscompass.vcu.edu/etd/2120.

Full text
Abstract:
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.
APA, Harvard, Vancouver, ISO, and other styles
More sources

Books on the topic "Digraph"

1

Voshtina, Oltion. A value for digraph-restricted games. Arlington: Dept. of Mathematics, University of Texas at Arlington, 1997.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
2

Andrei, Neculai. Sparse systems: Digraph approach of large-scale linear systems theory. Köln: Verlag TÜV Rheinland, 1985.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
3

Bang-Jensen, Jørgen, and Gregory Z. Gutin. Digraphs. London: Springer London, 2009. http://dx.doi.org/10.1007/978-1-84800-998-1.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Bang-Jensen, Jørgen, and Gregory Gutin. Digraphs. London: Springer London, 2002. http://dx.doi.org/10.1007/978-1-4471-3886-0.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Linda, Lesniak, and Behzad Mehdi, eds. Graphs & digraphs. 2nd ed. Monterey, Calif: Wadsworth & Brooks/Cole Advanced Books & Software, 1986.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
6

Linda, Lesniak, and Zhang Ping 1957-, eds. Graphs & digraphs. 5th ed. Boca Raton, FL: Chapman and Hall/CRC, 2010.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
7

Linda, Lesniak, ed. Graphs & digraphs. 4th ed. Boca Raton: Chapman & Hall/CRC, 2005.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
8

Company, Steck-Vaughn, ed. Blends and digraphs: Fl. Austin, Tex: Steck-Vaughn Co., 2002.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
9

Company, Steck-Vaughn, ed. Blends and digraphs: Sp. Austin, Tex: Steck-Vaughn Co., 2002.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
10

Company, Steck-Vaughn, ed. Blends and digraphs: Wh. Austin, Tex: Steck-Vaughn Co., 2002.

Find full text
APA, Harvard, Vancouver, ISO, and other styles
More sources

Book chapters on the topic "Digraph"

1

Kottarathil, Jomon, Sudev Naduvath, and Joseph Varghese Kureethara. "Digraph Decompositions." In Graph Theory and Decomposition, 39–48. Boca Raton: Chapman and Hall/CRC, 2024. http://dx.doi.org/10.1201/9781003391678-3.

Full text
APA, Harvard, Vancouver, ISO, and other styles
2

Kreutzer, Stephan, and Sebastian Ordyniak. "Digraph Decompositions and Monotonicity in Digraph Searching." In Graph-Theoretic Concepts in Computer Science, 336–47. Berlin, Heidelberg: Springer Berlin Heidelberg, 2008. http://dx.doi.org/10.1007/978-3-540-92248-3_30.

Full text
APA, Harvard, Vancouver, ISO, and other styles
3

Guo, Yubao, and Michel Surmacs. "Miscellaneous Digraph Classes." In Springer Monographs in Mathematics, 517–74. Cham: Springer International Publishing, 2018. http://dx.doi.org/10.1007/978-3-319-71840-8_11.

Full text
APA, Harvard, Vancouver, ISO, and other styles
4

Bisdorff, Raymond. "On Computing Digraph Kernels." In International Series in Operations Research & Management Science, 225–49. Cham: Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-030-90928-4_17.

Full text
APA, Harvard, Vancouver, ISO, and other styles
5

Xu, Wei, Xiaole Yue, and Qun He. "Iterative Digraph Cell Mapping Method." In Global Analysis of Nonlinear Dynamics, 51–74. New York, NY: Springer New York, 2012. http://dx.doi.org/10.1007/978-1-4614-3128-2_3.

Full text
APA, Harvard, Vancouver, ISO, and other styles
6

Kirkland, Stephen J. "Digraph-based Conditioning for Markov Chains." In Positive Systems, 215–16. Berlin, Heidelberg: Springer Berlin Heidelberg, 2004. http://dx.doi.org/10.1007/978-3-540-44928-7_29.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Berlinkov, Mikhail V. "Synchronizing Automata on Quasi-Eulerian Digraph." In Implementation and Application of Automata, 90–100. Berlin, Heidelberg: Springer Berlin Heidelberg, 2012. http://dx.doi.org/10.1007/978-3-642-31606-7_8.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Hochstättler, Winfried, and Johanna Wiehe. "The Chromatic Polynomial of a Digraph." In AIRO Springer Series, 1–14. Cham: Springer International Publishing, 2020. http://dx.doi.org/10.1007/978-3-030-63072-0_1.

Full text
APA, Harvard, Vancouver, ISO, and other styles
9

Kenkre, Sreyash, Vinayaka Pandit, Manish Purohit, and Rishi Saket. "On the Approximability of Digraph Ordering." In Algorithms - ESA 2015, 792–803. Berlin, Heidelberg: Springer Berlin Heidelberg, 2015. http://dx.doi.org/10.1007/978-3-662-48350-3_66.

Full text
APA, Harvard, Vancouver, ISO, and other styles
10

Ito, Takehiro, Yuni Iwamasa, Yasuaki Kobayashi, Yu Nakahata, Yota Otachi, and Kunihiro Wasa. "Reconfiguring Directed Trees in a Digraph." In Lecture Notes in Computer Science, 343–54. Cham: Springer International Publishing, 2021. http://dx.doi.org/10.1007/978-3-030-89543-3_29.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "Digraph"

1

Carvalho, Vinícius De Souza, Cândida Nunes Da Silva, and Orlando Lee. "Linial's Dual Conjecture for Path-Spine Digraphs." In Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2020. http://dx.doi.org/10.5753/etc.2020.11098.

Full text
Abstract:
Given a digraph D, a coloring 𝒞 of D is a partition of V(D) into stable sets. The k-norm of 𝒞 is defined as ΣC∈𝒞 min{|C|, k}. A coloring of D with minimum k-norm has its k-norm noted by χk(D). A (path)-k-pack of a digraph D is a set of k vertex-disjoint (directed) paths of D. The weight of a k-pack is the number of vertices covered by the k-pack. We denote by λk(D) the weight of a maximum k-pack. Linial conjectured that χk(D) ≤ λk(D) for every digraph. Such conjecture remains open, but has been proved for some classes of digraphs. We prove the conjecture for path-spine digraphs, defined as follows. A digraph D is path-spine if there exists a partition {X, Y} of V(D) such that D[X] has a Hamilton path and every arc in D[Y] belongs to a single path Q.
APA, Harvard, Vancouver, ISO, and other styles
2

Zhou, Honglu, Advith Chegu, Samuel S. Sohn, Zuohui Fu, Gerard de Melo, and Mubbasir Kapadia. "Harnessing Neighborhood Modeling and Asymmetry Preservation for Digraph Representation Learning." In Thirty-Second International Joint Conference on Artificial Intelligence {IJCAI-23}. California: International Joint Conferences on Artificial Intelligence Organization, 2023. http://dx.doi.org/10.24963/ijcai.2023/731.

Full text
Abstract:
Digraph Representation Learning aims to learn representations for directed homogeneous graphs (digraphs). Prior work is largely constrained or has poor generalizability across tasks. Most Graph Neural Networks exhibit poor performance on digraphs due to the neglect of modeling neighborhoods and preserving asymmetry. In this paper, we address these notable challenges by leveraging hyperbolic collaborative learning from multi-ordered partitioned neighborhoods and asymmetry-preserving regularizers. Our resulting formalism, Digraph Hyperbolic Networks (D-HYPR), is versatile for multiple tasks including node classification, link presence prediction, and link property prediction. The efficacy of D-HYPR was meticulously examined against 21 previous techniques, using 8 real-world digraph datasets. D-HYPR statistically significantly outperforms the current state of the art. We release our code at https://github. com/hongluzhou/dhypr.
APA, Harvard, Vancouver, ISO, and other styles
3

Sambinelli, M., C. N. Da Silva, and O. Lee. "Diperfect Digraphs." In III Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2018. http://dx.doi.org/10.5753/etc.2018.3173.

Full text
Abstract:
Let D be a digraph. A path partition P of D is a collection of paths such that {V (P ) : P 2 P } is a partition of V (D). We say D is ↵ -diperfect if for every maximum stable set S of D there exists a path partition P of D such that |S \ V (P )| = 1 for all P 2 P and this property holds for every induced subdigraph of D. A digraph C is an anti-directed odd cycle if (i) the underlying graph of C is a cycle x1x2 · · · x2k+1x1, where k 2, (ii) the longest path in C has length 2, and (iii) each of the vertices x1, x2, x3, x4, x6, x8, . . . , x2k is either a source or a sink. Berge (1982) conjectured that a digraph D is ↵ -diperfect if, and only if, D contains no induced anti-directed odd cycle. In this work, we verify this conjecture for digraphs whose underlying graph is series-parallel and for in-semicomplete digraphs.
APA, Harvard, Vancouver, ISO, and other styles
4

Sambinelli, M., C. N. Lintzmayer, C. N. Da Silva, and O. Lee. "Vertex partition problems in digraphs ⇤." In III Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2018. http://dx.doi.org/10.5753/etc.2018.3174.

Full text
Abstract:
Let D be a digraph and k be a positive integer. Linial (1981) conjectured that the k-norm of a k-minimum path partition of a digraph D is at most max{PC2 C |C| : C is a partial k-coloring of D}. Berge (1982) conjectured that every k-minimum path partition contains a partial k-coloring orthogonal to it. It is well known that Berge's Conjecture implies Linial's Conjecture. In this work, we verify Berge's Conjecture, and consequently Linial's Conjecture, for locally in-semicomplete digraphs and k-minimum path partitions containing only two paths. Moreover, we verify a conjecture related to Berge's and Linial's Conjectures for locally in-semicomplete digraphs.
APA, Harvard, Vancouver, ISO, and other styles
5

Cruz, Jadder Bismarck de Sousa, Cândida Nunes da Silva, and Orlando Lee. "Some Partial Results on Linial's Conjecture for Matching-Spine Digraphs." In Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2021. http://dx.doi.org/10.5753/etc.2021.16386.

Full text
Abstract:
Let $k$ be a positive integer. A \emph{partial $k$-coloring} of a digraph $D$ is a set $\calC$ of $k$ disjoint stable sets and has \emph{weight} defined as $\sum_{C \in \calC} |C|$. An \emph{optimal} $k$-coloring is a $k$-coloring of maximum weight. A \emph{path partition} of a digraph $D$ is a set $\calP$ of disjoint paths of $D$ that covers its vertex set and has \emph{$k$-norm} defined as $\sum_{P \in \mathcal{P}} \min\{|P|,k\}$. A path partition $\calP$ is \emph{$k$-optimal} if it has minimum $k$-norm. A digraph $D$ is \emph{matching-spine} if its vertex set can be partitioned into sets $X$ and $Y$, such that $D[X]$ has a Hamilton path and the arc set of $D[Y]$ is a matching. Linial (1981) conjectured that the $k$-norm of a $k$-optimal path partition of a digraph is at most the weight of an optimal partial $k$-coloring. We present some partial results on this conjecture for matching-spine digraphs.
APA, Harvard, Vancouver, ISO, and other styles
6

Zhang, Yu, Xiaofei Liao, Hai Jin, Bingsheng He, Haikun Liu, and Lin Gu. "DiGraph." In ASPLOS '19: Architectural Support for Programming Languages and Operating Systems. New York, NY, USA: ACM, 2019. http://dx.doi.org/10.1145/3297858.3304029.

Full text
APA, Harvard, Vancouver, ISO, and other styles
7

Marshall, Linda, and Derrick Kourie. "Deriving a digraph isomorphism for digraph compliance measurement." In the 2010 Annual Research Conference of the South African Institute of Computer Scientists and Information Technologists. New York, New York, USA: ACM Press, 2010. http://dx.doi.org/10.1145/1899503.1899521.

Full text
APA, Harvard, Vancouver, ISO, and other styles
8

Silva, Caroline A. de Paula, Orlando Lee, and Cândida N. da Silva. "χ-Diperfect Digraphs." In Concurso de Teses e Dissertações. Sociedade Brasileira de Computação - SBC, 2023. http://dx.doi.org/10.5753/ctd.2023.229897.

Full text
Abstract:
In 1982, Berge defined the class of χ-diperfect digraphs. A digraph D is χ-diperfect if for every induced subdigraph H of D and every minimum coloring S of H there exists a path P of H with exactly one vertex of each color class of S. Berge also showed examples of non-χ-diperfect orientations of odd cycles and their complements. The ultimate goal in this research area is to obtain a characterization of χ-diperfect digraphs in terms of forbidden induced subdigraphs. In this work, we give steps towards this goal by presenting characterizations of orientations of odd cycles and their complements that are χ-diperfect. We also show that certain classes of digraphs are χ-diperfect. Moreover, we present minimal non-χ-diperfect digraphs that were unknown.
APA, Harvard, Vancouver, ISO, and other styles
9

Franco, Álvaro J. P., and Marcelo E. Vendramin. "Super-colored paths in digraphs." In Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2021. http://dx.doi.org/10.5753/etc.2021.16389.

Full text
Abstract:
We work in an Anthropology application where it is desired to enumerate colored rings (structures that look like cycles) present in kinship net-works. For this goal, we came across the following question: for all vertex v of a vertex-colored digraph, how many colors (in maximum) a path starting in v can have? The answer for this question would help us to enumerate the colored rings since we would know how many colors a ring evolving some vertices could have, in maximum. Here, we call a path as v-super-colored if it starts in vertex v and it has the maximum amount of colors among all paths starting in v. We show that the problem to find the number of colors of v-super-colored paths for all v is NP-hard when the input digraph is general. We describe a simple algorithm which demonstrates that the problem is tractable if the input digraphis acyclic and the number of colors is small.
APA, Harvard, Vancouver, ISO, and other styles
10

Cohen, Gerard, Emanuela Fachini, and Janos Korner. "On digraph-different permutations." In 2008 International Symposium on Information Theory and Its Applications (ISITA). IEEE, 2008. http://dx.doi.org/10.1109/isita.2008.4895579.

Full text
APA, Harvard, Vancouver, ISO, and other styles

Reports on the topic "Digraph"

1

Kucherova, Hanna, Anastasiia Didenko, Olena Kravets, Yuliia Honcharenko, and Aleksandr Uchitel. Scenario forecasting information transparency of subjects' under uncertainty and development of the knowledge economy. [б. в.], October 2020. http://dx.doi.org/10.31812/123456789/4469.

Full text
Abstract:
Topicality of modeling information transparency is determined by the influence it has on the effectiveness of management decisions made by an economic entity in the context of uncertainty and information asymmetry. It has been found that information transparency is a poorly structured category which acts as a qualitative characteristic of information and at certain levels forms an additional spectrum of properties of the information that has been adequately perceived or processed. As a result of structuring knowledge about the factor environment, a fuzzy cognitive model of information transparency was constructed in the form of a weighted digraph. Structural analysis and scenario forecasting of optimal alternatives of the fuzzy cognitive model made it possible to evaluate the classes of factors, identify their limited relations, establish the centrality of the roles of information transparency and information and communication security in the system built and evaluate their importance when modeling the situation self-development. Information visibility, reliability and availability have been found to have the strongest impact on the system. Taking into account different initial weights of the key factors — information transparency and information and communication security — the study substantiates the strategic ways for economic entities to achieve their goals in the context of uncertainty and information asymmetry, which allows us to use this approach as a tool for strategic management in the information environment.
APA, Harvard, Vancouver, ISO, and other styles
2

Gao, Chunkai, Francesco Bullo, and Jorge Cortes. Notes on Averaging Over Acyclic Digraphs and Discrete Coverage Control. Fort Belvoir, VA: Defense Technical Information Center, January 2006. http://dx.doi.org/10.21236/ada459077.

Full text
APA, Harvard, Vancouver, ISO, and other styles
You might also be interested in the extended bibliographies on the topic 'Digraph' for particular source types:
Journal articles Dissertations / Theses Books
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography