10
$\begingroup$

Let $G$ be a simple undirected graph, $f(v, u)$ be the number of simple paths between $u$ and $v$ in $G$, $f(G) = \max f(v, u)$ over all pairs of vertices $v, u \in G$.

A recent IOI problem utilized the fact that there is no graph with $f(G) = 3$. Are there any other values of $k \geq 1$ such that no graph with $f(G) = k$ exists?

Computationally, all positive $k \neq 3$ not exceeding $50$ have $f(G) = k$ with $G$ having at most $8$ vertices (in fact, only $k = 45$ requires more than $7$).

Improve this question
$\endgroup$
4
  • $\begingroup$ It doesn't look to me like that fact was used in the IOI problem ... from what I understood, their example 3 simply says that there is no way to have 3 simple paths between two vertices in a graph with $|V|=2$. Is your fact about your defined $f(u,v)$ verified? $\endgroup$
    – JimN
    Sep 17, 2020 at 0:06
  • 1
    $\begingroup$ @JimN Yes: if $f(v, u) = 3$, we can always find $v', u'$ such that $f(v', u') > 3$. Since all prescribed $f(v, u) \leq 3$, then if you see $f(v, u) = 3$, you can immediately determine that no such graph exists. $\endgroup$
    – Mikhail Tikhomirov
    Sep 17, 2020 at 0:13
  • $\begingroup$ I see what you mean now. Used in making a solution to the problem. $\endgroup$
    – JimN
    Sep 17, 2020 at 1:31
  • 2
    $\begingroup$ Any $k=ab;a,b\ge 2$ can be realized as $f(G)$ for a graph $G$ obtained by gluing $K_{2,a}$ and $K_{2,b}$ by a vertex, so the question can be reduced to primes. $\endgroup$
    – Joseph Gordon
    Sep 20, 2020 at 0:09

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.