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

GRIPPO, LUCIANO N.; MOYANO, VERÓNICA A.

RAIRO - RECHERCHE OPERATIONNELLE (OPERATIONS RESEARCH)

EDP SCIENCES S A

Año: 2023

0399-0559

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]$ 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 $mathcal G$ be a graph class, the emph{$mathcal G$-width} of a graph $G$ is the minimum positive integer $k$ such that there exist $k$ independent sets $mathcal{N}_1,ldots,mathcal{N}_k$ such that a set $F$ of nonedges of $G$, whose endpoints belong to some $mathcal{N}_i$ with $i=1,ldots,k$, can be added so that the resulting graph $G´$ belongs to $mathcal G$. We said that a graph $G$ is $k$-probe-$mathcal G$ if it has $mathcal G$-width at most $k$ and when $mathcal 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 $hle k$ is NP-complete. Besides, a characterization by minimal forbidden induced subgraphs for $2$-probe-split cographs is presented.