1
$\begingroup$

All the definition and results which I am using here has been taken from the Garry Chartrand book $\textbf{The Introduction of Graph Theory}$ and the paper $\textbf{On the Commuting Graph of Dihedral Group}$. Here I am denoting the set N$(v)$ is the collection of all vertices which are adjacent to $v$ in a simple graph $\Gamma$ and the symbol $u \sim v$ means $u$ and $v$ are adjacent.

  • A vertex $v$ in a graph $\Gamma$ is a $\textbf{boundary vertex}$ of a vertex $u$ if $d(u, w) \leq d(u, v)$ for $w \in$N$(v)$, while a vertex $v$ is a boundary vertex of a graph $\Gamma$ if $v$ is a boundary vertex of some vertex of $\Gamma$.

  • A vertex $v$ is said to be a $\textbf{complete vertex}$ if the subgraph induced by the neighbors of $v$ is complete.

  • A vertex $v$ is said to be an $\textbf{interior vertex}$ of a graph $\Gamma$ if for each $u \ne v$, there exists a vertex $w$ and a path $u-w$ such that $v$ lies in that path at the same distance from both $u$ and $w$. A subgraph induced by the interior vertices of $\Gamma$ is called \emph{interior} of $\Gamma$ and it is denoted by $Int(\Gamma)$.

The following results are on the page of 337 and 339 of the above book.

Let $\Gamma$ be a connected graph and $v \in V(\Gamma)$. Then $v$ is a complete vertex of $\Gamma$ if and only if $v$ is a boundary vertex of $x$ for all $x \in V(\Gamma) \setminus \{v\}$.

Let $\Gamma$ be a connected graph and $v \in V(\Gamma)$. Then $v$ is a boundary vertex of $\Gamma$ if and only if $v$ is not an interior vertex of $\Gamma$.

If $\Gamma$ is a complete graph of size $n$ and $v \in V(\Gamma)$, then by the definition of complete vertex, $v$ is a complete vertex. By using the above two results, $v$ is not an interior vertex.

when I am applying the definition of an interior vertex, for each $u \ne v \in V(\Gamma)$ and chose $w \in V(\Gamma) \setminus \{u, v\}$, we have a path $u \sim v \sim w$. Thus, $v$ is an interior vertex.

I am a little bit confused so please help me where I am doing wrong. I would be thankful for your kind help.

$\endgroup$
2
$\begingroup$

I suspect the issue is with the definition of interior you are using. This should say that $v$ is an interior vertex of $\Gamma$ if for each $u\neq v$, there exists a vertex $w$ and a $u-w$ geodesic containing $v$.

With this definition, the path $u\sim v\sim w$ in $K_n$ does not cause any problems, because it is not a geodesic (the single edge $u\sim w$ is a shorter path).

$\endgroup$
1
  • $\begingroup$ Thanks, Brandon for your kind help. $\endgroup$
    – Struggler
    Sep 22 '20 at 3:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.