2011/06/29 by Elaine M. Eschen, Xiaoqiang Wang, Eschen, Elaine M. +1
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Graph Labeling and Dimension Problems #cs.DM
paper · pdf · doi:10.48550/arxiv.1106.6061
Please cite this article in press as: E.M. Eschen, X. Wang, Algorithms for unipolar and generalized split graphs. Discrete Applied Mathematics (2013),http://dx.doi.org/10.1016/j.dam.2013.08011
openalex publication_date 2011/06/29 · arxiv created 2013/09/20 · arxiv updated 2013/09/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A graph G=(V,E) is a \it unipolar graph if there exits a partition V=V1 ∪ V2 such that, V1 is a clique and V2 induces the disjoint union of cliques. The complement-closed class of \it generalized split graphs are those graphs G such that either G \it or the complement of G is unipolar. Generalized split graphs are a large subclass of perfect graphs. In fact, it has been shown that almost all C5-free (and hence, almost all perfect graphs) are generalized split graphs. In this paper we present a recognition algorithm for unipolar graphs that utilizes a minimal triangulation of the given graph, and produces a partition when one exists. Our algorithm has running time O(nm^′), where m^′ is the number of edges in a minimal triangulation of the given graph. Generalized split graphs can recognized via this algorithm in O(nm' + n\OLm') = O(n3) time. We give algorithms on unipolar graphs for finding a maximum independent set and a minimum clique cover in O(n+m) time and for finding a maximum clique and a minimum proper coloring in O(n2.5/log n), when a unipolar partition is given. These algorithms yield algorithms for the four optimization problems on generalized split graphs that have the same worst-case time bound. We also prove that the perfect code problem is NP-Complete for unipolar graphs.