Note: Vertex stress in generalized Johnson graphs of diameter 2

1. Introduction

For reference reading on the basic notions and notation in graph theory, see [1,2]. Unless mentioned otherwise, all graphs \(G\) will be undirected, simple and connected graphs. For a graph \(G\) the meaning of say, \(deg(v_i)\), \(v_i \in V(G)\) will be assumed to be clear (and similarly for other graph parameters). If a distinction between a vertex \(v_i \in V(G)\) and a vertex \(v_j \in V(H)\) with \(H\) another graph is required, the adoption of the notation \(deg_G(v_i)\) and \(deg_H(v_j)\) will be used (and similarly for other graph parameters). Reference to vertices \(u,v\) (or \(v_i,v_j\)) will mean that \(u\) and \(v\) (or \(v_i\) and \(v_j\)) are distinct vertices.

Recall from [3] that if \(\sigma(v)\) the number of shortest paths between vertices \(u\), \(w\) which contain \(v\) as an internal vertex, then the vertex stress of \(v\) is defined by, \(\mathcal{S}_G(v) = \sum\limits_{u\neq w\neq v}\sigma(v)\). Hence, the vertex stress of vertex \(v\in V(G)\) is the number of times \(v\) is contained as an internal vertex in all shortest paths between all pairs of distinct vertices in \(V(G)\backslash \{v\}\). Such a shortest \(uw\)-path is also called a \(uw\)-distance path. Also see [4]. The total vertex stress of \(G\) is given by \(\mathcal{S}(G) = \sum\limits_{v\in V(G)}\mathcal{S}_G(v)\), [5].

Graphs from either the subsets or the \(t\)-element subsets of a set \(X = \{1,2,3,\dots,n\}\), and subject to various adjacency regimes (or incidence functions) have been widely studied. Consider the set \(X = \{1,2,3,\dots, n\}\) and the vacant parking set, \(Y = \{\underbrace{-,-,-,\dots,-}_{n~positions}\}\). It is known that parking each element of \(X\) in a position in \(Y\) to obtained a parked set can be achieved in \(n!\) ways. From a set theoretical perspective any pair of parked sets is considered to be identical sets. It implies that set theoretical or combinatorial outcomes such as, generating \(t\)-element subsets and determining clusters of intersecting \(t\)-element subsets with intersecting cardinality say, \(s\) and so on, will yield equivalent (or identical) outcomes. It is agreed that such properties together with outcomes stemming from these properties will not be proven from first principles.

Furthering the study of vertex stress related parameters for the families of graphs from sets or set-graphs is motivated by the demonstrable research interest. More so, if it is appreciated how much of the research in machine learning and AI technology finds its foundation in modern graph theory and set theory.

2. Generalized Johnson graphs

Let \(X = \{1,2,3,\dots,n\}\), \(n \geq 2\). Let \(1 \leq t \leq n-1\) and \begin{equation} V(X,t) = \{X_i:i = 1,2,3,\dots,\binom{n}{t}, X_i \  a \  t-element \  subset \  of \  X\}. \end{equation} Recall the definition of generalized Johnson graphs.

Definition 1. For \(0 \leq l \leq t\) define the generalized Johnson graphs, \begin{equation} G(n,t,l) \  with \  V(G(n,t,l)) = \{v_i:v_i \  maps \  to \  X_i \in V(X,t)\} \  and \  E(G(n,t,l)) = \{v_iv_j:|X_i \cap X_j| = l\}. \end{equation}

For a specific \(n\) and \(t\) the integer range of \(l\) yields a family of \((t+1)\) graphs.

Example 1. Let \(n = 6\) i.e. \(X = \{1,2,3,4,5,6\}\) and let \(t = 3\). Therefore, \(0 \leq l \leq 3\) and, \begin{equation} V(X,3) = \big{\{}\{1,2,3\}, \{1,2,4\}, \{1,2,5\}, \{1,2,6\}, \{1,3,4\}, \{1,3,5\}, \{1,3,6\}, \{1,4,5\}, \{1,4,6\}, \{1,5,6\}, \{2,3,4\}, \{2,3,5\}, \{2,3,6\}, \{2,4,5\}, \{2,4,6\}, \{2,5,6\}, \{3,4,5\}, \{3,4,6\}, \{3,5,6\}, \{4,5,6\}\big{\}}. \end{equation} With a left to right read of \(V(X,t)\), let \(v_i \mapsto\) (\(i^{th}\) \(3\)-element subset).

