Reputation: 29
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:
Upvotes: 0
Views: 143
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