Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The eccentricity $ecc(v)$ of $v$ in $G$ is the greatest distance from $v$ to any other node.

The radius $rad(G)$ of $G$ is the value of the smallest eccentricity.

The diameter $diam(G)$ of $G$ is the value of the greatest eccentricity.

The center of $G$ is the set of nodes $v$ such that $ecc(v) = rad(G)$

Find the radius, diameter and center of the graph : http://gyazo.com/69685c4d20adc762e020264ddc3b089f Appreciate as much help as possible.

I tried following an example and still didn't get it, when you count the distance from a node to another, do you count the starting node too or you count the ending node instead. And when you count, do you count the ones above and below or how do you count? :)

share|improve this question

1 Answer 1

The distance is defined as the number of edges on the shortest path between the vertices. For example, adjacent vertices have a distance of $1$.

In your graph, it might be helpful to explicitly enumerate the eccentricity of each vertex. It is not too difficult to eye-ball the eccentricity for each vertex. I have labelled your graph below with the vertex eccentricities

                                             enter image description here

You can see that in this graph, the larger eccentricities occur at the sides of the graph, with the largest (the diameter) being $6$. The smallest eccentricity occurs at the central vertex with an eccentricity of $3$. This is your radius. Your center consists of all the vertices which have eccentricity equal to the radius, in this case $3$. For this graph, there is only a single such vertex, so your center in the single vertex labelled $3$ in the graph.

You can see that the name center really is quite aptly named. The vertices of the center minimizes the maximum distance to any vertex of the graph and in this sense, really are the most central vertices in the graph.

share|improve this answer
    
I have another question,when you need to find the radius and diameter of graphs like $P_2_k$ , $P_2k_+_1$, $C_2_k$ ; $C_2k_+_1$, $K_n$, and $K_m,_n$ is there a formula or how do you do it? –  Max Bummer Nov 19 '12 at 14:11
1  
In general, finding radius, diameter, eccentricity, etc is more or less a computational problem. You're probably better off with a computer algorithm when finding these parameters for larger graphs. For special classes of graphs however, we can describe these quantities exactly. For a path graph $P_n$, the diameter is $n-1$ and the radius is $\frac{n}{2}$ rounded up to the nearest integer. For a cycle graph $C_n$, the radius and the diameter are both $\frac{n}{2}$, rounded down to the nearest integer. –  EuYu Nov 19 '12 at 14:40
    
For the complete graph $K_n$, every pair of vertices are adjacent. So again, the diameter and the radius are both $1$. For the complete bipartite graph $K_{m,n}$, you need two steps to reach any vertex so the radius and the diameter are both $2$. The exception to this is when $m$ or $n$ is $1$. In that case, the single vertex can reach any other vertex in a single step so the radius is reduced to $1$. Notice that in most cases, if there is some sort of symmetry in the graph then the problem becomes a lot easier. –  EuYu Nov 19 '12 at 14:43
    
And for 2k+1 just add one? –  Max Bummer Nov 20 '12 at 11:27
    
I never assumed $n$ to be even or odd. –  EuYu Nov 20 '12 at 13:53

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.