0
$\begingroup$

I have to find number of ways (combination) to create graph that for each 3 vertices there are minimum 2 vertices connected. There is n vertices. For example when n=3, there are 7 possible combinations. How can I make this with maybe dynamic programming?

$\endgroup$
  • 1
    $\begingroup$ Try finding what graphs satisfying this condition look like. $\endgroup$ – Yuval Filmus Feb 10 '18 at 21:26
  • 1
    $\begingroup$ Your graphs are the complements of triangle-free graphs. $\endgroup$ – Yuval Filmus Feb 11 '18 at 6:29
2
$\begingroup$

Your condition on the graph is the same as requiring its complement to be triangle-free. It is known that there are a lot of triangle-free graph. Indeed, since every bipartite graph is triangle-free, if we fix a partition of the vertex set into two sets of size $n/2$ (assuming for simplicity that $n$ is even), then we already get $2^{n^2/4}$ triangle-free graphs. It turns out that there aren't that much more, see this question on mathoverflow.

Perhaps you'd be interested in a paper on generating maximal triangle-free graphs up to isomorphism (in your case, you will be generating minimal graphs satisfying your condition), whose number is more manageable.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Okay, so I need to generate triangle-free graphs and for all of these count combination of complements these graphs? How I can make that for expamle when n=3? (Answer is 7) $\endgroup$ – Sango Feb 19 '18 at 21:49
  • $\begingroup$ Use a software package such as nauty. $\endgroup$ – Yuval Filmus Feb 19 '18 at 21:57
  • $\begingroup$ I cannot use that because of my software, is there any way to generate all possible triangle-free graphs with n vertices? (the best in C++) $\endgroup$ – Sango Feb 19 '18 at 22:11
  • $\begingroup$ I just pointed out a way: use nauty. You can use it both as a standalone program and as a library. $\endgroup$ – Yuval Filmus Feb 19 '18 at 22:15
  • $\begingroup$ Yes, of course but I need to write an algorithm in C++ without any additionally libraries or something like that $\endgroup$ – Sango Feb 19 '18 at 22:19

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.