1
$\begingroup$

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?

$\endgroup$

2 Answers 2

2
$\begingroup$

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. 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 (warning: self-citation!), and here for the related notion of twin-cover.

$\endgroup$
2
  • $\begingroup$ this MO question, what does MO mean? $\endgroup$
    – Ginger
    Jan 18, 2018 at 17:21
  • $\begingroup$ @Ginger Math Overflow $\endgroup$ Jan 18, 2018 at 18:11
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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