On Tue, 10 Jul 2018, david.coud...@inria.fr wrote:
A clique is a "series" module in the modular decomposition because its
complement is not connected.
See the survey https://arxiv.org/pdf/0912.1457
* A module is of type parallel if G is not connected but its complement it
* A module is of type series if G is connected but its complement is not. In
particular, a clique gives a series module
It is also written in the paper that the smallest prime graph is the P4.
sage: [graphs.PathGraph(i).is_prime() for i in range(5)]
[True, True, False, False, True]
I think the question is similar to asking if number 1 is prime. Directly
by definition given in the doc there can not be a non-prime graph of at
most 2 vertices, as there can't be nontrivial module. (Assuming that
"trivial" means empty subset, single element or the whole graph.)
Anyways, I left this for others to decide.
--
Jori Mäntysalo
