Strong cliques and equistability of EPT graphs

In 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 gene...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Alcón, Liliana Graciela, Gutiérrez, Marisa, Kovács, István, Milanič, Martin, Rizzi, Romeo
Formato:	Articulo
Lenguaje:	Inglés
Publicado:	2016
Materias:	Matemática Ept graph Equistable graph General partition graph Strong clique Triangle condition Triangle graph
Acceso en línea:	http://sedici.unlp.edu.ar/handle/10915/95926 https://ri.conicet.gov.ar/11336/54193
Aporte de:	SEDICI (UNLP) de Universidad Nacional de La Plata

id	I19-R120-10915-95926
record_format	dspace
institution	Universidad Nacional de La Plata
institution_str	I-19
repository_str	R-120
collection	SEDICI (UNLP)
language	Inglés
topic	Matemática Ept graph Equistable graph General partition graph Strong clique Triangle condition Triangle graph
spellingShingle	Matemática Ept graph Equistable graph General partition graph Strong clique Triangle condition Triangle graph Alcón, Liliana Graciela Gutiérrez, Marisa Kovács, István Milanič, Martin Rizzi, Romeo Strong cliques and equistability of EPT graphs
topic_facet	Matemática Ept graph Equistable graph General partition graph Strong clique Triangle condition Triangle graph
description	In 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.
format	Articulo Articulo
author	Alcón, Liliana Graciela Gutiérrez, Marisa Kovács, István Milanič, Martin Rizzi, Romeo
author_facet	Alcón, Liliana Graciela Gutiérrez, Marisa Kovács, István Milanič, Martin Rizzi, Romeo
author_sort	Alcón, Liliana Graciela
title	Strong cliques and equistability of EPT graphs
title_short	Strong cliques and equistability of EPT graphs
title_full	Strong cliques and equistability of EPT graphs
title_fullStr	Strong cliques and equistability of EPT graphs
title_full_unstemmed	Strong cliques and equistability of EPT graphs
title_sort	strong cliques and equistability of ept graphs
publishDate	2016
url	http://sedici.unlp.edu.ar/handle/10915/95926 https://ri.conicet.gov.ar/11336/54193
work_keys_str_mv	AT alconlilianagraciela strongcliquesandequistabilityofeptgraphs AT gutierrezmarisa strongcliquesandequistabilityofeptgraphs AT kovacsistvan strongcliquesandequistabilityofeptgraphs AT milanicmartin strongcliquesandequistabilityofeptgraphs AT rizziromeo strongcliquesandequistabilityofeptgraphs
bdutipo_str	Repositorios
_version_	1764820493376946177

Strong cliques and equistability of EPT graphs

Ejemplares similares