1
$\begingroup$

I considered a graph, path $P_8$ and added two more vertices such that eccentricity of two vertices is three and rest of the vertices have eccentricity four, and $P_8$ is induced in the new graph. I got the following figure, where exactly two vertices (numbered 2 and 7) are central vertices (eccentricity two) and rest are non-central vertices i.e., diametral vertices (eccentricity four) and $P_8$ is induced in this graph.

enter image description here

Is there any way to get the same result for the graph path $P_9$, or other path graphs, by adding exactly two vertices. Any kind of help or suggestion will be highly useful for me. I am thankful in advance for the help.

$\endgroup$
2
  • 1
    $\begingroup$ What exactly is the result that you are looking for? Are you looking to add two vertices to $P_9$ to achieve diameter $4$ and radius $3$? $\endgroup$
    – Joey Kilpatrick
    Nov 6, 2018 at 6:40
  • $\begingroup$ Yeah, You are right, but the condition is that only two vertices should have eccentricity 3 and rest should have eccentricity four. $\endgroup$
    – monalisa
    Nov 6, 2018 at 7:18

2 Answers 2

Reset to default
2
+100
$\begingroup$

I want to note that there is one other graph (and only one up to isomorphism) that meets your conditions on $P_8$:

enter image description here

Here, vertices $7$ and $9$ have eccentricity $3$ and the rest have eccentricity $4$.

I have found $76$ such graphs on $P_9$ though many of these are not unique up to isomorphism. Also, some of the graphs are subgraphs of other such graphs. A couple are listed below.

enter image description here

Above, vertices $1$ and $2$ have eccentricity $3$ and the rest have eccentricity $4$.

enter image description here

Above, vertices $7$ and $10$ have eccentricity $3$ and the rest have eccentricity $4$.

I would be happy to provide more information about the graphs if you want more. Just comment.

$\endgroup$
5
  • 1
    $\begingroup$ Amazing. That is really helpful to me. I am glad that you helped me. Really thanks a lot. $\endgroup$
    – monalisa
    Nov 8, 2018 at 8:30
  • $\begingroup$ How did you manage to get such a large family of graphs? $\endgroup$
    – monalisa
    Nov 8, 2018 at 11:04
  • $\begingroup$ @monalisa I used SageMath to look for graphs that had the required property. My code produced $14$ such non-isomorphic graphs on $P_9$ and $2$ on $P_8$. I would be happy to post a second answer here to classify the $14$ graphs. Just let me know. $\endgroup$
    – Joey Kilpatrick
    Nov 8, 2018 at 21:16
  • $\begingroup$ That would be so helpful to me if you can share them. Once again thanks a lot for your efforts. $\endgroup$
    – monalisa
    Nov 11, 2018 at 8:54
  • $\begingroup$ @monalisa Added another answer. Hope you find it helpful. $\endgroup$
    – Joey Kilpatrick
    Nov 12, 2018 at 1:15
1
$\begingroup$

These are the $15$ graphs (up to isomorphism) with this property on $P_9$.

enter image description here enter image description here enter image description here enter image description here enter image description here enter image description here enter image description here enter image description here

$\endgroup$
1
  • $\begingroup$ A million thanks for this answer. I am grateful to you. Thank you. $\endgroup$
    – monalisa
    Nov 12, 2018 at 5:23

You must log in to answer this question.

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