Invariants of Bipartite Kneser B type-k graphs

Every vertex of $H_{B}(n,k)$ is a set formed using the elements of $\mathscr{B}_{n}$. Here $\mathscr{B}_{n}=\{\pm a_{1},\pm a_{2},\pm a_{3},\dots,\pm a_{n-1},a_{n}\},\text{where },a_{1}<a_{2}\dots<a_{n}\;\text{and}\;-a_{n}\notin\mathscr{B}_{n}.$ $H_{B}(n,k)$ has vertices as subsets of cardinality $1$ to $n$. $|V(G)|$ is the total number of sets of cardinality $1$ to $n$.
Let $N_{i}$ be the number of subsets of $\mathscr{B}_{n}$ of cardinality $i$, where $1\leq i\leq n$.
$N_{1}=1\binom{n}{1}=2^{0}\binom{n}{1},N_{2}=2\binom{n}{2},N_{3}=2^{2}\binom{n}{3},\dotsc,N_{n}=2^{n-1}\binom{n}{n}$.
Thus, $|V(G)|=\sum\limits_{i=1}^{n}N_{i}=2^{0}\binom{n}{1}+2\binom{n}{2}+2^{2}\binom{n}{3}+\dotsb 2^{n-1}\binom{n}{n}=\dfrac{3^{n}-1}{2}$, by binomial theorem. ∎

By the construction of $H_{B}(n,k)=V_{1}\cup V_{2}$, $|V_{2}|$ forms a maximum independent set and $|V_{2}|=|\phi(\mathscr{B}_{n})|-\binom{n}{k}$.
Therefore, $\alpha(G)=\sum\limits_{i=1}^{n}2^{i-1}\binom{n}{i}-\binom{n}{k}$. ∎

As $\alpha(G)+\beta(G)=|G|$, we get $\beta(G)=\binom{n}{k}$. ∎

In $H_{B}(n,k)$, no two vertices in $V_{1}$ are adjacent, and every vertex in it is adjacent to some other vertex in $V_{2}$. Thus, $V_{1}$ forms a dominating set for $H_{B}(n,k)$.
$V_{1}$, being the smallest dominating set,we get $\gamma(H_{B}(n,k))=\binom{n}{k}$, for all $n\geq 2$. ∎

Let $u$ be a $k$-vertex in $V_{1}$.
The number of $1$-vertices in $V_{2}$ adjacent to $u$ is $2^{0}\binom{k}{1}$.
The number of $2$-vertices in $V_{2}$ adjacent to $u$ is $2^{1}\binom{k}{2}$.
The number of $3$-vertices in $V_{2}$ adjacent to $u$ is $2^{2}\binom{k}{3}$.
⋮
The number of $k$-vertices in $V_{2}$ adjacent to $u$ is $2^{k-1}\binom{k}{k}-1$.
The number of $k+1$-vertices in $V_{2}$ adjacent to $u$ is $2^{k}\binom{n-k}{1}$.
The number of $k+2$-vertices in $V_{2}$ adjacent to $u$ is $2^{k+1}\binom{n-k}{2}$.
⋮
The number of $n$-vertices in $V_{2}$ adjacent to $u$ is $2^{n-1}\binom{n-k}{n-k}$.
The degree of $u$,

Since every vertex in $V_{1}$ is of the same degree and $d(u)$ is the maximum, we get, $|E(G)|=\binom{n}{k}\left(\dfrac{3^{k}-3}{2}+2^{k-1}(3^{n-k}-1)\right)$.

∎

As every $k$-vertex, $v$ in $V_{2}$, is of degree $1$, when a $k$-vertex $u$ in $V_{1}$ adjacent to $v$ is removed, $v$ becomes isolated. Accordingly, we get $\kappa(G)=1$. ∎

Let $v$ be any $k$-vertex in $V_{2}$. Since $d(v)=1$, the graph becomes disconnected when the only edge adjacent to it is removed. Consequently, we get $\lambda(G)=1$. ∎

Let $u$ be a $k$-vertex in $V_{1}$. Then, $u$ is adjacent to a $1$-vertex $x$ in $V_{2}$, and $x$ is adjacent to another $k$-vertex $y$ in $V_{1}$. The vertex $y$ is adjacent to an $n$-vertex $v$ in $V_{2}$ and $v$ is adjacent to $u$. Thus, there is a cycle $u-x-y-v-u$ of length $4$. Since any cycle in a bipartite graph is of even length, eventually, we get Girth(G)=4.

