yes, I know that. But I don't see how I can use it.

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

To Alexander Chervov (or anyone else who knows), You say that "If elements are quite small, then sing.vals. will be small, it can be made precise". How can it "be made precise" ? I would be interested to know more (I am not myself mathematician). In my case, the elements of A are all smaller that between -1 and 1. Don't know if it helps... Thank you.

Sorry for being imprecise. I am interested in the largest singular value only. An M-Matrix has mainly two properties : 1- all non diagonal entries are negative 2- all principal minors are positive A sufficient condition to check that a matrix is an M-Matrix is that it can be written (\lambda I - B) for some nonnegative matrix B and some \lambda > p, where p is a maximal eigenvalue of B. A property of an M-Matrix is that all the eigenvalues are positive. I don't know if these properties can help. But yes, I am trying to find conditions to ensure that the largest s.v. is < 1. Thanks,