Case 1, \(l = 0\):

\begin{equation} E(G(6,3,0)) =\{v_1v_{20}, v_2v_{19}, v_3v_{18}, v_4v_{17}, v_5v_{16}, v_6v_{15}, v_7v_{14}, v_8v_{13}, v_9v_{12}, v_{10}v_{11}\}. \end{equation}

Case 2, \(l = 1\):

\( E(G(6,3,1)) =\{v_1v_8, v_1v_9, v_1v_{10}, v_1v_{14}, v_1v_{15}, v_1v_{16}, v_1v_{17}, v_1v_{18}, v_1v_{19},v_2v_6, v_2v_7, v_2v_{10}, v_2v_{12}, v_2v_{13}, v_2v_{16}, v_2v_{17}, v_2v_{18}, v_2v_{20}, v_3v_5, v_3v_7, v_3v_9, v_3v_{11}, v_3v_{13}, v_3v_{15}, v_3v_{17},\)

\(v_3v_{19}, v_3v_{20}, v_4v_5, v_4v_6, v_4v_8, v_4v_{11}, v_4v_{12}, v_4v_{14}, v_4v_{18}, v_4v_{19}, v_4v_{20}, v_5v_{10}, v_5v_{12}, v_5v_{13}, v_5v_{14}, v_5v_{15}, v_5v_{19}, v_5v_{20}, v_6v_9, v_6v_{11}, v_6v_{13}, v_6v_{14}, v_6v_{16}, v_6v_{18}, v_6v_{20}, v_7v_8,\)

\( v_7v_{11}, v_7v_{12}, v_7v_{15}, v_7v_{16}, v_7v_{17}, v_7v_{20}, v_8v_{11}, v_8v_{12}, v_8v_{15}, v_8v_{16}, v_8v_{18}, v_8v_{19}, v_9v_{11}, v_9v_{13}, v_9v_{14}, v_9v_{16}, v_9v_{17}, v_9v_{19}, v_{10}v_{12}, v_{10}v_{13}, v_{10}v_{14}, v_{10}v_{15}, v_{10}v_{17},\)

\(v_{10}v_{18}, v_{11}v_{16}, v_{11}v_{19}, v_{11}v_{20}, v_{12}v_{15}, v_{12}v_{18}, v_{12}v_{20}, v_{13}v_{14}, v_{13}v_{17}, v_{13}v_{20}, v_{14}v_{18}, v_{14}v_{19}, v_{15}v_{17}, v_{15}v_{19}, v_{16}v_{17}, v_{16}v_{18}\}. \)

Case 3, \(l = 2\):

\(E(G(6,3,2)) =\) \(\{v_1v_2, v_1v_3, v_1v_4, v_1v_5, v_1v_6, v_1v_7, v_1v_{11}, v_1v_{12}, v_1v_{13},\) \(v_2v_3, v_2v_4, v_2v_5, v_2v_8, v_2v_9, v_2v_{11}, v_2v_{14}, v_2v_{15},\) \(v_3v_6, v_3v_8, v_3v_{10}, v_3v_{12}, v_3v_{14}, v_3v_{16},\)

\(v_4v_7, v_4v_9, v_4v_{10}, v_4v_{13}, v_4v_{15}, v_4v_{16},\) \(v_5v_6, v_5v_7, v_5v_8, v_5v_9, v_5v_{11}, v_5v_{17}, v_5v_{18},\) \(v_6v_7, v_6v_8, v_6v_{10}, v_6v_{12}, v_6v_{17}, v_6v_{19},\) \(v_7v_9, v_7v_{10}, v_7v_{13}, v_7v_{18}, v_7v_{19},\)

\(v_8v_9, v_8v_{10}, v_8v_{14}, v_8v_{17}, v_8v_{20},\) \(v_9v_{10}, v_9v_{15}, v_9v_{18}, v_9v_{20},\) \(v_{10}v_{16}, v_{10}v_{19}, v_{10}v_{20},\) \(v_{11}v_{12}, v_{11}v_{13}, v_{11}v_{14}, v_{11}v_{15}, v_{11}v_{17}, v_{11}v_{18},\)

\(v_{12}v_{13}, v_{12}v_{14}, v_{12}v_{16}, v_{12}v_{17}, v_{12}v_{19},\) \(v_{13}v_{15}, v_{13}v_{16}, v_{13}v_{18}, v_{13}v_{19},\) \(v_{14}v_{15}, v_{14}v_{16}, v_{14}v_{17}, v_{14}v_{20},\) \(v_{15}v_{16}, v_{15}v_{18}, v_{15}v_{20},\)

\(v_{16}v_{19}, v_{16}v_{20},\) \(v_{17}v_{18}, v_{17}v_{19}, v_{17}v_{20},\) \(v_{18}v_{19}, v_{18}v_{20},\) \(v_{19}v_{20}\}.\)

