Results 201 to 210 of about 34,890 (227)
Some of the next articles are maybe not open access.
Anais do XXXVI Concurso de Teses e Dissertações (CTD 2023), 2022
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.
Caroline Aparecida de Paula Silva +2 more
openaire +1 more source
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.
Caroline Aparecida de Paula Silva +2 more
openaire +1 more source
Journal of Graph Theory, 2014
AbstractThe clique number of a digraph D is the size of the largest bidirectionally complete subdigraph of D. D is perfect if, for any induced subdigraph H of D, the dichromatic number defined by Neumann‐Lara (The dichromatic number of a digraph, J. Combin. Theory Ser. B 33 (1982), 265–270) equals the clique number .
Andres, Stephan Dominique +1 more
openaire +2 more sources
AbstractThe clique number of a digraph D is the size of the largest bidirectionally complete subdigraph of D. D is perfect if, for any induced subdigraph H of D, the dichromatic number defined by Neumann‐Lara (The dichromatic number of a digraph, J. Combin. Theory Ser. B 33 (1982), 265–270) equals the clique number .
Andres, Stephan Dominique +1 more
openaire +2 more sources
Canadian Mathematical Bulletin, 1966
The line - graph of an ordinary graph G is that graph whose points can be put in one-to-one correspondence with the lines of G in such a way that two points of are adjacent if and only if the corresponding lines of G are adjacent. This concept originated with Whitney [ 5 ], has the property that its (point) chromatic number equals the line chromatic
Chartrand, G., Stewart, M. J.
openaire +1 more source
The line - graph of an ordinary graph G is that graph whose points can be put in one-to-one correspondence with the lines of G in such a way that two points of are adjacent if and only if the corresponding lines of G are adjacent. This concept originated with Whitney [ 5 ], has the property that its (point) chromatic number equals the line chromatic
Chartrand, G., Stewart, M. J.
openaire +1 more source
Regular Digraphs Containing a Given Digraph
Canadian Mathematical Bulletin, 1984AbstractLet the maximum degree d of a digraph D be the maximum of the set of all outdegrees and indegrees of the points of D. We prove that every digraph D of order P and maximum degree d has a d-regular superdigraph H with at most d + 1 more points, and that this bound, which is independent of p, is best possible.
Harary, Frank, Karabed, Razmik
openaire +1 more source
Proceedings of the Twenty-Fourth International Conference on Architectural Support for Programming Languages and Operating Systems, 2019
Many systems are recently proposed for large-scale iterative graph analytics on a single machine with GPU accelerators. Despite of many research efforts, for iterative directed graph processing over GPUs, existing solutions suffer from slow convergence speed and high data access cost, because many vertices are ineffectively reprocessed for lots of ...
Yu Zhang +5 more
openaire +1 more source
Many systems are recently proposed for large-scale iterative graph analytics on a single machine with GPU accelerators. Despite of many research efforts, for iterative directed graph processing over GPUs, existing solutions suffer from slow convergence speed and high data access cost, because many vertices are ineffectively reprocessed for lots of ...
Yu Zhang +5 more
openaire +1 more source
Canadian Journal of Mathematics, 1967
SummaryWe call a digraph “antisymmetrical” if there is an automorphismθof its graph, of period 2, which reverses the direction of every edge and maps no edge or vertex onto itself. We construct a theory of flows invariant underθfor such a diagraph. This theory is analogous to the Max Flow Min Cut theory for ordinary flows in digraphs.
openaire +2 more sources
SummaryWe call a digraph “antisymmetrical” if there is an automorphismθof its graph, of period 2, which reverses the direction of every edge and maps no edge or vertex onto itself. We construct a theory of flows invariant underθfor such a diagraph. This theory is analogous to the Max Flow Min Cut theory for ordinary flows in digraphs.
openaire +2 more sources
SIAM Journal on Discrete Mathematics, 2020
zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Pavol Hell +3 more
openaire +2 more sources
zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Pavol Hell +3 more
openaire +2 more sources
1998
Abstract The underlying graph of a digraph D is the graph obtained by replacing each arc of D by the corresponding undirected edge. The converse of D is the digraph obtained by reversing the direction of each arc in D, and the complement of D is the digraph with vertex set Vin which vw is an arc if and only if it is not an arc in D.
Ronald C Read, Robin J Wilson
openaire +1 more source
Abstract The underlying graph of a digraph D is the graph obtained by replacing each arc of D by the corresponding undirected edge. The converse of D is the digraph obtained by reversing the direction of each arc in D, and the complement of D is the digraph with vertex set Vin which vw is an arc if and only if it is not an arc in D.
Ronald C Read, Robin J Wilson
openaire +1 more source
2013
This chapter gives the basic introduction to directed graphs (digraphs) and their pertinent concepts, elements, and frameworks. From a general point of view, the most majority of concepts of digraphs have similar characteristics with networks structures.
Alireza Boloori, Monirehalsadat Mahmoudi
openaire +1 more source
This chapter gives the basic introduction to directed graphs (digraphs) and their pertinent concepts, elements, and frameworks. From a general point of view, the most majority of concepts of digraphs have similar characteristics with networks structures.
Alireza Boloori, Monirehalsadat Mahmoudi
openaire +1 more source
Combinatorics, Probability and Computing, 1995
This paper presents a constructive proof that for any planar digraph G on p vertices, there exists a subset S of the transitive closure of G such that the number of arcs in S is less than or equal to the number of arcs in G, and such that the diameter of G∪S is O(α(p, p)(log p)2).
openaire +1 more source
This paper presents a constructive proof that for any planar digraph G on p vertices, there exists a subset S of the transitive closure of G such that the number of arcs in S is less than or equal to the number of arcs in G, and such that the diameter of G∪S is O(α(p, p)(log p)2).
openaire +1 more source