14
$\begingroup$

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

enter image description here

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? :)

2 Answers 2

17

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.

  • 0
    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?2012-11-19
  • 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.2012-11-19
  • 0
    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.2012-11-19
  • 0
    And for 2k+1 just add one?2012-11-20
  • 1
    I never assumed $n$ to be even or odd.2012-11-20
  • 0
    Well for n to be even or odd, what would it be?For odd/even path graphs,cycle graph, what would the radius and diameter be?2012-11-21
  • 0
    It would be exactly as I said. You can take $n$ to be even _or_ odd. I never made a restriction. All the formulas that I give are valid for both even and odd $n$.2012-11-21
  • 0
    And not rounded to the nearest integer, what would they be instead of $n/2$ ?2012-11-22
  • 0
    In the answer above . the eccentricity of the bottom leftmost node should be 10. as the longest path from source to dest(rightmost bottom) vertex is covered by reading 10 edges. Correct Me if i m wrong2013-04-10
  • 0
    @Fida The **distance** is defined as the _shortest_ path between two vertices.2013-04-10
0

I think for the path graph Pn, the diameter is n−1.But the radius is (n-1/2)rounded up to the nearest integer. For example,P3 it has radius of 1 but not 2.

  • 1
    Welcome to MSE. Please use [MathJax](https://math.meta.stackexchange.com/questions/5020/mathjax-basic-tutorial-and-quick-reference).2018-03-09