Case 4. \(l = 3\): Clearly, \(E(G(6,3,3)) = \emptyset\). Hence, the graph is the null graph \(\mathfrak{N}_{20}\).

Note that the example serves to illustrate the standard method of generating the \(t\)-element subsets of \(X\) (or the elements of \(V(X,t)\)). Also the labeled vertex mapping is standardized. Suffice to say that the aforesaid standardizations are found in most popular text books as well as, in most algorithmic generators of \(t\)-element subsets. Furthermore, note that for \(\ell = 0\) the generalized Johnson graphs is the family of Kneser graphs. Vertex stress related parameters for Kneser graphs are found in [6]. Henceforth, \(1 \leq \ell < t\). Furthermore, generalized Kneser graphs are defined similar to Definition 1 except that adjacency is defined as,

\(E(G(n,t,l)) = \{v_iv_j:|X_i \cap X_j| \leq l\}\)   as   in   [7,8]   or,

\(E(G(n,t,l)) = \{v_iv_j:|X_i \cap X_j| < l\}\)   as   in   [9,10].

We specifically consider the case of equality. It means that generalized Johnson graphs are under consideration. Furthermore, we restrict the variables of Definition 1 to \(n \geq 4\), \(1 \leq \ell < t \leq \lfloor \frac{n}{2}\rfloor\) to ensure connectedness. Note that our restrictions are tighter than those found in [11] i.e. \(n \geq 2t\) and the ordered triple \((n,t,\ell) \neq (2t,t,0)\). Thus in Example 1 only the graphs yielded in Case 2 and 3 will be considered. We recall useful results from [11].

Theorem 2. [11] For \(G(n,t,\ell)\), \(n \geq 2t\) it follows that: \begin{equation*} diam(G(n,t,\ell)) = \begin{cases} 3, & \mbox{if \(3(t-\ell)-1 \leq n < 3t - 2\ell\)   and   \(\ell \neq 0\)};\\ \lceil \frac{t-\ell -1}{n-2t+2\ell}\rceil + 1, & \mbox{if \(n < 3(t-\ell)-1\)  or   \(\ell = 0\)};\\ \lceil \frac{t}{t-\ell}\rceil, & \mbox{if \(n \geq 3t - 2\ell\)   and   \(\ell \neq 0\).} \end{cases} \end{equation*}

Theorem 3.[11] Let \(v_i\), \(v_i\) be vertices of \(G(n,t,\ell)\), \(n \geq 2t\) and let \(|v_i\cap v_j|=x\). Then: \begin{equation*} d(v_i,v_j) = \begin{cases} 3, & \mbox{if   \(x < min\{\ell, -n+3t-2\ell\}\)};\\ \lceil \frac{t-x}{t-\ell}\rceil, & \mbox{if   \(-n+3t-2\ell \leq x < \ell\)};\\ min\{2\lceil \frac{t-x}{n-2t+2\ell}\rceil,2\lceil \frac{x-\ell}{n-2t+2\ell}\rceil +1\}, & \mbox{if   \(x \geq \ell\).} \end{cases} \end{equation*}

2.1. Number of \(r\)-distance paths

