Miao Dongjing
Miao Dongjing

Reputation: 29

What is the name of this type of undirected graph?

Undirected graph G can be partationed into several vertex groups, each vertex pair (u,v) has an edge if "u" and "v" are in the different groups; no edge, otherwise. Intuitively, if we use a vertex "g" to represent a group, and we add an edge (gi,gj) if there are edges between the two group, then the graph G is a clique. Now, we have several such type graphs G1...Gn, each vertex in some Gi may has a same id with a vertex in some Gj.

If we combine graphs G1...Gn to get a graph G',like the example below, What is the name of this type of undirected graph?

example:what properties will the graph G3 have?

Upvotes: 0

Views: 143

Answers (1)

anonymous
anonymous

Reputation: 201

perhaps the groups you mean are independent sets. however, as Henrik pointed out, collapsing to independent sets (even if they are chosen inclusionwise maximal), does not necessarily yield a clique.

Upvotes: 1

Related Questions