MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am interested in the properties of the following subclass of split graphs:

The class consists of all split graphs $G=(C\cup I)$ where $C$ is a clique and $I$ an independent set, and every pair of vertices in $I$ have at least one common neighbor in $C$.

Does this class of graphs have a special name? Has this class and its properties been studied? If so, what would be some good references for this?

share|cite|improve this question
up vote 7 down vote accepted

Split graphs of diameter 2?

share|cite|improve this answer
I guess that's all that can be said about these. I searched far and wide, these don't seem to have any specific name. Thank you. – gphilip Aug 25 '10 at 3:42

I don't know if this can help you, but it's easy to see that your class is a superclass of connected threshold graphs. I think that the inclusion is strict, since $S_3$(link) is in your class, but is not a threshold graph.

share|cite|improve this answer
Thank you, that helps a bit. – gphilip Sep 19 '10 at 23:48

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.