From a set theoretical perspective the application of Definition 1 to any pair of \(t\)-elements subsets yields equivalent outcomes. For example, it means as is known, that \(G(n,t,\ell)\) is degree regular. Recall that \(deg(v_i) = \binom{t}{\ell}\times \binom{n-t}{t-\ell}\). For \(1 \leq \ell \leq t-1\) an important interpretation of the formula for the degree of any vertex \(v_i\) is that the open neighborhood \(N(v_i)\) can be partitioned into \(\binom{t}{\ell}\) subsets (or sub-neighborhoods) denoted by, \(N_{s_i}(v_i)\), \(i = 1,2,3,\dots, \binom{t}{\ell}\) such that, \begin{equation} |v_j \cap v_q| \geq \ell \  with \  v_j, v_q \in N_{s_i}(v_i). \end{equation} Furthermore, \begin{equation} |N_{s_j}(v_i)| = |N_{s_k}(v_i)| = \binom{n-t}{t-\ell}. \end{equation} It follows immediately that, \begin{equation} |N_{s_i}(v_i)| = |N_{s_j}(v_j)|, i,j \in \{1,2,3,\dots, \binom{t}{\ell}\}. \end{equation}

Remark 1. It is agreed that the numbering of \(N_{s_i}(v_i)\) follows the conventional ordering of \(t\)-element subsets as they are generated and belongs to \(N(v_i)\).

Since \(diam(G(n,t,\ell))\) is known, the equivalence of outcome implies that for any pair of vertices \(v_i,v_j\) both vertices has equal number of \(1\)-distance paths (edges), equal number of \(2\)-distance paths and so on, up to the equal number of maximum distance-paths i.e. \(diam(G(n,t,\ell)\)-paths. Hence, by settling a result for vertex \(v_1\), the result is immediately settled for all vertices \(v_k \in V(G(n,t,\ell))\) by the principle of choice without the loss of generality. In the next subsection we investigate a case enumeration in an attempt to find explicit formula (or stepwise formula) for the size of, \(|N(v_1) \cap N(v_j)|\) where \(j\) is the smallest value such that \(v_1\) and \(v_j\) are adjacent.

2.2. Case enumeration

Case 1, \(\ell = t-1\):} By the convention let \(v_1 = \{1,2,3,\dots,t-1,t\}\) and \(v_2 = \{1,2,3,\dots,t-1,t+1\}\). Clearly, all vertices of the form \(N_{s_1}(v_1) = \{1,2,3,\dots,t-1,t+j\}\), \(j=2,3,4,\dots,(n-j)\) are common neighbors to vertices \(v_1, v_2\). Thus, if \(n \geq 3t-2\ell\) a total of

\begin{equation} \binom{n-(2t-\ell)}{t-\ell} \end{equation} common neighbors between \(v_1\) and \(v_2\) exist in \(N_{s_1}(v_1)\). Else, it is zero. Note that the reasoning to obtain the outcome relied inherently on the restriction placed on \(t\) in respect of \(n\) and then specifically that \(\ell = t-1\). Hence, \(n\) may increase arbitrarily large and so may \(t\) in accordance to the restriction between \(t\) and \(n\). This implies that for a fixed \(\ell\) the difference \(t-\ell\) may freely increase or decrease within bounds. Finally, for \(\ell = t-1\) it follows easily that that in each of the other \(\binom{t}{\ell} - 1\) sub-neighborhoods of \(v_1\) there are exactly one common neighbors. Hence, vertices \(v_1\) and \(v_2\) share: \begin{equation} N(v_1) \cap N(v_2) = \big{(}\binom{t}{\ell}-1\big{)} + \binom{n-(2t-\ell)}{t-\ell} \end{equation} common neighbors.

It is straightforward to verify that if \(\ell = 1\) then,

\begin{equation} N(v_j) \cap N_{s_1}(v_1) = \emptyset. \end{equation} Through similar combinatorial reasoning as above and for the values \(1 \leq \ell \leq t-2\), we claim that:

Claim 4. Let \(1 \leq \ell \leq t-1\) and \(2 \leq t \leq \lfloor \frac{n}{2}\rfloor\), then:

