1
$\begingroup$

In the following figure I tried to draw a graph from $P_{11}$ (vertex set as $u_1,\ldots,u_{11}$) by adding two vertices(red colored) to $P_{11}$, with exactly two vertices having eccentricity five and rest of the vertices having eccentricity four. I want the resultant graph to an induced subgraph of $P_{11}$.

I almost succeeded but unable to move forward from here. I want eccentricity of $u_1$ and $y$ to be fourKindly help. Thanks a lot for the help.

Note: Eccentricity of vertices is given in numbers.

enter image description here

Is there any other way to make $P_{11}$ as induced subgraph of a graph $G$, Eccentricity of every vertex is four and two vertices have acc 5. $G$ is obtained by adding two vertices to $P_{11}$.

$\endgroup$
3
  • $\begingroup$ You could surely write some code that checks the eccentricity of each vertex in every possible graph formed by adding two vertices to $P_11$ (there are approximately $2^{\binom{13}{2}-10}$ such graphs)? $\endgroup$
    – JRyan
    Jan 8, 2018 at 13:46
  • $\begingroup$ Could you clarify what you mean by "I want the resultant graph to [be?] an induced subgraph of $P_{11}$?" $\endgroup$
    – Fabio Somenzi
    Jan 8, 2018 at 18:14
  • $\begingroup$ @FabioSomenzi ... My original graph is $P_{11}$ and I added two new vertices, red in color. Now I want $P_{11}$ to be an induced subgraph of this final graph (where I added two vertices). $\endgroup$
    – monalisa
    Jan 9, 2018 at 3:13

1 Answer 1

Reset to default
1
$\begingroup$

Since the original question does not contain the definition of eccentricity, recall that the eccentricity of a vertex $v$ in a graph $G$ is the maximum distance between $v$ and any other vertex $u$ of $G$.

The following graph has two vertices with eccentricity 5 (green vertices $u_1$ and $u_{11}$) and the remaining vertices have eccentricity 4. It is constructed by adding two red vertices $u_{12}$ and $u_{13}$ to a path of length 11. Deleting $u_{12}$ and $u_{13}$ recovers the path of length 11, and thus the path of length 11 is an induced subgraph. Each vertex is labeled with its name $u_i$ and its eccentricity.

enter image description here

$\endgroup$
1
  • $\begingroup$ Thank you so much, Adam. I appreciate your efforts. $\endgroup$
    – monalisa
    Jan 9, 2018 at 15:38

You must log in to answer this question.

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