∎

The circuit rank, which is also called the cyclomatic number of a graph, is $n-m+c$, where n, m, and c are the order, size, and the number of connected components, respectively. As $c=1$ and n and m are already determined for $H_{B}(n,k)$, the result follows. ∎

Let $d_{V_{2}}(r)$, where $r=1,2,3,\dotsc,k-1,k+1,\dotsc,n$, denote the degrees of $r$-vertices in $V_{2}$, and $d_{V_{1}}(k)$ denote the degree of any $k$-vertex in $V_{1}$. Let the multiplicities of degrees of any $k$-vertex in $V_{1}$, and $r$-vertices in $V_{2}$ be denoted by $N_{V_{1}}(k)$ and  $N_{V_{2}}(r)$ respectively.

We have, $d_{V_{2}}(1)=\binom{n-1}{k-1},\;N_{V_{2}}(1)=2^{0}\binom{n}{1}$, $d_{V_{2}}(2)=\binom{n-2}{k-2},\;N_{V_{2}}(2)=2^{1}\binom{n}{2}$, $d_{V_{2}}(k-1)=\binom{n-(k-1)}{k-(k-1)},\;N_{V_{2}}(k-1)=2^{k-2}\binom{n}{k-1}$, $d_{V_{2}}(k+1)=\binom{k+1}{k},\;N_{V_{2}}(k+1)=2^{k}\binom{n}{k+1}$, $\cdots$, $d_{V_{2}}(n)=\binom{n}{k}$, and $N_{V_{2}}(n)=2^{n-1}\binom{n}{n}$.

Let $u$ be any $k$-vertex in $V_{1}$. For $s=1,2,3,\dotsc,k-1$, the number of $s$-vertices adjacent to $u$ is $2^{s-1}\binom{k}{s}$. The number of $k$-vertices adjacent to $u$ is $2^{k-1}\binom{k}{k}-1$. For $s=k+1,k+2,\dotsc,n$, the number of $s$-vertices adjacent to $u$ is $2^{s-1}\binom{n-k}{t}$. Here, $t=1,2,\dotsc,n-k$. Hence, the degree of any $k$-vertex,which is denoted as $u$, in $V_{1}$ is $d_{V_{1}}(k)=2^{0}\binom{k}{1}+2^{1}\binom{k}{2}+\dotsb+2^{k-1}\binom{k}{k}-1+2^{k}\binom{n-k}{1}+2^{k+1}\binom{n-k}{2}+\dotsb+2^{n-1}\binom{n-k}{n-k}$.

The number of $k$-vertices in $V_{1}$ is $N_{V_{1}}(k)=\binom{n}{k}$. Every $k$-vertex in $V_{2}$ has degree $d_{V_{2}}(k)=1$. Then, the number of $k$-vertices in $V_{2}$ is $N_{V_{2}}(k)=(2^{k-1}-1)\binom{n}{k}$. Thus, the degree of every vertex in $H_{B}(n,k)$ and the number of vertices having a specific degree are determined. The degree sequence is obtained by arranging the sequence, $\Big{\{}d_{V_{2}}(1)^{N_{V_{2}}(1)},d_{V_{2}}(2)^{N_{V_{2}}(2)}\dots,d_{V_{2}}(k-1)^{N_{V_{2}}(k-1)},d_{V_{1}}(k)^{N_{V_{1}}(k)},d_{V_{2}}(k)^{N_{V_{2}}(k)}$, $d_{V_{2}}(k+1)^{N_{V_{2}}(k+1)},\dots d_{V_{2}}(n)^{N_{V_{2}}(n)}\Big{\}}$ of degrees with corresponding multiplicities as a monotonic non-increasing sequence. ∎

By the definition of Omega invariant, we have

∎

It follows by the formula of $r$ given in Eqn.(4.2). ∎

Let $u\in V_{1}$ and $v\in V_{2}$. If $u$ and $v$ are adjacent, then $d(u,v)=1$. Suppose that $v$ is not adjacent to $u$. Since the degree of $v$ is at least $1$, it must be adjacent to some vertex $w\in V_{1}$. Let $x$ be an $n$-vertex in $V_{2}$. As $x$ is a common neighbour of $u$ and $w$, $u-x-w-v$ is the shortest path from $u$ to $v$, and hence $d(u,v)=3$. Let $u,v\in V_{1}$. As any $n$-vertex $x$ is a common neighbour of $u$ and $v$, $u-x-v$ is the shortest path from $u$ to $v$, and hence $d(u,v)=2$. Let $u,v\in V_{2}$. Then, $d(u,v)=2$ in one of the following three cases.

