2
$\begingroup$

I am trying to solve a problem.

$G$ is a graph where eccentricity of vertices $x$ and $y$ is $8$, and rest of the vertices have eccentricity $7$. Also $d(x,y) = 8$. I am trying to make eccentricities of $x$ and $y$ also $7$ by adding a vertex (or two vertices). The old graph must be induced in new graph. I proposed a construction:

Let $w$ be any vertex in $G$ such that $d(y,w) = 3$. Add a new vertex $z$ and make it adjacent to $y$ and $w$.

Is this true that every vertex in this new graph will have eccentricity $7$? For a few examples, I got the desired result. Or is there any other way to construct this(by adding one more vertex)?

PS: As asked by @bof, I tried for a smaller value. Like in the following figure, two vertices have eccentricity three and rest have eccentricity two, I tried to make eccentricity of every as two by adding a new vertex. As required the old graph is induced in new graph.

enter image description here

$\endgroup$
6
  • $\begingroup$ The eccentricity of a graph vertex in a connected graph is the maximum graph distance between and any other vertex of. $\endgroup$
    – monalisa
    Jun 10, 2018 at 15:19
  • $\begingroup$ I have a definition of eccentricity only on trees, what is the definition on graphs, for example if I have $K_4$ how eccentricity of each vertex? $\endgroup$
    – thetha
    Jun 10, 2018 at 21:04
  • $\begingroup$ Since for an arbitrary vertex $x$ in $K_4$, the maximum distance between $x$ and other vertices is one, hence eccentricity is one for every vertex of $K_4$ and hence for every complete graph. See this link will help you. :) tutorialspoint.com/graph_theory/… $\endgroup$
    – monalisa
    Jun 11, 2018 at 3:30
  • $\begingroup$ Are you sure this can be done? Was this given as an exercise? $\endgroup$
    – bof
    Jun 11, 2018 at 7:39
  • $\begingroup$ Yeah, it is an exercise. Prove or disprove type. $\endgroup$
    – monalisa
    Jun 11, 2018 at 8:20

1 Answer 1

Reset to default
2
+50
$\begingroup$

It is not necessarily true that the eccentricity of every vertex in the new graph is exactly $7$.

In the graph below, the eccentricity of $z$ is $6$.

$\endgroup$
3
  • $\begingroup$ Thanks for providing a counter example. It was a headache to disprove. :) So, is there any other way of constructing such graph? $\endgroup$
    – monalisa
    Jun 11, 2018 at 6:00
  • $\begingroup$ @monalisa I'll try to think about it, but it seems quite difficult to find a way to make the eccentricity of each vertex exactly $7$. $\endgroup$
    – Ѕᴀᴀᴅ
    Jun 11, 2018 at 6:03
  • $\begingroup$ Thank you so much for your efforts. I appreciate it. $\endgroup$
    – monalisa
    Jun 11, 2018 at 6:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .