Xiaoqiang Wang

  1. Algorithms for Unipolar and Generalized Split Graphs.

    Authors: Elaine M. Eschen, Xiaoqiang Wang
    Subjects: Discrete Mathematics
    Abstract

    A graph $G=(V,E)$ is a {\it unipolar graph} if there exits a partition $V=V_1
    \cup V_2$ such that, $V_1$ is a clique and $V_2$ 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 $C_5$-free (and hence, almost all
    perfect graphs) are generalized split graphs.

Syndicate content