Disimplicial arcs, transitive vertices, and disimplicial eliminations
Copyright policy )Disimplicial arcs, transitive vertices, and disimplicial eliminations
In this article we deal with the problems of finding the disimplicial arcs of a digraph and recognizing some interesting graph classes defined by their existence. A <i>diclique</i> of a digraph is a pair $V$ → $W$ of sets of vertices such that $v$ → $w$ is an arc for every $v$ ∈ $V$ and $w$ ∈ $W$. An arc $v$ → $w$ is <i>disimplicial</i> when it belongs to a unique maximal diclique. We show that the problem of finding the disimplicial arcs is equivalent, in terms of time and space complexity, to that of locating the transitive vertices. As a result, an efficient algorithm to find the bisimplicial edges of bipartite graphs is obtained. Then, we develop simple algorithms to build disimplicial elimination schemes, which can be used to generate bisimplicial elimination schemes for bipartite graphs. Finally, we study two classes related to perfect disimplicial elimination digraphs, namely weakly diclique irreducible digraphs and diclique irreducible digraphs. The former class is associated to finite posets, while the latter corresponds to dedekind complete finite posets.
- National Scientific and Technical Research Council Argentina
- University of Buenos Aires Argentina
- National University of Quilmes Argentina
- Universidid De Buenos Aires Argentina
dedekind digraphs, FOS: Computer and information sciences, disimplicial arcs, Discrete Mathematics (cs.DM), BISIMPLICIAL EDGES OF BIPARTITE GRAPHS, bisimplicial elimination schemes, [info.info-dm] computer science [cs]/discrete mathematics [cs.dm], Geometry, Epistemology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Graph Labeling, DISIMPLICIAL ELIMINATION SCHEMES, Graph, TRANSITIVE DIGRAPHS, QA1-939, FOS: Mathematics, https://purl.org/becyt/ford/1.2, https://purl.org/becyt/ford/1, Graph Labeling and Dimension Problems, bisimplicial edges of bipartite graphs, Bipartite graph, disimplicial elimination schemes, Graph Spectra and Topological Indices, Digraph, Discrete mathematics, BISIMPLICIAL ELIMINATION SCHEMES, FOS: Philosophy, ethics and religion, Arc (geometry), Philosophy, DEDEKIND DIGRAPHS, Computational Theory and Mathematics, Combinatorics, Computer Science, Physical Sciences, DICLIQUE IRREDUCIBLE DIGRAPHS, Simple (philosophy), diclique irreducible digraphs, transitive digraphs, Geometry and Topology, DISIMPLICIAL ARCS, Transitive relation, Mathematics, Computer Science - Discrete Mathematics, Graph Theory and Algorithms
dedekind digraphs, FOS: Computer and information sciences, disimplicial arcs, Discrete Mathematics (cs.DM), BISIMPLICIAL EDGES OF BIPARTITE GRAPHS, bisimplicial elimination schemes, [info.info-dm] computer science [cs]/discrete mathematics [cs.dm], Geometry, Epistemology, [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], Graph Labeling, DISIMPLICIAL ELIMINATION SCHEMES, Graph, TRANSITIVE DIGRAPHS, QA1-939, FOS: Mathematics, https://purl.org/becyt/ford/1.2, https://purl.org/becyt/ford/1, Graph Labeling and Dimension Problems, bisimplicial edges of bipartite graphs, Bipartite graph, disimplicial elimination schemes, Graph Spectra and Topological Indices, Digraph, Discrete mathematics, BISIMPLICIAL ELIMINATION SCHEMES, FOS: Philosophy, ethics and religion, Arc (geometry), Philosophy, DEDEKIND DIGRAPHS, Computational Theory and Mathematics, Combinatorics, Computer Science, Physical Sciences, DICLIQUE IRREDUCIBLE DIGRAPHS, Simple (philosophy), diclique irreducible digraphs, transitive digraphs, Geometry and Topology, DISIMPLICIAL ARCS, Transitive relation, Mathematics, Computer Science - Discrete Mathematics, Graph Theory and Algorithms
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).0 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!