1
$\begingroup$

Hi,

For a given number of edges, the non directed graph which maximises the number of paths of length 2 is the quasi-star or the quasi-complete graph. Does anyone know :

1- what is the non directed graph which maximises the number of paths of length 3 2- same question for length 4 3- same question for length 3 + 4

If you have any hint, thank you very much.

Improve this question
$\endgroup$
4
  • $\begingroup$ Is the number of vertices also given? $\endgroup$
    – Felix Goldberg
    Commented Apr 10, 2012 at 16:21
  • $\begingroup$ yes, sorry I forgot to mention. The number of vertices is also given. But if it helps, consider it can be as large as you wish and you don't need to connect them all. And by the way, I just noticed my mistake: I need the graphs which maximise the number of walks, not paths ! Sorry again $\endgroup$
    – user20638
    Commented Apr 10, 2012 at 18:58
  • $\begingroup$ Just a random note. Let $A$ be the adjacency matrix of your graph. The number of walks of length $k$ between vertices $v_i,v_j$ is given by the $(v_i,v_j)$ entry of $A^k$. Maybe this can help you somehow. $\endgroup$
    – Jernej
    Commented Apr 10, 2012 at 20:40
  • $\begingroup$ yes, I know that. But I don't see how I can use it. $\endgroup$
    – user20638
    Commented Apr 10, 2012 at 20:43

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .