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$

1 Answer 1

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
    Commented Sep 22, 2020 at 3:57

You must log in to answer this question.

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