I was doing the following problem.

Let * denote a graph operation, where $G=G_1\ast G_2\ldots\ast G_n$ with the vertex set $V(G) = \{(x_1,\ldots,x_n) : x_i\in V(G_i)\}$ and adjacency in operation is defined as:

If $(x_1,x_2,\ldots,x_n)$ and $(y_1,y_2,\ldots, y_n)$ are in V(G), then they are adjacent if $x_i \sim y_i$ for some $i\in \{1,2,\ldots,n\}$.

I am doing a particular case to find when every $G_i$ contains a vertex $g_i$ such that $deg(g_i)=n_i - 1$, where $|V(G_i)|=n_i$.

Here is my attempt:

We will get a vertex $x=(g_1,\ldots,g_n)$ such that $x$ is adjacent to all vertices in $G$, thus eccentricity of $x$ is 1, i.e., ecc(x) = 1. Now for other type of vertices if for some $i\in \{1,2,\ldots,n\}$, $x_i \sim y_i$ then $d(x,y)=1$ follows from the definition of operation "*". If $x_i \nsim y_i$, $\forall $i, $1\leq i\leq n$, then consider a vertex $z=(z_1,z_2,\ldots,z_n) \in V(G)$ such that $x_1 \sim z_1$ and $y_2 \sim z_2$ and thus distance is two in this case and thus eccentricity of all other vertices is 2. So, only vertex with ecc 1 and all other vertices have ecc 2.

Am I missing any vertex? Is my way to proceed correct? If not then please give hint or suggestions where I am going wrong. Thanks.


1 Answer 1


Most of it is correct: every vertex of $G$ has eccentricity $1$ or $2$. However, it’s not true that there is one vertex with eccentricity $1$, and all other vertices have eccentricity $2$. If $n=2$, and $G_1$ and $G_2$ are disjoint copies of $K_2$, then $G=G_1*G_2$ is isomorphic to $K_4$, and every vertex has eccentricity $1$.

  • $\begingroup$ Means ecc will be two for other vertices if we put one more conditon that at least one $G_i$ is not a complete graph. Am I right sir? $\endgroup$
    – monalisa
    Commented Dec 19, 2013 at 5:10
  • $\begingroup$ @monalisa: Yes, it will be $2$ for some of the other vertices, but not necessarily for all of them. If $x_1\not\sim y_1$ in $G_1$, say, let $x=\langle x_1,g_2,\ldots,g_n\rangle$ and $y=\langle y_1,g_2,\ldots,g_n\rangle$; then $d(x,y)=2$. If I’ve made no mistake, $P_3*K_2$ has two vertices of ecc. $1$ and $4$ of ecc. $2$. $\endgroup$ Commented Dec 19, 2013 at 5:17
  • $\begingroup$ yes, sir, you are right. Is there any condition that we impose such that only one vertex has ecc 1 and all other have ecc 2. $\endgroup$
    – monalisa
    Commented Dec 19, 2013 at 5:41
  • $\begingroup$ @monalisa: You’ll get that if you require that each $G_k$ have just one vertex, $g_k$ of degree $n_k-1$. If $y\in G$, and $y\ne\langle g_1,\ldots,g_n\rangle$, there is a $k$ such that $y_k\ne g_k$, and there is a vertex $x_k$ in $G_k$ such that $x_k\not\sim y_k$. Let $x_i=y_i$ for $i\ne k$; then $d(x,y)=2$. If some $G_k$ has two vertices of degree $n_k-1$, $G$ will have at least two vertices of eccentricity $1$. $\endgroup$ Commented Dec 19, 2013 at 5:54
  • $\begingroup$ Oh.... sorry sir.. yes...you are right. If we consider exactly one vertex in every $G_i$ of degree $n_i - 1$, then its possible. thanks a lot :) $\endgroup$
    – monalisa
    Commented Dec 19, 2013 at 5:57

You must log in to answer this question.

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