|November 4th, 2016, 09:52 AM||#1|
Joined: Nov 2016
Graph theory - diameter of biconnected graph
I want to calculate a graph diameter (or the bounds for its value) given a few graph properties such as number of vertices, edges or the max. degree.
I'm aware that finding the diameter in a graph involves NP algorithms, but I don't need to find the diameter path, I just need the value of it.
Although Moore bound presents some usefull aspects (it is from the "degree diameter problem" and could be adapted to calculate the diameter), as far as I've read, graphs that strictly follows Moore bound are rare. Plus, in my case I work only with biconnected undirected unweighted graphs, which don't seem to be a very popular kind of graph among degree diameter problem researches.
My question is: is there an expression (equality or inequality) that relates the diameter to number of vertices or number of edges or max. degree in biconnected undirected unweighted graphs? Or is it an open issue?
Thanks in advance!
|November 4th, 2016, 11:16 AM||#2|
Joined: Oct 2016
I think such a closed expression does not exist because there are various different biconnected undirected unweighted graphs with different diameters but with the same number of vertices, edges and max. degree, even. Does that help?
|biconnected, biconnected graph, diameter, graph, graph theory, theory|
|Thread||Thread Starter||Forum||Replies||Last Post|
|Graph Theory / Harary graph||hyenaa||Geometry||0||May 14th, 2015 12:10 PM|
|A graph problem in graph theory!||lubna_mira||Applied Math||0||January 12th, 2014 02:52 PM|
|Graph theory: Linking graph characteristics and minimal cut||avnerg||Applied Math||0||September 18th, 2013 06:03 AM|
|graph theory - social networks and reverting the graph||johnyjj2||Applied Math||0||December 28th, 2010 03:49 PM|
|Graph theory - 4 stroke graph||kec11494||Applied Math||0||December 14th, 2010 07:01 PM|