A Characterization of Claw-free CIS Graphs and New Results on the Order of CIS Graphs

A graph is CIS if every maximal clique interesects every maximal stable set. Currently, no good characterization or recognition algorithm for the CIS graphs is known. We characterize graphs in which every maximal matching saturates all vertices of degree at least two and use this result to give a st...

Descripción completa

Detalles Bibliográficos
Autores principales: Alcón, Liliana Graciela, Gutiérrez, Marisa, Milanič, Martin
Formato: Articulo
Lenguaje:Inglés
Publicado: 2019
Materias:
Matemática
CIS graph
Maximal clique
Maximal stable set
Maximal independent set
Randomly internally matchable graph
Claw-free graph
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/103273
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-103273
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
CIS graph
Maximal clique
Maximal stable set
Maximal independent set
Randomly internally matchable graph
Claw-free graph
spellingShingle Matemática
CIS graph
Maximal clique
Maximal stable set
Maximal independent set
Randomly internally matchable graph
Claw-free graph
Alcón, Liliana Graciela
Gutiérrez, Marisa
Milanič, Martin
A Characterization of Claw-free CIS Graphs and New Results on the Order of CIS Graphs
topic_facet Matemática
CIS graph
Maximal clique
Maximal stable set
Maximal independent set
Randomly internally matchable graph
Claw-free graph
description A graph is CIS if every maximal clique interesects every maximal stable set. Currently, no good characterization or recognition algorithm for the CIS graphs is known. We characterize graphs in which every maximal matching saturates all vertices of degree at least two and use this result to give a structural, efficiently testable characterization of claw-free CIS graphs. We answer in the negative a question of Dobson, Hujdurović, Milanič, and Verret [Vertex-transitive CIS graphs, European J. Combin. 44 (2015) 87–98 ] asking whether the number of vertices of every CIS graph is bounded from above by the product of its clique and stability numbers. On the positive side, we show that the question of Dobson et al. has an affirmative answer in the case of claw-free graphs.
format Articulo
Articulo
author Alcón, Liliana Graciela
Gutiérrez, Marisa
Milanič, Martin
author_facet Alcón, Liliana Graciela
Gutiérrez, Marisa
Milanič, Martin
author_sort Alcón, Liliana Graciela
title A Characterization of Claw-free CIS Graphs and New Results on the Order of CIS Graphs
title_short A Characterization of Claw-free CIS Graphs and New Results on the Order of CIS Graphs
title_full A Characterization of Claw-free CIS Graphs and New Results on the Order of CIS Graphs
title_fullStr A Characterization of Claw-free CIS Graphs and New Results on the Order of CIS Graphs
title_full_unstemmed A Characterization of Claw-free CIS Graphs and New Results on the Order of CIS Graphs
title_sort characterization of claw-free cis graphs and new results on the order of cis graphs
publishDate 2019
url http://sedici.unlp.edu.ar/handle/10915/103273
work_keys_str_mv AT alconlilianagraciela acharacterizationofclawfreecisgraphsandnewresultsontheorderofcisgraphs
AT gutierrezmarisa acharacterizationofclawfreecisgraphsandnewresultsontheorderofcisgraphs
AT milanicmartin acharacterizationofclawfreecisgraphsandnewresultsontheorderofcisgraphs
AT alconlilianagraciela characterizationofclawfreecisgraphsandnewresultsontheorderofcisgraphs
AT gutierrezmarisa characterizationofclawfreecisgraphsandnewresultsontheorderofcisgraphs
AT milanicmartin characterizationofclawfreecisgraphsandnewresultsontheorderofcisgraphs
bdutipo_str Repositorios
_version_ 1764820441753452544

Ejemplares similares