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

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 Gis polar if its vertex set can be partitioned into two sets Aand Bsuch 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 Gsuch 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 Gbe a graph class, the G-widthof a graph Gis the minimum positive integer ksuch that there exist kindependent sets N1, … , Nksuch that a set Fof nonedges of G, whose endpoints belong to some Niwith i= 1, … , k, can be added so that the resulting graph G′belongs to G. We say that a graph Gis k-probe-Gif it has G-width at most kand when Gis the class of split graphs it is denominated k-probe-split. We prove that deciding, given a graph Gand a positive integer k, whether Gis a h-probe-split graph for some h≤ kis NP-complete. Besides, a characterization by minimal forbidden induced subgraphs for 2-probe-split cographs is presented.