1
$\begingroup$

A simple graph is a minimal graph with radius and diameter of 2 if its radius and diameter are 2, and removing any edge would increase its diameter. The question is how many such unlabelled graphs on $n$ vertices are there.

I was trying to simplify the task by assuming that all such graphs contain a Hamiltonian cycle. But I am not sure if it is true either.

Is it possible to compute in time polynomial on $n$?

Improve this question
$\endgroup$
2
  • $\begingroup$ Such a graph does not necessarily contain a hamiltonian cycle. For example, consider the graph with 5 vertices (from $0$ to $4$) and 6 edges : $01, 02, 03, 14, 24, 34$. $\endgroup$
    – Nathaniel
    Commented Jun 26 at 21:06
  • $\begingroup$ I see. It looks like the graph would contain a cycle of either $n$ or $n-1$ vertices though... $\endgroup$
    – rus9384
    Commented Jun 26 at 21:12

1 Answer 1

Reset to default
0
$\begingroup$

All complete bipartite graphs $G=(U\cup V, E)$ with $|U| \ge |V| > 1$ have radius $= 2$ and diameter $= 2$. Also, notice that removing any edge would increase the radius and diameter. Thus, it is a minimal graph.

So your required number is at least as large as the number of such complete bipartite graphs having $|U| + |V| = n$. This is an integer partitioning problem with the special constraint $|U| \ge |V| > 1$ and can be easily calculated.

Improve this answer
$\endgroup$
3
  • $\begingroup$ A graph $C_5$ is not a complete bipartite graph. $\endgroup$
    – rus9384
    Commented Jun 27 at 6:45
  • $\begingroup$ Also, this integer partitioning is how you count maximal r2d2 graphs: $\sum_{i=2}^{\lfloor n/2\rfloor}p_i(n-i)$. $\endgroup$
    – rus9384
    Commented Jun 27 at 7:28
  • 1
    $\begingroup$ @rus9384, You are right; $C_5$ and other graphs can have radius = 2 and diameter = 2. I have updated the answer. $\endgroup$
    – codeR
    Commented Jun 27 at 9:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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