<p>Indeed this concept exists. Two vertices $u,v$ that have the same neighbors are often called twins. They are called true twins if they are also connected, and false twins otherwise. In your definition, all vertices of $X$ are true twins.</p>

<p>It looks like there are several other names in the literature for these concepts. See e.g. this <a href="https://mathoverflow.net/questions/142467/does-the-notion-of-graphs-with-vertex-multiplicity-exist">MO question</a>. In FPT algorithms we sometimes call the number of twin classes into which a graph can be partitioned the neighborhood diversity of the graph, see e.g. <a href="https://link.springer.com/article/10.1007%2Fs00453-011-9554-x?LI=true" rel="nofollow noreferrer">here</a> (warning: self-citation!), and <a href="https://link.springer.com/chapter/10.1007/978-3-642-28050-4_21" rel="nofollow noreferrer">here</a> for the related notion of twin-cover.</p>

CC BY-SA 3.0
2018-01-18T17:21:05.713Z
this MO question, what does MO mean?
Ginger
CC BY-SA 3.0
2018-01-18T18:11:27.823Z
@Ginger Math Overflow
Michael Lampis
CC BY-SA 3.0
2018-01-18T12:13:08.703Z
2018-01-18T12:13:08.703Z
Michael Lampis
<p>Clique modules has been re-discovered many times. In this paper, they are called "critical cliques" (and many other bioinformatics papers and algorithmic graph theory papers)</p>

<p><a href="http://webdocs.cs.ualberta.ca/~ghlin/src/Paper/5root_KKL08.pdf" rel="nofollow noreferrer">http://webdocs.cs.ualberta.ca/~ghlin/src/Paper/5root_KKL08.pdf</a></p>

<p>In this 2005 paper by Hsu: <a href="https://link.springer.com/chapter/10.1007/3-540-56402-0_31" rel="nofollow noreferrer">https://link.springer.com/chapter/10.1007/3-540-56402-0_31</a>  they are called "Type I modules" . This paper of Hsu cites this terminology back to the 1991 paper by Hsu and Ma on obtaining a modular decomposition of chordal graphs (predating the first linear-time modular decomposition algorithm). I think the Hsu+Ma paper is the earliest reference I've seen that assigns any special name to clique modules.</p>

CC BY-SA 3.0
2018-01-19T09:14:26.130Z
2018-01-19T09:14:26.130Z
JimN
<p>For modular decomposition.</p>

<p>X is a module if all members of X have the same set of neighbors among vertices not in X.</p>

<p>I need a special modular decomposition.</p>

<p>X is my module if all members of X have the same set of neighbors among vertices not in X, and X is a clique.</p>

<p>I think this should have been studied already, I would like to avoid redefining it and use some non-standard name, can someone give me some reference?</p>

<graph-theory>
reference for a special modular decomposition
Ginger
# reference for a special modular decomposition

(Asked by: username_0 on 2018-01-17)

For modular decomposition.

X is a module if all members of X have the same set of neighbors among vertices not in X.

I need a special modular decomposition.

X is my module if all members of X have the same set of neighbors among vertices not in X, and X is a clique.

I think this should have been studied already, I would like to avoid redefining it and use some non-standard name, can someone give me some reference?

**Tags:** graph-theory

---

## 2 answers

### Answer by username_1 on 2018-01-18. Score: 2

Indeed this concept exists. Two vertices $u,v$ that have the same neighbors are often called twins. They are called true twins if they are also connected, and false twins otherwise. In your definition, all vertices of $X$ are true twins.

It looks like there are several other names in the literature for these concepts. See e.g. this [MO question](https://mathoverflow.net/questions/142467/does-the-notion-of-graphs-with-vertex-multiplicity-exist). In FPT algorithms we sometimes call the number of twin classes into which a graph can be partitioned the neighborhood diversity of the graph, see e.g. [here](https://link.springer.com/article/10.1007%2Fs00453-011-9554-x?LI=true) (warning: self-citation!), and [here](https://link.springer.com/chapter/10.1007/978-3-642-28050-4_21) for the related notion of twin-cover.

> **Comments:**
> **username_0**: this MO question, what does MO mean?  
> **username_1**: @Ginger Math Overflow  

---

### Answer by username_2 on 2018-01-19. Score: 1

Clique modules has been re-discovered many times. In this paper, they are called "critical cliques" (and many other bioinformatics papers and algorithmic graph theory papers)

<http://webdocs.cs.ualberta.ca/~ghlin/src/Paper/5root_KKL08.pdf>

In this 2005 paper by Hsu: <https://link.springer.com/chapter/10.1007/3-540-56402-0_31> they are called "Type I modules" . This paper of Hsu cites this terminology back to the 1991 paper by Hsu and Ma on obtaining a modular decomposition of chordal graphs (predating the first linear-time modular decomposition algorithm). I think the Hsu+Ma paper is the earliest reference I've seen that assigns any special name to clique modules.


---

