3
$\begingroup$

I was trying to construct a graph $G_1$ and $G_2$, wherein both graphs $P_4$ is an induced graph. Graph $G_1$ is such that it contains exactly one vertex of eccentricity two and rest of the vertices with eccentricity three. Similarly, the graph $G_2$ is such that it contains exactly one vertex of eccentricity three and the rest of the vertices with eccentricity four. In both the cases, $P_4$ is induced in $G_1$ and $G_2$.

I tried in the following manner.

For $G_1$, I added $6$ vertices to $P_4$ and got the result, and for $G_2$, I added $10$ vertices to $P_4$ and got the result. However, later I got that $G_1$ can be obtained with the fewer number of vertices. Can $G_2$ be also obtained by adding less than $10$ vertices, if possible? Kindly help me to get the graph. Any hint or suggestion is helpful.

My attempt : (numbers are the eccentricity of the vertices)

enter image description here

enter image description here

Graph $G_1$ with less number of vertices:

enter image description here

P.S.

For $G_2$, I also got an example. consider $C_6$ with vertices $1,2,3,4,5,6$. Add $5$ vertices $1′,2′,3′,4′,5′$ and make edges $1′2′,2′3′,3′4′,4′5′$, and $xx′$, where $x=1,2,3,4,5$. This also gives a graph with exactly one vertex with eccentricity $3$ and rest with $4$. The total number of vertices is $11$. Can we think of a smaller order? I am wondering that.

$\endgroup$
2
  • $\begingroup$ Where does this problem come from, and why the constraint that $P_4$ must be an induced graph? It seems to me that the eccentricity constraints are much tougher (and would already make a great puzzle without adding the $P_4$ requirement). $\endgroup$
    – antkam
    Commented Mar 29, 2019 at 19:11
  • $\begingroup$ @antkam An assignment problem by the professor. $\endgroup$
    – monalisa
    Commented Mar 29, 2019 at 19:32

1 Answer 1

1
+50
$\begingroup$

HINT only (for now).

Your $G_2$ has $14$ nodes. I found one with only $11$ nodes. You said "Any hint or suggestion is helpful" so perhaps you prefer just hints so that you can enjoy finding it yourself? :) Anyway if these hints are not enough feel free to ask again.

Inspired by the smaller $G_1$ solution...

  • Lets start with an outer ring. To achieve a "base" eccentricity of $4$, the ring has $8$ nodes, i.e. opposite nodes have distance $4$. (Analogous to the smaller $G_1$ having an outer ring of $6$ nodes to achieve a "base" eccentricity of $3$.)

  • Lets add a center node $C$, and lets "attach" $C$ to the ring at $3$ nodes $X,Y,Z$. We eventually want $C$ to have the lower eccentricity $3$, so intuitively you want to "space out" $X,Y,Z$ around the ring.

  • If we "attach" using edges $(C,X), (C,Y), (C,Z)$ then $C$ will have eccentricity $2$. So some of the attachments must be multi-hop path(s), e.g. $(C,A), (A,X)$ would make a $2$-hop path from $C$ to $X$. This of course adds an "extra" internal node $A$.

  • [Hand crafting time] Can you find a way to use as few of these "extra" nodes as possible? I found a way to use only $2$ of them, for a total of $8 + 1 + 2 = 11$ nodes, while maintaining $C$'s eccentricity at $3$ and everyone else's at $4$.

No idea if $11$ is the fewest nodes possible.

Incidentally, note that $P_4$ being induced was not part of the consideration. In a sense having an induced $P_4$ is "easy" to satisfy, so I worried about the eccentricity constraints first and the final graph does have an induced $P_4$ (many, many such subgraphs).

UPDATE

Here is my $11$-node solution. The outer square is the ring of $8$ nodes and the center node has eccentricity $3$. My labeling also shows this is the same as the OP's example minus two edges ($22'$ and $44'$).

6-----1-----1'
|     |     |
|     2     |
|     |     |
5--4--3     2'
|      \    |
|       \   |
|        \  |
|         \ |
|          \|
5'----4'----3'
$\endgroup$
7
  • $\begingroup$ For $G_2$, I also got an example. consider $C_6$ with vertices $1,2,3,4,5,6$. Add 5 vertices $1',2',3',4',5'$ and make edges $1'2',2'3', 3'4',4'5',$ and $xx'$ where $x=1,2,3,4,5$. This also gives a graph with exactly one vertex with eccentricity $3$ and rest with $4$. Number of vertices is $11$. Can we think of smaller order? I am wondering that. $\endgroup$
    – monalisa
    Commented Mar 29, 2019 at 4:50
  • 1
    $\begingroup$ @monalisa - very interesting! that is dramatically different from my example, and still the same no. of nodes $11$... $\endgroup$
    – antkam
    Commented Mar 29, 2019 at 12:40
  • $\begingroup$ yeah :) Just trying for a fewer number of nodes, if possible. $\endgroup$
    – monalisa
    Commented Mar 29, 2019 at 12:41
  • $\begingroup$ in your example, you only need edges $xx'$ for $x = 1, 3, 5$. this of course doesn't change the number of nodes. also i found another neat solution, but with $15$ nodes: the $4$-dimensional hypercube with any one vertex deleted. $\endgroup$
    – antkam
    Commented Apr 2, 2019 at 18:17
  • 1
    $\begingroup$ no, thank YOU for the problem! :) i found it a lot of fun and it's something i can think about in my spare time. BTW i just realized that your example, when modified to have edges $xx'$ only for $x=1,3,5$, is actually the same as my example. $\endgroup$
    – antkam
    Commented Apr 3, 2019 at 22:01

You must log in to answer this question.

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