\begin{equation*} N_{s_1}(v_1) \cap N(v_j) = \begin{cases} \binom{n-(2t-\ell)}{t-\ell}, & \mbox{if \(n \geq 3t-2\ell\)};\\ 0, & \mbox{otherwise}. \end{cases} \end{equation*}

Proof. The results follow immediately from the symmetry properties of a generalized Johnson graph with straightforward combinatorial manipulation. By the principle of "choice without the loss of generality" immediate mathematical induction applies to generalize in respect of sufficiently large \(t\) and \(n\) both of which remain in accordance to the restrictions.

Claim 5. Let \(1 \leq \ell \leq t-1\) and \(2 \leq t \leq \lfloor \frac{n}{2}\rfloor\) then, for each \(k \in \{2,3,4,\dots,\binom{t}{\ell}\}\): \begin{equation*} N_{s_k}(v_1) \cap N(v_j) = \begin{cases} 1, & \mbox{if \(\ell = t-1\)};\\ \big{(}n-(2t-\ell)\big{)}(t-\ell), & \mbox{otherwise}. \end{cases} \end{equation*}

Proof. The results follow immediately from the symmetry properties of a generalized Johnson graph with straightforward combinatorial manipulation. By the principle of "choice without the loss of generality" immediate mathematical induction applies to generalize in respect of sufficiently large \(t\) and \(n\) both of which remain in accordance to the restrictions.

3. Vertex stress related parameters

Henceforth, generalized Johnson graphs of diameter 2 will be considered. Thus it is required that: \begin{equation*} n \begin{cases} \geq 3t-2\ell,\\ or\\ < 3(t-\ell)-1, \end{cases} \end{equation*} and \(\lceil \frac{t}{2}\rceil \leq \ell \leq t-1\).

The restriction reads together with Theorem 2 above (or Theorem 4.2 in [11]) and Theorem 2.4 in [11] implies that girth of the generalized Johnson graphs under consideration is \(3\). The aforesaid implies that for any vertex \(v_j\in N(v_i)\) there exists a vertex \(v_k \in N(v_i)\) such that \(v_i,v_j,v_k\) induce cycle \(C_3\), (a triangle).

Recall the definition of total induced vertex stress of a vertex in \(G\) from [12].

Definition 6.[12] Let \(V(G)=\{v_i:1\leq i \leq n\}\) and for the ordered vertex pair \((v_i,v_j)\) let there be \(k_G(i,j)\) distinct shortest paths of length \(l_G(i,j)\) from \(v_i\) to \(v_j\). Then, total induced vertex stress of a vertex is given by, \(\mathfrak{s}_{G}(v_i)= \sum\limits_{j=1,j\neq i}^{n}k_G(i,j)(l_G(i,j)-1)\).

Proposition 7. Let \(j\) is the smallest value such that \(v_1\) and \(v_j\) are adjacent. Furthermore, let:

• (i) \(n \geq 3t-2\ell\) and \(\ell = t-1\) and \(\beta(v_j) = \binom{n-(2t-\ell)}{t-\ell} + \binom{t}{\ell}-1\) or,
• (ii) \(n \geq 3t-2\ell\) and \(1 \leq \ell \leq t-2\) and \(\beta(v_j) = \binom{n-(2t-\ell)}{t-\ell} + \big{[}\binom{t}{\ell}-1\big{]}\big{[}n-(2t-\ell)\big{]}(t-\ell)\) or,
• (iii) \(3 \leq n \leq 3t-2\ell-1\) and \(\ell = t-1\) and \(\beta(v_j) = \binom{t}{\ell}-1\) or,
• (iv) \(3 \leq n \leq 3t-2\ell-1\) and \(1 \leq \ell \leq t-2\) and \(\beta(v_j) = \big{[}\binom{t}{\ell}-1\big{]}\big{[}n-(2t-\ell)\big{]}(t-\ell)\).

Let \(\gamma(v_j) = deg(v_j)-\beta(v_j) -1\).

Subject to either (i) or (ii) or (iii) or (iv) the vertex \(v_1 \in V(G(n,t,\ell))\) has induced vertex stress:

\begin{equation} \mathfrak{s}_{G(n,t,\ell)}(v_1) = deg(v_1)\times \gamma(v_j). \end{equation}

