I would like to know if there is an upper bound on the length of the shortest paths between vertices on an undirected and unweighted graph based on degree of vertices, number of vertices and number of edges. I consider the shortest paths. So path length is smaller than the number of vertices. I want to know if I can get a better bound with the information of degrees of vertices.

Specifically I have a graph where degree of each vertex is either 1, 2 or 3.

  • 1
    $\begingroup$ Paths and cycles have low degrees, so I don't think you can get a meaningful bound. $\endgroup$ – Yuval Filmus Mar 1 '16 at 6:26
  • $\begingroup$ I edited the question. I want to consider only the shortest paths between vertices. $\endgroup$ – Ibraheem Moosa Mar 1 '16 at 6:37
  • 1
    $\begingroup$ Same example still works. $\endgroup$ – Yuval Filmus Mar 1 '16 at 6:39
  • $\begingroup$ What do you mean by degrees of paths and cycles? $\endgroup$ – Ibraheem Moosa Mar 1 '16 at 6:49
  • $\begingroup$ I mean that vertices in paths and cycles have very low degrees (1 and 2), as well as only few edges, and yet their diameter is large. $\endgroup$ – Yuval Filmus Mar 1 '16 at 7:37

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.