Finding Degree from neighbor vertex

Question

I have one problem to find the equation of degree from neighbor of vertex. That equation implements to hierarchical product.

This is the definition from degree from neighbor vertex: $$\deg\big(N(v_i)\big)=\sum_{v_k\in N(v_i)}\deg(v_k)$$ where $N(v_i)$ is the set of neighbors of the vertex $v_i$.

Example. We have $K_3$ where each vertex has degree $2$. So $N(v_1)=\{v_2,v_3\}$ and $\deg\big(N(v_i)\big)=4$.

Let $G_1$ and $G_2$ be simple graphs with vertex sets $V_1$ and $V_2$, respectively, having a distinguished or root vertex, labeled $0$. The hierarchical product $H=G_2\sqcap G_1$ is the graph with vertices $x_2x_1$, $x_i\in V_i$, $i=1,2$, and edges defined as follows: $$ x_2x_1\sim\begin{cases}x_2y_1&\text{if }y_1x_1\in E(G_1)\text,\\y_2x_1&\text{if }y_2x_2\in E(G_2)\text{ and }x_1=0\text.\end{cases} $$ Note that the structure of the obtained product graph $H$ heavily depends on the root vertices of the factors $G_1$ and $G_2$.

Answer 1

You are asking for $\text{deg}_H(N(x_2 x_1))$ for $x_1 \in V_1$ and $x_2 \in V_2$.

It suffices to find a general expression for $\text{deg}_H(y_2 y_1)$, since then $$\text{deg}_H(N(x_2 x_1)) = \sum_{y_2 y_1 \in N(x_2 x_1)} \text{deg}_H(y_2 y_1).$$

• If $y_1 \ne 0$, then the neighbors of $y_2 y_1$ are $\{y_2 z_1 : z_1 \in N_{G_1}(y_1)\}$ so $\text{deg}_H(y_2 y_1) = \text{deg}_{G_1}(y_1)$.
• If $y_1 = 0$, then the neighbors of $y_2 y_1$ are $\{y_2 z_1 : z_1 \in N_{G_1}(y_1)\} \sqcup \{z_2 y_1 : z_2 \in N_{G_2}(y_2)\}$ so $\text{deg}_H(y_2 y_1) = \text{deg}_{G_1}(y_1) + \text{deg}_{G_2}(y_2)$.

In short, a simple formula for $\text{deg}_H(y_2 y_1)$ is $\text{deg}_{G_1}(y_1) + \text{deg}_{G_2}(y_2) \cdot \mathbf{1}_{y_1 = 0}$, where $\mathbf{1}_{y_1=0}$ equals one of $y_1 = 0$ and equals zero otherwise.

Can you put everything together to get $\text{deg}_H(N(x_2 x_1))$? I think the answer will be $\text{deg}_{G_1}(N(x_1))$ plus another term.