2017/02/25 by Andreas Brandstädt, Brandstädt, Andreas, Raffaele Mosca +1
Computer Science · #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #cs.DM
paper · pdf · doi:10.48550/arxiv.1702.07914
arXiv admin note: text overlap with arXiv:1701.03414
arxiv created 2017/04/27 · arxiv updated 2017/04/28
A graph G is a \em chordal-k-generalized split graph if G is chordal and there is a clique Q in G such that every connected component in G[V ∖ Q] has at most k vertices. Thus, chordal-1-generalized split graphs are exactly the split graphs. We characterize chordal-k-generalized split graphs by forbidden induced subgraphs. Moreover, we characterize a very special case of chordal-2-generalized split graphs for which the Efficient Domination problem is \NP-complete.