Case 1:

There exists $x\in V_{1}$ such that $x$ is a superset of both $u^{\dagger}$ and $v^{\dagger}$.

Case 2:

There exists $y\in V_{1}$ such that $y$ is a subset of both $u^{\dagger}$ and $v^{\dagger}$ .

Case 3:

There exists $w\in V_{1}$ such that $w$ is a subset of $u^{\dagger}$ and a
          super set of $v^{\dagger}$ or $w$ is a subset of $v^{\dagger}$ and a superset of $u^{\dagger}$ .

In other words, $d(u,v)=2$ if either $|u^{\dagger}\cup v^{\dagger}|\leq k$ or $|u^{\dagger}\cap v^{\dagger}|\geq k$ or $|u^{\dagger}\cap v^{\dagger}|=|u^{\dagger}|\leq k$. If none of these three conditions are satisfied, then $d(u,v)\neq 2$. Choose $x,y\in V_{1}$ such that $d(x,u)=1$ and $d(y,v)=1$. Let $w$ be any $n$-vertex in $V_{2}$. Then $w$ is a common neighbour of $x$ and $y$. Thus, we get the shortest path $u-x-w-y-v$ of length $4$ and hence $d(u,v)=4$. ∎

Let $v\in V_{1}$. For any $u\in V_{1}$, $d(v,u)=2$. If $w\in V_{2}$ such that it is adjacent to $v$, then $d(v,w)=2$. If $w$ is not adjacent to $v$, then $d(v,w)=3$. Thus, $e(v)=3$. Let $v\in V_{2}$ be an $n$-vertex. Since $v$ is adjacent to all vertices in $V_{1}$ and $d(v,u)=2$ for any $u\in V_{2}$, we get $e(v)=2$. Let $v\in V_{2}$ be an $r$-vertex, $1\leq r<n$. The distance from $v$ to any vertex in $V_{1}$ is either $1$ or $3$, and the distance from $v$ to any vertex in $V_{2}$ is either $2$ or $3$.

∎

$\text{diam}(G)=\text{max}\{e(v):v\in V\}=\text{max}\{2,3,4\}=4$.

$\text{rad}(G)=\text{min}\{e(v):v\in V\}=\text{min}\{2,3,4\}=2$. ∎

As the eccentricity of any $r$-vertex $v$, where $1\leq r<n$ is $e(v)=4=\text{diam}(G)$, we get, $\text{Periphery},P(G)=\{v\in V_{2}| v\;\text{is an r-vertex},1\leq r<n\}$ As the eccentricity of any $n$-vertex $v$ is $e(v)=2=\text{rad}(G)$, we get, $\text{Center},C(G)=\{v\in V_{2}| v\;\text{is an n-vertex}\}$.

For finding the median($G$), we find the status of vertices in $V$. We have the status of any vertex $v\in G$,  $s(v)=\sum\limits_{u\in V(G)}d(v,u)$. First, we find the status of any $n$-vertex $v$ in $V_{2}$. The sum of the distances from $v$ to $\binom{n}{k}$ vertices in $V_{1}$ is $\binom{n}{k}$.  The sum of the distance from $v$ to $\frac{3^{n}-1}{2}-\binom{n}{k}-2^{n-1}$, $r$-vertices, where $1\leq r<n$ in $V_{2}$  is  $2\left(\frac{3^{n}-1}{2}-\binom{n}{k}-2^{n-1}\right)$. Therefore, status of $v$ is $2\left(\frac{3^{n}-1}{2}-\binom{n}{k}-2^{n-1}\right)+\binom{n}{k}$. There are vertices at distances $1,2,$ and $3$ from vertices in $V_{1}$. There are vertices at distances $1,2,3$, and $4$ from  $r$-vertices in $V_{2}$. This leads to the conclusion that the status of any $n$-vertex is minimum compared to other vertices in $V$. Thus, Median, $M(G)$=$C(G)=\{v\in V_{2}|\text{ v is an n-vertex}\}.$

∎