Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

A bipartite graph G contains set of people in one partition (call each node as people node) and their interests in other partition (call it as interest node). There are edges between people and their interests so two people may share same interest vice versa,but there cannot be edge within same partition (as bipartite graph says). Now, from above I'll draw a projected graph $G'(V',E')$ such that

$$V' := \{ v \in V \mid v \textrm{ is a people node}\}$$

$$E' := \{ (u,v) \in V'^2 \mid \textrm{ $u$, $v$ share at least one interest}\}$$

So conversion from $G$ to $G'$ is easy but I've $G'$ now and I want to convert it to $G$ with minimum number of interest nodes. So in order to generalize above "reverse conversion",my claim is,

Decompose $G'$ into minimum number of complete graphs such that each edge of $G'$ must be included in at least one complete graph.The number of complete graphs you get in above decomposition is the number of minimum interest nodes required.

Is it correct?

share|improve this question
add comment

1 Answer 1

Yes, this is correct.

It is worth mentioning that different bipartite graphs may give the same projected graph.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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