On two variants of split graphs : 2-unipolar graph and k-probe-split graph

Revista con referato

Guardado en:
Detalles Bibliográficos
Autores principales: Grippo, Luciano Norberto, Moyano, Verónica A.
Formato: Artículo publishedVersion
Lenguaje:Inglés
Publicado: EDP Sciences 2026
Materias:
2-unipolar graph
K-probe-split graph
Split-width
Matemáticas
Matemática Aplicada
Acceso en línea:http://repositorio.ungs.edu.ar:8080/xmlui/handle/UNGS/2670
Aporte de:
Repositorio Institucional Digital de Acceso Abierto (UNGS) de Universidad Nacional de General Sarmiento
id I71-R177-UNGS-2670
record_format dspace
spelling I71-R177-UNGS-26702026-01-14T10:56:59Z On two variants of split graphs : 2-unipolar graph and k-probe-split graph Grippo, Luciano Norberto Moyano, Verónica A. 2-unipolar graph K-probe-split graph Split-width Matemáticas Matemática Aplicada Revista con referato Fil: Grippo, Luciano Norberto. Universidad Nacional de General Sarmiento. Instituto de Ciencias; Argentina. Fil: Grippo, Luciano Norberto. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. A graph is called split if its vertex set can be partitioned into a stable set and a clique. In this article, we studied two variants of split graphs. A graph G is polar if its vertex set can be partitioned into two sets A and B such that G[A] is a complete multipartite graph and G[B] is a disjoint union of complete graphs. A 2-unipolar graph is a polar graph G such that G[A] is a clique and G[B] is the disjoint union of complete graphs with at most two vertices. We present a minimal forbidden induced subgraph characterization for 2-unipolar graphs. In addition, we show that they can be represented as an intersection of substars of special cacti. Let G be a graph class, the G-width of a graph G is the minimum positive integer k such that there exist k independent sets N1, … , Nk such that a set F of nonedges of G, whose endpoints belong to some Ni with i = 1, … , k, can be added so that the resulting graph G' belongs to G. We say that a graph G is k-probe-G if it has G-width at most k and when G is the class of split graphs it is denominated k-probe-split. We prove that deciding, given a graph G and a positive integer k, whether G is a h-probe-split graph for some h ? k is NP-complete. Besides, a characterization by minimal forbidden induced subgraphs for 2-probe-split cographs is presented. 2026-01-14T10:56:59Z 2026-01-14T10:56:59Z 2024 info:eu-repo/semantics/article info:ar-repo/semantics/artículo info:eu-repo/semantics/publishedVersion Grippo, L. N. y Moyano, V. A. (2024). On two variants of split graphs: 2-unipolar graph and k-probe-split graph. RAIRO-Operation Research, 58(4), 3597-3606. 0399-0559 http://repositorio.ungs.edu.ar:8080/xmlui/handle/UNGS/2670 eng http://dx.doi.org/10.1051/ro/2023149 info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-nc-nd/4.0/ application/pdf application/pdf EDP Sciences RAIRO-Operation Research. Jul. 2024; 58(4): 3597-3606 https://www.rairo-ro.org/articles/ro/abs/2024/04/contents/contents.html
institution Universidad Nacional de General Sarmiento
institution_str I-71
repository_str R-177
collection Repositorio Institucional Digital de Acceso Abierto (UNGS)
language Inglés
orig_language_str_mv eng
topic 2-unipolar graph
K-probe-split graph
Split-width
Matemáticas
Matemática Aplicada
spellingShingle 2-unipolar graph
K-probe-split graph
Split-width
Matemáticas
Matemática Aplicada
Grippo, Luciano Norberto
Moyano, Verónica A.
On two variants of split graphs : 2-unipolar graph and k-probe-split graph
topic_facet 2-unipolar graph
K-probe-split graph
Split-width
Matemáticas
Matemática Aplicada
description Revista con referato
format Artículo
Artículo
publishedVersion
author Grippo, Luciano Norberto
Moyano, Verónica A.
author_facet Grippo, Luciano Norberto
Moyano, Verónica A.
author_sort Grippo, Luciano Norberto
title On two variants of split graphs : 2-unipolar graph and k-probe-split graph
title_short On two variants of split graphs : 2-unipolar graph and k-probe-split graph
title_full On two variants of split graphs : 2-unipolar graph and k-probe-split graph
title_fullStr On two variants of split graphs : 2-unipolar graph and k-probe-split graph
title_full_unstemmed On two variants of split graphs : 2-unipolar graph and k-probe-split graph
title_sort on two variants of split graphs : 2-unipolar graph and k-probe-split graph
publisher EDP Sciences
publishDate 2026
url http://repositorio.ungs.edu.ar:8080/xmlui/handle/UNGS/2670
work_keys_str_mv AT grippolucianonorberto ontwovariantsofsplitgraphs2unipolargraphandkprobesplitgraph
AT moyanoveronicaa ontwovariantsofsplitgraphs2unipolargraphandkprobesplitgraph
_version_ 1858615806601986048

Ejemplares similares