My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
LinkBack Thread Tools Display Modes
November 4th, 2016, 09: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!
Estevan is offline  
 
November 4th, 2016, 11:16 AM   #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?
Gregor Samsa is offline  
November 4th, 2016, 01: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...
Estevan is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

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 12:10 PM
A graph problem in graph theory! lubna_mira Applied Math 0 January 12th, 2014 01: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 02:49 PM
Graph theory - 4 stroke graph kec11494 Applied Math 0 December 14th, 2010 06:01 PM





Copyright © 2017 My Math Forum. All rights reserved.