1
$\begingroup$

I was doing following construction. We know $C_4$ and $C_5$ are $2$-self-centered graphs. When we add a new vertex $x$ and $y$ to $C_4$ and $C_5$, resp, (shown in fig) the new graph contains exactly two vertices with eccentricity three and rest with eccentricity two. I was curious to know if we propose a similar construction where eccentricity of every vertex is three and only one vertex with ecc two, using the same graphs $C_4$ and $C_5$. By adding one or two vertices such that resultant graphs contain $C_4$ and $C_5$ and as induced subgraphs. Any hint will be appreciated. Thanks a lot.

Note : A self-centered graph is a graph where eccentricity of every vertex is the same.

enter image description here

$\endgroup$
6
  • $\begingroup$ What makes a vertex eccentrjc? $\endgroup$
    – William Elliot
    Mar 31, 2018 at 8:05
  • $\begingroup$ The maximum distance between a vertex to all other vertices is considered as the eccentricity of vertex. The distance from a particular vertex to all other vertices in the graph is taken and among those distances, the eccentricity is the highest of distances $\endgroup$
    – monalisa
    Mar 31, 2018 at 10:15
  • $\begingroup$ Are there selfcentered graphs that are not circuits? $\endgroup$
    – William Elliot
    Mar 31, 2018 at 10:31
  • $\begingroup$ complete graphs, cartesian product of self centered graphs are some examples. $\endgroup$
    – monalisa
    Mar 31, 2018 at 10:57
  • $\begingroup$ The addition of edges cannot increase eccentricities. $\endgroup$
    – Bob Krueger
    Mar 31, 2018 at 16:49

1 Answer 1

Reset to default
1
+50
$\begingroup$

We seek a graph $G$ with the desired eccentricities and containing $C_5$ as an induced subgraph. Start with the induced $C_5$ subgraph and add one vertex. Clearly, $G$ must be connected, and there is only one way to add an edge to connect the new vertex, up to isomorphism. $C_5$ plus one connected vertex

The vertices of eccentricity $2$ are circled. Because additional edges cannot decrease eccentricity and the graph has too many vertices of eccentricity $2$, the single extra vertex is insufficient. Add a second vertex. We again add an edge for connectivity, and there are four non-isomorphic ways to do so.

$C_5$ plus two connected vertices, #1 $C_5$ plus two connected vertices, #2 $C_5$ plus two connected vertices, #3 $C_5$ plus two connected vertices, #4

With reasoning similar to before, the top two graphs will not suffice. The bottom two graphs have vertices with eccentricity $4$, so additional edges are necessary, but it can be checked that no edge may be added (keeping the $C_5$ induced) without creating an additional vertex with eccentricity $2$, so neither graph suffices. Therefore, at least $3$ additional vertices are necessary.

Below left is a graph with $C_5$ as an induced subgraph and $3$ added vertices such that the circled vertex has eccentricity $2$ and every other vertex has eccentricity $3$, satisfying the desired properties. In a similar way, it can be shown that $3$ vertices must be added to $C_4$ to satisfy the desired properties, and the graph below right shows that $3$ suffice.

satisfying graph with $3$ vertices added to $C_5$ satisfying graph with $3$ vertices added to $C_4$

$\endgroup$
3
  • $\begingroup$ Can we do the same for the graph $C_6$? I tried using this scheme by adding three vertices. But I am getting all vertices with eccentricity four and three with eccentricity 3. I want only one vertex with ecc 3 and rest with ecc 4. It is like some kind of generalisation. I will be thankful to you a lot. $\endgroup$
    – monalisa
    Apr 3, 2018 at 4:46
  • 1
    $\begingroup$ A similar construction works in that case, but $5$ added vertices are necessary. $\endgroup$
    – noedne
    Apr 3, 2018 at 18:40
  • $\begingroup$ Thank you so much for your help. Your answer really helped me a lot. Amazing details with clear construction. $\endgroup$
    – monalisa
    Apr 4, 2018 at 5:49

You must log in to answer this question.

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