1
$\begingroup$

I am trying to construct a graph using $K_3$ graph. The graph $G$, obtained by adding vertices to $K_3$, should contain only one vertex with eccentricity two and the rest of the vertices with eccentricity three, and $K_3$ must be induced in $G$.
I can only add three, four or five vertices to $K_3$. I tried many examples but unable to do so. Kindly help. A little help or hint will be of great use to me. Thanks a lot for help.

Similarly, I have to draw a graph $G_1$ using $K_3$ by adding 7, 8 or 9 vertices such that the resultant graph contains only one vertex with eccentricity three and the rest of the vertices with eccentricity four.

My attempt to draw $G_1$ is as follows (but not successful). Vertices in red have eccentricity three and rest of the vertices have eccentricity four.

enter image description here

$\endgroup$
4
  • $\begingroup$ You have changed the question by saying "adding 7,8,9 vertices". I will try to do the second one again. $\endgroup$
    – ArsenBerk
    Commented Aug 26, 2018 at 15:16
  • $\begingroup$ Extremely sorry about that. For the sake of solving it easily, I added the condition. Again very sorry. $\endgroup$
    – monalisa
    Commented Aug 26, 2018 at 17:31
  • $\begingroup$ I tried many things but wasn't able to find a way for your second question :/ $\endgroup$
    – ArsenBerk
    Commented Aug 26, 2018 at 17:58
  • $\begingroup$ Kindly see one more question by me, where I tried the same. Drew Some figure. Here is the link - math.stackexchange.com/questions/2894971/… $\endgroup$
    – monalisa
    Commented Aug 26, 2018 at 18:04

1 Answer 1

4
$\begingroup$

Well, actually I have no idea how can I turn my answer into a hint so I will go step by step. After each step, you can stop reading and think the rest for yourself. I will also write the eccentricities of vertices after each step.

Step 1: First of all, let us construct a graph where every vertex has eccentricity $3$. In order to do that, I consider the $n$-gons, where I started from $n = 5$. In a graph of $5$-gon, each vertex has eccentricity $2$. So I went for $n = 6$, where every vertex has eccentricity $3$. So we can continue from there:

enter image description here

Step 2: Now I thought how can we obtain $K_3$ without creating a vertex with eccentricity $2$ or $4$, i.e., by keeping all the eccentricities $3$. If we draw an edge inside the $6$-gon (a diagonal), then we won't have all the vertices having eccentricity $3$. So I added a new vertex outside as the following and got a $K_3$:

enter image description here

Step 3: Now, notice that all the vertices still has eccentricity $3$. Now we need to decrease one of the vertices' eccentricity by $1$ to have exactly one vertex with eccentricity $2$. At this point, I couldn't find a way of doing it by adding edges. But first I added an edge to have more than one vertices (three) of eccentricity $2$:

enter image description here

Step 4: And the last step. Our purpose here is to make eccentricity of two of the vertices $3$ again without changing the eccentricities of other vertices. Here, I couldn't find a way to do that by adding edges (maybe there is a way but I wasn't able to find it) so again I considered adding a vertex (also notice that with this one, we will have $5$ additional vertices to $K_3$). But while adding this one, I also considered vertices' paths of maximum length. Because I can't add a new vertex to a vertex where a path of length $3$ ends. We also have to add it so that vertices with eccentricity $2$ will have a longer path with length $3$. By considering these, I added the last vertex as the following:

enter image description here

And we are done.

$\endgroup$
4
  • $\begingroup$ Thank you so much for your efforts. I appreciate the detailed answer. $\endgroup$
    – monalisa
    Commented Aug 25, 2018 at 9:14
  • $\begingroup$ Can you help me if I want to draw exactly one vertex with eccentricity three and rest with eccentricity four? Same conditions as before. $\endgroup$
    – monalisa
    Commented Aug 25, 2018 at 10:39
  • 1
    $\begingroup$ Hmm, with at most $8$ vertices, I doubt it can be done but I will try it. $\endgroup$
    – ArsenBerk
    Commented Aug 25, 2018 at 10:54
  • $\begingroup$ Even I am trying using $C_8$ $\endgroup$
    – monalisa
    Commented Aug 25, 2018 at 11:40

You must log in to answer this question.

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