
Number Theory Number Theory Math Forum 
 LinkBack  Thread Tools  Display Modes 
November 4th, 2016, 10:52 AM  #1 
Newbie Joined: Nov 2016 From: Brazil Posts: 2 Thanks: 0  Graph theory  diameter of biconnected graph
Hello everyone, 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, 12:16 PM  #2 
Newbie Joined: Oct 2016 From: Europe Posts: 11 Thanks: 5 
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?

November 4th, 2016, 02:05 PM  #3 
Newbie Joined: Nov 2016 From: Brazil Posts: 2 Thanks: 0 
Well, an equation seems unreal, but I was hoping an inequation that gives lower ou upper bounds...


Tags 
biconnected, biconnected graph, diameter, graph, graph theory, theory 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Graph Theory / Harary graph  hyenaa  Geometry  0  May 14th, 2015 01: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 07: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 