On probe 2-clique graphs and probe diamond-free graphs

Given a class G of graphs, probe G graphs are defined as follows. A graph G is probe G if there exists a partition of its vertices into a set of probe vertices and a stable set of nonprobe vertices in such a way that non-edges of G, whose endpoints are nonprobe vertices, can be added so that the res...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Bonomo, Flavia, Durán, Guillermo A., Grippo, Luciano Norberto, Safe, Martín Darío
Publicado:	2015
Materias:	2-clique graphs Diamond-free graphs Probe graphs Diamonds Graphic methods Polynomial approximation Probes Block graphs Chordal graphs Forbidden induced subgraphs Polynomial-time Probe graph Recognition algorithm Graph theory
Acceso en línea:	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14627264_v17_n1_p187_Bonomo http://hdl.handle.net/20.500.12110/paper_14627264_v17_n1_p187_Bonomo
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	paper:paper_14627264_v17_n1_p187_Bonomo
record_format	dspace
spelling	paper:paper_14627264_v17_n1_p187_Bonomo2023-06-08T16:16:18Z On probe 2-clique graphs and probe diamond-free graphs Bonomo, Flavia Durán, Guillermo A. Grippo, Luciano Norberto Safe, Martín Darío 2-clique graphs Diamond-free graphs Probe graphs Diamonds Graphic methods Polynomial approximation Probes 2-clique graphs Block graphs Chordal graphs Diamond-free graphs Forbidden induced subgraphs Polynomial-time Probe graph Recognition algorithm Graph theory Given a class G of graphs, probe G graphs are defined as follows. A graph G is probe G if there exists a partition of its vertices into a set of probe vertices and a stable set of nonprobe vertices in such a way that non-edges of G, whose endpoints are nonprobe vertices, can be added so that the resulting graph belongs to G. We investigate probe 2-clique graphs and probe diamond-free graphs. For probe 2-clique graphs, we present a polynomial-time recognition algorithm. Probe diamond-free graphs are characterized by minimal forbidden induced subgraphs. As a by-product, it is proved that the class of probe block graphs is the intersection between the classes of chordal graphs and probe diamond-free graphs. © 2015 Discrete Mathematics and Theoretical Computer Science (DMTCS). Fil:Bonomo, F. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Durán, G. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Grippo, L.N. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Safe, M.D. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2015 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14627264_v17_n1_p187_Bonomo http://hdl.handle.net/20.500.12110/paper_14627264_v17_n1_p187_Bonomo
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-134
collection	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic	2-clique graphs Diamond-free graphs Probe graphs Diamonds Graphic methods Polynomial approximation Probes 2-clique graphs Block graphs Chordal graphs Diamond-free graphs Forbidden induced subgraphs Polynomial-time Probe graph Recognition algorithm Graph theory
spellingShingle	2-clique graphs Diamond-free graphs Probe graphs Diamonds Graphic methods Polynomial approximation Probes 2-clique graphs Block graphs Chordal graphs Diamond-free graphs Forbidden induced subgraphs Polynomial-time Probe graph Recognition algorithm Graph theory Bonomo, Flavia Durán, Guillermo A. Grippo, Luciano Norberto Safe, Martín Darío On probe 2-clique graphs and probe diamond-free graphs
topic_facet	2-clique graphs Diamond-free graphs Probe graphs Diamonds Graphic methods Polynomial approximation Probes 2-clique graphs Block graphs Chordal graphs Diamond-free graphs Forbidden induced subgraphs Polynomial-time Probe graph Recognition algorithm Graph theory
description	Given a class G of graphs, probe G graphs are defined as follows. A graph G is probe G if there exists a partition of its vertices into a set of probe vertices and a stable set of nonprobe vertices in such a way that non-edges of G, whose endpoints are nonprobe vertices, can be added so that the resulting graph belongs to G. We investigate probe 2-clique graphs and probe diamond-free graphs. For probe 2-clique graphs, we present a polynomial-time recognition algorithm. Probe diamond-free graphs are characterized by minimal forbidden induced subgraphs. As a by-product, it is proved that the class of probe block graphs is the intersection between the classes of chordal graphs and probe diamond-free graphs. © 2015 Discrete Mathematics and Theoretical Computer Science (DMTCS).
author	Bonomo, Flavia Durán, Guillermo A. Grippo, Luciano Norberto Safe, Martín Darío
author_facet	Bonomo, Flavia Durán, Guillermo A. Grippo, Luciano Norberto Safe, Martín Darío
author_sort	Bonomo, Flavia
title	On probe 2-clique graphs and probe diamond-free graphs
title_short	On probe 2-clique graphs and probe diamond-free graphs
title_full	On probe 2-clique graphs and probe diamond-free graphs
title_fullStr	On probe 2-clique graphs and probe diamond-free graphs
title_full_unstemmed	On probe 2-clique graphs and probe diamond-free graphs
title_sort	on probe 2-clique graphs and probe diamond-free graphs
publishDate	2015
url	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_14627264_v17_n1_p187_Bonomo http://hdl.handle.net/20.500.12110/paper_14627264_v17_n1_p187_Bonomo
work_keys_str_mv	AT bonomoflavia onprobe2cliquegraphsandprobediamondfreegraphs AT duranguillermoa onprobe2cliquegraphsandprobediamondfreegraphs AT grippolucianonorberto onprobe2cliquegraphsandprobediamondfreegraphs AT safemartindario onprobe2cliquegraphsandprobediamondfreegraphs
_version_	1768541908753186816

On probe 2-clique graphs and probe diamond-free graphs

Ejemplares similares