1. Pantheon
  2. Trabalhos Acadêmicos e Técnicos
  3. Relatórios Técnicos e de Pesquisa
  4. Relatórios
Please use this identifier to cite or link to this item: http://hdl.handle.net/11422/1560
Full metadata record
DC FieldValueLanguage
dc.contributor.authorSzwarcfiter, Jayme Luiz-
dc.date.accessioned2017-03-14T17:33:49Z-
dc.date.available2023-12-21T03:02:48Z-
dc.date.issued1990-10-31-
dc.identifier.citationSZWARCFITER, J. L. On edge transitivity of directed graphs. Rio de Janeiro: NCE, UFRJ, 1990. 14 p. (Relatório Técnico, 26/90)pt_BR
dc.identifier.urihttp://hdl.handle.net/11422/1560-
dc.description.abstractWe examine edge transitivity of directed graphs. The class of local comparability graphs is defined as the underlying graphs of locally edge transitive digraphs. The latter generalize edge transitive orientations, while local comparability graphs include comparability, anti-comparability and circle graphs. Recognizing local comperability graphs is NP-complete, however they are differences of comparability graphs. We define dimension so as to generalize that of an edge transitive digraph. Connect proper interval graphs are characterized as exaclty the class of local comparability graphs of dimension one. Finally, a characterization of circle graphs is given also in terms of edge transitivity.en
dc.languageengpt_BR
dc.relation.ispartofRelatório Técnico NCEpt_BR
dc.rightsAcesso Abertopt_BR
dc.subjectGrafos direcionadospt_BR
dc.titleOn edge transitivity of directed graphspt_BR
dc.typeRelatóriopt_BR
dc.description.resumoExaminamos transitividade em arestas de grafos direcionados. A classe dos grafos de comparabilidade local é definida como os grafos subjacentes dos dígrafos localmente transitivos em arestas. Estes últimos generalizam orientações transitivas em arestas, enquanto que grafos de comparabilidade local incluem os de comparabilidade, anti-comparabilidade e circulares. Reconhecer grafos de comparabilidade local é NP-completo, contudo, eles constituem diferenças de grafos de comparabilidade. Definimos dimensão de modo a generalizar a de um dígrafo transitivo em arestas. Os grafos conexos de intervalo próprio são caracterizados exatamente como a classe dos de comparabilidade local de dimensão um. Finalmente, uma caracterização dos grafos circulares é apresentada em termos de transitividade em arestas.pt_BR
dc.publisher.countryBrasilpt_BR
dc.publisher.departmentInstituto Tércio Pacitti de Aplicações e Pesquisas Computacionaispt_BR
dc.subject.cnpqCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAOpt_BR
dc.citation.issue2690pt_BR
dc.embargo.termsabertopt_BR
Appears in Collections:Relatórios

Files in This Item:
File Description SizeFormat 
26_90_000040393.pdf1.18 MBAdobe PDFView/Open
Show simple item record Recommend this item View Statistics


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.