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 diclique 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 disimpli...

Descripción completa

Detalles Bibliográficos
Autor principal:	Soulignac, Francisco Juan
Publicado:	2015
Materias:	Bisimplicial edges of bipartite graphs Bisimplicial elimination schemes Dedekind digraphs Diclique irreducible digraphs Disimplicial arcs Disimplicial elimination schemes Transitive digraphs Algorithms Directed graphs Set theory Bipartite graphs Elimination scheme Graph theory
Acceso en línea:	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14627264_v17_n2_p101_Eguia http://hdl.handle.net/20.500.12110/paper_14627264_v17_n2_p101_Eguia
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	paper:paper_14627264_v17_n2_p101_Eguia
record_format	dspace
spelling	paper:paper_14627264_v17_n2_p101_Eguia2023-06-08T16:16:18Z Disimplicial arcs, transitive vertices, and disimplicial eliminations Soulignac, Francisco Juan Bisimplicial edges of bipartite graphs Bisimplicial elimination schemes Dedekind digraphs Diclique irreducible digraphs Disimplicial arcs Disimplicial elimination schemes Transitive digraphs Algorithms Directed graphs Set theory Bipartite graphs Dedekind digraphs Diclique irreducible digraphs Disimplicial arcs Elimination scheme Transitive digraphs Graph theory 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 diclique 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 disimplicial 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. © 2015 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France. Fil:Soulignac, F.J. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2015 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14627264_v17_n2_p101_Eguia http://hdl.handle.net/20.500.12110/paper_14627264_v17_n2_p101_Eguia
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-134
collection	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic	Bisimplicial edges of bipartite graphs Bisimplicial elimination schemes Dedekind digraphs Diclique irreducible digraphs Disimplicial arcs Disimplicial elimination schemes Transitive digraphs Algorithms Directed graphs Set theory Bipartite graphs Dedekind digraphs Diclique irreducible digraphs Disimplicial arcs Elimination scheme Transitive digraphs Graph theory
spellingShingle	Bisimplicial edges of bipartite graphs Bisimplicial elimination schemes Dedekind digraphs Diclique irreducible digraphs Disimplicial arcs Disimplicial elimination schemes Transitive digraphs Algorithms Directed graphs Set theory Bipartite graphs Dedekind digraphs Diclique irreducible digraphs Disimplicial arcs Elimination scheme Transitive digraphs Graph theory Soulignac, Francisco Juan Disimplicial arcs, transitive vertices, and disimplicial eliminations
topic_facet	Bisimplicial edges of bipartite graphs Bisimplicial elimination schemes Dedekind digraphs Diclique irreducible digraphs Disimplicial arcs Disimplicial elimination schemes Transitive digraphs Algorithms Directed graphs Set theory Bipartite graphs Dedekind digraphs Diclique irreducible digraphs Disimplicial arcs Elimination scheme Transitive digraphs Graph theory
description	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 diclique 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 disimplicial 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. © 2015 Discrete Mathematics and Theoretical Computer Science (DMTCS), Nancy, France.
author	Soulignac, Francisco Juan
author_facet	Soulignac, Francisco Juan
author_sort	Soulignac, Francisco Juan
title	Disimplicial arcs, transitive vertices, and disimplicial eliminations
title_short	Disimplicial arcs, transitive vertices, and disimplicial eliminations
title_full	Disimplicial arcs, transitive vertices, and disimplicial eliminations
title_fullStr	Disimplicial arcs, transitive vertices, and disimplicial eliminations
title_full_unstemmed	Disimplicial arcs, transitive vertices, and disimplicial eliminations
title_sort	disimplicial arcs, transitive vertices, and disimplicial eliminations
publishDate	2015
url	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14627264_v17_n2_p101_Eguia http://hdl.handle.net/20.500.12110/paper_14627264_v17_n2_p101_Eguia
work_keys_str_mv	AT soulignacfranciscojuan disimplicialarcstransitiveverticesanddisimplicialeliminations
_version_	1768543003125743616

Disimplicial arcs, transitive vertices, and disimplicial eliminations

Ejemplares similares