Proof. Since \(deg(v_1) = \binom{t}{\ell}\binom{n-t}{t-\ell}\), there exists \(deg(v_1)\) unique \(1\)-paths leading from \(v_1\) of which all contribute \(0\) count to the induced vertex stress of \(v_1\). From vertex \(v_j\) a total of \(\gamma(v_j) = deg(v_j)-\beta(v_j) -1\) edges join at least one or more vertices in \(N(v_j)\backslash N[v_1]\). Hence, via \(v_j\) there exist \(\gamma(v_j)\), \(2\)-paths from \(v_1\) (or \(v_j\) an internal vertex). Obviously, \(\gamma(v_j)=\gamma(v_k) = \gamma(v_l)\) \(\forall~v_k,v_l \in N(v_1)\). Since \(G(n,t,\ell)\) is of diameter \(2\) all distance-paths from \(v_1\) have been accounted for if and only if all vertices in \(N(v_1)\) have been accounted for. Each such \(2\)-path contributes a count of \(1\) to the induced stress of vertex \(v_1\). The number of \(2\)-paths per case is yielded by Claims 4 and 5, respectively. This settles the result.

Theorem 8. Connected generalized Johnson graphs \(G(n,t,\ell)\) have vertex stress related parameters:

• (i) \(\mathfrak{s}_{G(n,t,\ell)}(v_i) = \mathfrak{s}_{G(n,t,\ell)}(v_1)\), \(\forall~v_i\).
• (ii) \(\mathfrak{s}(G(n,t,\ell)) = \binom{n}{t}\mathfrak{s}_{G(n,t,\ell)}(v_i)\).
• (iii) \(\mathcal{S}(G(n,t,\ell)) = \frac{1}{2}\mathfrak{s}(G(n,t,\ell))\).
• (iv) \(\mathcal{S}_{G(n,t,\ell)}(v_i) = \frac{\mathcal{S}(G(n,t,\ell))}{\binom{n}{t}}\), \(\forall~v_i\).

Proof. The results follow immediately from the symmetry properties of a generalized Johnson graph and the principle of "choice without the loss of generality" read together with Definition 6 as well as those applicable in §1.

Corollary 9. Connected generalized Johnson graphs \(G(n,t,\ell)\) are stress regular as defined in [4].

4. Conclusion

The note serves as the foundation to establish the same parameters for generalized Johnson graphs of diameter greater than or equal to \(3\). From §3 it is intuitively evident that meaningful research with regards to generalized Johnson graphs of diameter greater or equal to \(2\) would require a coded algorithmic approach rather than exhaustive methods utilizing explicit formula. Utilize the GeeksforGeeks algorithm\(^1\) [13] to determine the set of all shortest \((v_iv_j)\)-paths for all pairs of vertices. The outcomes yields both the number of shortest paths as well as the respective path descriptions.

Stemming from the notion of hyper graphs, let a set of connected graphs be \(\mathcal{G} = \{G_i: i = 1,2,3,\dots,n\}\) and let \(Y_i = \{\underbrace{G_j,G_k,G_l,\dots,G_q}_{t-entries}\}\), \(1 \leq t \leq n-1\), \(i = 1,2,3,\dots,\binom{n}{t}\) be the \(t\)-element subsets of \(\mathcal{G}\). If \(t \geq 2\), the singularization of a \(Y_i\), \(1 \leq i \leq \binom{n}{t}\) into a connected graph is achieved by some graph operation say, \(f_1(G,H)\) by defining the singularized graph,

\begin{equation} Y^{s}_i = f_1(f_1(f_1(f_1(G_i,G_j),G_k),\dots, G_q)). \end{equation} Now a conventional vertex \(v_i\) which is isomorphic to \(K_1\) is generalized to a vertex which is isomorphic to a \(Y^{s}_i\). Hence, \(v_i\) maps to \(Y^{s}_i\). The generalized Johnson graph can be defined for the singularized vertex set in terms of the corresponding \(t\)-element subsets. This opens a new avenue of research.

Acknowledgments :

The author would like to thank the anonymous referees for their constructive comments, which helped to improve the elegance of this note.

Conflicts of Interest:

''The author declares that there is no conflict of interest in respect of this research.''