Strong cliques and equistability of EPT graphs

dc.creatorAlcón, Liliana Graciela
dc.creatorGutiérrez, Marisa
dc.creatorKovács, István
dc.creatorMilanič, Martin
dc.creatorRizzi, Romeo
dc.date2016-04
dc.date2020-05-14T13:56:29Z
dc.date.accessioned2023-07-14T19:54:34Z
dc.date.available2023-07-14T19:54:34Z
dc.identifierhttp://sedici.unlp.edu.ar/handle/10915/95926
dc.identifierhttps://ri.conicet.gov.ar/11336/54193
dc.identifierissn:0166-218X
dc.identifier.urihttps://repositorioslatinoamericanos.uchile.cl/handle/2250/7437160
dc.descriptionIn this paper, we characterize the equistable graphs within the class of EPT graphs, the edge-intersection graphs of paths in a tree. This result generalizes a previously known characterization of equistable line graphs. Our approach is based on the combinatorial features of triangle graphs and general partition graphs. We also show that, in EPT graphs, testing whether a given clique is strong is co-NP-complete. We obtain this hardness result by first showing hardness of the problem of determining whether a given graph has a maximal matching disjoint from a given edge cut. As a positive result, we prove that the problem of testing whether a given clique is strong is polynomial in the class of local EPT graphs, which are defined as the edge intersection graphs of paths in a star and are known to coincide with the line graphs of multigraphs.
dc.descriptionFacultad de Ciencias Exactas
dc.descriptionConsejo Nacional de Investigaciones Científicas y Técnicas
dc.formatapplication/pdf
dc.format13-25
dc.languageen
dc.rightshttp://creativecommons.org/licenses/by-nc-sa/4.0/
dc.rightsCreative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0)
dc.subjectMatemática
dc.subjectEpt graph
dc.subjectEquistable graph
dc.subjectGeneral partition graph
dc.subjectStrong clique
dc.subjectTriangle condition
dc.subjectTriangle graph
dc.titleStrong cliques and equistability of EPT graphs
dc.typeArticulo
dc.typeArticulo


Este ítem pertenece a la siguiente institución