pith. sign in

arxiv: 1702.07914 · v3 · pith:6RITTT4Unew · submitted 2017-02-25 · 💻 cs.DM

On Chordal-k-Generalized Split Graphs

classification 💻 cs.DM
keywords splitchordal-generalizedgraphscharacterizegraphcasechordal
0
0 comments X
read the original abstract

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 \setminus 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.