We introduce the ID-index of a finite simple connected graph. For a graph \(G=(V,\ E)\) with diameter \(d\), we let \(f:V\longrightarrow \mathbb{Z}\) assign ranks to the vertices. Then under \(f\), each vertex \(v\) gets a string, which is a \(d\)-vector with the \(i\)-th coordinate being the sum of the ranks of the vertices that are of distance \(i\) from \(v\). The ID-index of \(G\), denoted by \(IDI(G)\), is defined to be the minimum number \(k\) for which there is an \(f\) with \(|f(V)|=k\), such that each vertex gets a distinct string under \(f\). We present some relations between ID-graphs, which were defined by Chartrand, Kono, and Zhang, and their ID-indices; give a lower bound on the ID-index of a graph; and determine the ID-indices of paths, grids, cycles, prisms, complete graphs, some complete multipartite graphs, and some caterpillars.
In this paper, every graph is assumed to be a finite simple connected graph, so each graph we study has a finite diameter.
The topic of uniquely identifying each vertex in a graph has been extensively studied. For example, we have the metric dimension of a graph \(G=(V,\ E)\), which is the smallest size of a set \(S\subseteq V\) such that every vertex \(v\in V\) can be uniquely determined by the distances between \(v\) and the vertices in \(S\). This concept was introduced by Slater [15] in 1975 and independently by Harary and Melter [6] in 1976, and has been studied by multiple scholars (see [1, 3, 7, 8]). Another example is the partition dimension of a graph, where vertex colorings are used (see [2, 5, 13, 14]).
Chartrand, Kono, and Zhang introduced ID-graphs in [4], which gave a new idea of identifying vertices in a graph. For a graph \(G\) with diameter \(d\), a red-white coloring of \(G\) is an assignment of red and white to the vertices in \(G\) with at least \(1\) vertex being red. Under a red-white coloring, each vertex \(v\) in \(G\) has a code, which is a \(d\)-vector, with the \(i\)-th coordinate being the number of red vertices that are of distance \(i\) from \(v\). A red-white coloring of \(G\) where each vertex gets a distinct code is said to be an ID-coloring of \(G\). If \(G\) has an ID-coloring, then it is an ID-graph, and the ID-number of \(G\), denoted by \(ID(G)\), is the minimum number of red vertices we need to construct an ID-coloring.
Kono and Zhang studied ID-trees in [10]; gave a note on ID-caterpillars in [11]; and studied ID-grids and ID-prisms in [12]. The results in these papers were also presented in Kono’s dissertation [9].
Generalizing this idea, we introduce the ID-index of a graph. We let \(G=(V,\ E)\) be a graph with diameter \(d\), let \(f:V\longrightarrow \mathbb{Z}\) assign integers to the vertices in \(G\), and say \(f(v)\) is the rank of \(v\) for \(v\in V\). Under \(f\), each \(v\in V\) gets a string, which is a \(d\)-vector with the \(i\)-th coordinate being the sum of the ranks of the vertices that are of distance \(i\) from \(v\). The ID-index of \(G\), denoted by \(IDI(G)\), is defined to be the minimum number \(k\) for which there is an \(f:V\longrightarrow \mathbb{Z}\) with \(|f(V)|=k\), such that each vertex \(v\in V\) gets a distinct string under \(f\).
For example, the ID-index of the Petersen graph is \(3\). In Figure 1, we have a construction showing that three ranks are enough. Note that, in the figure, the label on each vertex is in the form “rank, (string)”, so “\(3,\ (2,\ 11)\)” means the rank of this vertex is \(3\), and the string of this vertex is \((2,\ 11)\). Later we will explain why the ID-index of the Petersen graph cannot be \(1\) or \(2\).
Indeed, every graph \(G=(V,\ E)\) has an ID-index. Too see this, we can assign \(1,\ 2,\ …,\ |V|\) to the vertices in \(G\), and it is guaranteed that each vertex gets a distinct string because for the vertex with rank \(i\), the sum of the coordinates of its string is \(\frac{|V|(|V|+1)}{2}-i\).
We have some connections between an ID-graph and its ID-index.
Proposition 1.1. If \(G\) is an ID-graph, then \(IDI(G)\le 2\).
Proof. Assume \(G\) is an ID-graph with an ID-coloring. We know that each vertex has a distinct code in this ID-coloring. Then we construct a rank assignment by letting the rank of each red vertex be \(1\), and letting the rank of each white vertex be zero. It is easy to see that the string of a vertex is the same as the code of this vertex, so each vertex has a distinct string, and thus \(IDI(G)\le 2\). ◻
Proposition 1.2. For a graph \(G\), the following two statements are equivalent.
\(\bullet\) \(G\) is an ID-graph, and there is an ID-coloring of \(G\) where every vertex is red.
\(\bullet\) \(IDI(G)=1\).
Proof. If \(G\) is an ID-graph with an ID-coloring where every vertex is red, then we can let the rank of every vertex be \(1\), and each vertex will have a distinct string, which is the same as its code. Thus \(IDI(G)=1\).
For the other direction, if \(IDI(G)=1\), then there is an \(r\in \mathbb{Z}\) with \(r\neq 0\) such that we can let the rank of every vertex be \(r\), and each vertex \(v\) will get a distinct string \((c_{v1},\ c_{v2},\ …,\ c_{vd})\), where \(d\) is the diameter of \(G\). Now if we let every vertex in \(G\) be red, then we can see that the code of \(v\) is \((\frac{c_{v1}}{r},\ \frac{c_{v2}}{r},\ …,\ \frac{c_{vd}}{r})\), which means each vertex has a distinct code, and thus \(G\) is an ID-graph with an ID-coloring where every vertex is red. ◻
The converse of Proposition 1.1 is not true, because a graph \(G\) with \(IDI(G)=2\) is not necessarily an ID-graph. For example, the construction in Figure 2 shows that the ID-index of the complete tripartite graph \(K_{1,\ 1,\ 2}\) is \(2\) (obviously it is not \(1\)). However, \(K_{1,\ 1,\ 2}\) is not an ID-graph, because it was showed in [4] that the only ID-complete multipartite graphs are \(K_{1,\ 1}\) and \(K_{1,\ 2}\).
Also, this example tells us that, for a graph \(G\) and its (induced) subgraph \(G'\), we do not necessarily have \(IDI(G')\le IDI(G)\). We can see that the triangle \(K_3\) is an (induced) subgraph of \(K_{1,\ 1,\ 2}\), and \(IDI(K_3)=3>2=IDI(K_{1,\ 1,\ 2})\).
In this section, we determine the ID-indices of some graphs, including paths, grids, cycles, prisms, complete graphs, some complete multipartite graphs, and some caterpillars.
First we give a lower bound on the ID-index of a graph, using the \(t\)-tuplets defined in [4]. For a graph \(G=(V,\ E)\), a set \(S\) of vertices with \(|S|=t\ge 2\) is said to be a \(t\)-tuplet if either
\(\bullet\) \(S\) is an independent set, and any two vertices in \(S\) have the same neighborhood;
or
\(\bullet\) \(S\) is a clique, and any two vertices in \(S\) have the same closed neighborhood, where the closed neighborhood of \(v\) is just \(N(v)\cup \{v\}\).
It is easy to see that, if \(u\) and \(v\) are two vertices in the same \(t\)-tuplet, then for any vertex \(w\) other than \(u\) and \(v\), we have \(d(u,\ w)=d(v,\ w)\), where \(d(\cdot,\ \cdot)\) measures the distance between two vertices.
Theorem 2.1. Let \(G=(V,\ E)\) be a graph, and let \(T(G)\) be the largest \(t\) such that there is a \(t\)-tuplet in \(G\). We have \[\begin{align*} IDI(G)\ge T(G). \end{align*}\]
Proof. Let \(u\) and \(v\) be two vertices in a \(T(G)\)-tuplet, and let \(f:V\longrightarrow \mathbb{Z}\) be a rank assignment under which we have \(f(u)=f(v)=r\) for some \(r\in \mathbb{Z}\).
We have, of course, \(d(u,\ v)=d(v,\ u)=D\) with \(D\in \{1,\ 2\}\), so \(u\) will contribute \(r\) to the \(D\)-th coordinate in the string of \(v\); and \(v\) will also contribute \(r\) to the \(D\)-th coordinate in the string of \(u\). For any vertex \(w\) other than \(u\) and \(v\), as we just mentioned, we have \(d(u,\ w)=d(v,\ w)\), so \(w\) will contribute \(f(w)\) to the same coordinate in the string of \(u\) and in the string of \(v\). So, under rank assignment \(f\), \(u\) and \(v\) will get exactly the same string. Thus, in order to let each vertex have a distinct string, we need to let the vertices in a \(T(G)\)-tuplet get distinct ranks, which means \(IDI(G)\ge T(G)\). ◻
Let us look at specific graphs.
In this subsection, we make use of the results in [4, 12] to study some basic families of graphs, whose ID-indices are constants.
For paths, it is proved in [4] that every path \(P_n\) with \(n\ge 2\) is an ID-graph, so by Proposition 1.1, we have \(IDI(P_n)\le 2\). It is easy to see that every vertex being red does not give us an ID-coloring of \(P_n\), so by Proposition 1.2, we know \(IDI(P_n)\neq 1\). So for any path \(P_n\) with \(n\ge 2\), we have \(IDI(P_n)=2\).
For grids, it is proved in [12] that the grid \(P_m\square P_n\) is an ID-graph if and only if \((m,\ n)\neq (2,\ 2)\). Similar to paths, we can draw the conclusion that \(IDI(P_m\square P_n)=2\) if \((m,\ n)\neq (2,\ 2)\). Also, we can make the observation that \(IDI(P_2\square P_2)=IDI(C_4)=3\).
For cycles, it is proved in [4] that the cycle \(C_n\) is an ID-graph if and only if \(n\ge 6\). Similar to paths, we can reach the conclusion that \(IDI(C_n)=2\) if \(n\ge 6\). Also, we can make the observation that \(IDI(C_3)=IDI(C_4)=IDI(C_5)=3\).
For prisms, it is proved in [12] that the prism \(Y_n:=C_n\square P_2\) is an ID-graph if and only if \(n\ge 6\). Similar to paths, we can conclude that \(IDI(Y_n)=2\) if \(n\ge 6\). Then, for \(Y_3\), \(Y_4\), and \(Y_5\), by construction, we know that the ID-index of each of them is at most \(3\). Figure 3 shows a feasible rank assignment and the strings under this assignment for \(Y_5\). The constructions for \(Y_3\) and \(Y_4\) are similar.
Actually we have \(IDI(Y_3)=IDI(Y_4)=IDI(Y_5)=3\). To verify this, we show that each of them is not \(2\), because obviously they cannot be \(1\). Of course, one may show this by a case-by-case argument, but we can also do it in a much easier way.
We mentioned that, in general, a graph \(G\) with \(IDI(G)=2\) is not necessarily an ID-graph. However, if \(G\) has a specific property stated in the following lemma, then it is an ID-graph.
Lemma 2.2. Let \(G=(V,\ E)\) be a graph with diameter \(d\). If there exist integers \(n_1,\ n_2,\ …,\ n_d\ge 1\) with \(\sum\limits_{i=1}^d n_i=|V|-1\) such that for any vertex \(v\in V\) and any \(1\le i\le d\), there are \(n_i\) vertices at distance \(i\) from \(v\), then for any rank assignment \(f\) which gives each vertex a distinct string, the rank assignment \(kf+b:v\longmapsto kf(v)+b\) with \(k\neq 0\) also gives each vertex a distinct string. Furthermore, if we also have \(IDI(G)=2\), then \(G\) is an ID-graph.
Proof. Suppose for \(G\), we have \(n_1,\ n_2,\ …,\ n_d\) satisfying the conditions stated above. For vertices \(u\) and \(v\), assume they have strings \((c_{u1},\ c_{u2},\ …,\ c_{ud})\) and \((c_{v1},\ c_{v2},\ …,\ c_{vd})\) under rank assignment \(f\), and we have \(c_{ui}\neq c_{vi}\) for some \(1\le i\le d\). Then under \(kf+b\) with \(k\neq 0\), the \(i\)-th coordinate in the string of \(u\) will be \(kc_{ui}+n_i b\), and the \(i\)-th coordinate in the string of \(v\) will be \(kc_{vi}+n_i b\). We have \(kc_{ui}+n_i b\neq kc_{vi}+n_i b\) because \(c_{ui}\neq c_{vi}\) and \(k\neq 0\). So \(kf+b\) also gives each vertex a distinct string.
Now we further assume \(IDI(G)=2\), so there is some \(f\) which assigns \(r_1\in \mathbb{Z}\) to some vertices, and assigns \(r_2\) with \(r_2\neq r_1\) to others, such that each vertex has a distinct string. Then it is easy to see that there exist \(k\neq 0\) and \(b\) such that \(kr_1+b=0\) and \(kr_2+b=1\). We know \(kf+b\) is a rank assignment where each vertex has a distinct string. But now, we can let every vertex with rank zero be white, and let every vertex with rank \(1\) be red. Then we obtain an ID-coloring of \(G\) where the code of a vertex is the same as the string of this vertex, so \(G\) is an ID-graph. ◻
Proposition 2.3. We have \(IDI(Y_n)\neq 2\) for \(n\in \{3,\ 4,\ 5\}\).
Proof. We can apply Lemma 2.2 to \(Y_3\), \(Y_4\), and \(Y_5\), because:
\(\bullet\) For \(Y_3\), we have: \(diam(Y_3)=2\), \(n_1=3\), and \(n_2=2\).
\(\bullet\) For \(Y_4\), we have: \(diam(Y_4)=3\), \(n_1=3\), \(n_2=3\), and \(n_3=1\).
\(\bullet\) For \(Y_5\), we have: \(diam(Y_5)=3\), \(n_1=3\), \(n_2=4\), and \(n_3=2\).
By Lemma 2.2, we know that if \(IDI(Y_n)=2\) for some \(n\in \{3,\ 4,\ 5\}\), then \(Y_n\) is an ID-graph. However, as we mentioned earlier, it is proved in [12] that \(Y_n\) is an ID-graph if and only if \(n\ge 6\). So \(IDI(Y_n)\neq 2\) for \(n\in \{3,\ 4,\ 5\}\). ◻
Note that Lemma 2.2 also applies to the Petersen graph, so if the ID-index of the Petersen graph is \(2\), then the Petersen graph is an ID-graph. However, it was showed in [4] that the Petersen graph is not an ID-graph, so its ID-index cannot be \(2\). Combining this fact with the observation that its ID-index is not \(1\), and the construction in Figure 1, we know that indeed the ID-index of the Petersen graph is \(3\).
In this subsection, the lower bound in Theorem 2.1 plays a key role.
The complete graph \(K_n\) itself is an \(n\)-tuplet, so by Theorem 2.1, we know \(IDI(K_n)\ge n\), and thus \(IDI(K_n)=n\).
Then for the complete multipartite graphs, we can see that the vertices in each part form a \(t\)-tuplet with \(t\) being the part size. So, in the complete \(k\)-partite graph \(K_{m_1,\ m_2,\ …,\ m_k}\) with \(m_1\le m_2\le …\le m_k\), we know that \(IDI(K_{m_1,\ m_2,\ …,\ m_k})\ge m_k\).
We can determine the exact ID-indices for some of the complete multipartite graphs.
Theorem 2.4. For the complete \(k\)-partite graph \(K_{m_1,\ m_2,\ …,\ m_k}\) with \(m_1<m_2<…<m_k\), we have \[\begin{align*} IDI(K_{m_1,\ m_2,\ …,\ m_k})=m_k. \end{align*}\]
Proof. We already know \(IDI(K_{m_1,\ m_2,\ …,\ m_k})\ge m_k\), and we will show \(IDI(K_{m_1,\ m_2,\ …,\ m_k})\\ \le m_k\) by construction. We construct a rank assignment \(f\) in the following fashion: For each \(1\le i\le k\), there are \(m_i\) vertices in the \(i\)-th part. Let the ranks of these vertices be \(1,\ 2,\ …,\ m_i\), and let \(M\) denote the sum of the ranks of all vertices.
Under this rank assignment \(f\), two vertices in different parts have different strings, because their first coordinates must vary. Assuming \(u\) is in the \(p\)-th part, and \(v\) is in the \(q\)-th part, with \(p\neq q\), we have that the first coordinate in the string of \(u\) is \(M-\sum\limits_{\ell=1}^{m_p}\ell\), the first coordinate in the string of \(v\) is \(M-\sum\limits_{l=1}^{m_q}l\), and they two are different because \(m_p\neq m_q\).
Also, two vertices in the same part have different strings, because their second coordinates must vary. Assuming \(u\) and \(v\) are both in the \(r\)-th part, with \(1\le f(u)\neq f(v)\le m_r\), we have that the second coordinate in the string of \(u\) is \(\sum\limits_{\ell=1}^{m_r}-f(u)\), the second coordinate in the string of \(v\) is \(\sum\limits_{\ell=1}^{m_r}-f(v)\), and they two are different because \(f(u)\neq f(v)\).
Under this \(f\), each vertex has a distinct string, so \(IDI(K_{m_1,\ m_2,\ …,\ m_k})\le m_k\), and thus \(IDI(K_{m_1,\ m_2,\ …,\ m_k})=m_k\). ◻
Also, we know the exact ID-indices of the complete bipartite graphs.
Theorem 2.5. For the complete bipartite graph \(K_{m,\ n}\) with \(m\le n\), we have \[IDI(K_{m,\ n})=\begin{cases} n &if\ m<n, \\ n+1 &if\ m=n. \end{cases}\]
Proof. The case that \(m<n\) is already solved in the previous theorem. Let us assume \(m=n\).
First, we show that \(IDI(K_{n,\ n})>n\). Assume we only have \(n\) ranks \(r_1,\ r_2,\ …,\ r_n\). Because each part is an \(n\)-tuplet, we know that, in each part, the \(n\) ranks must all appear. But now, it is easy to see that, for any \(1\le i\le n\), the vertex in the first part with rank \(r_i\) and the vertex in the second part with rank \(r_i\) have the same string, which we do not want to happen. So \(IDI(K_{n,\ n})>n\).
Then, we show that \(IDI(K_{n,\ n})\le n+1\) by construction. We construct \(f\) by letting the vertices in the first part get ranks \(1,\ 2,\ …,\ n\), and letting the vertices in the second part get ranks \(2,\ 3,\ …,\ n+1\). Then, the same as what we did in the previous proof, it is easy to check that any two vertices have different strings. ◻
New strategies are needed to determine the exact ID-indices for general complete multipartite graphs.
Problem 2.6. Determine the exact value of \(IDI(K_{n_1\times 1, n_2\times 2, …, n_t\times t})\).
The last part of this paper is devoted to finding the ID-indices of caterpillars. A caterpillar is a tree, where there is a path that contains every vertex of degree at least \(2\). This path is called the spine of the caterpillar.
Let \(G\) be a caterpillar with the spine being a path on \(n\) vertices. From one end of the spine to the other end, we denote the spine vertices by \(s_1,\ s_2,\ …,\ s_n\), and denote the number of leaves attached on \(s_i\) by \(L_i\). For example, Figure 4 shows a caterpillar with \(L_1=2\), \(L_2=3\), \(L_3=2\), \(L_4=0\), and \(L_5=3\).
Note that \(L_2,\ L_3,\ …,\ L_{n-1}\) could be zero, but \(L_1\) and \(L_n\) must be at least \(1\), because if a spine vertex on the end does not have any attached leaves, then this vertex will be considered a leaf attached to the spine vertex next to it.
As we can see, the diameter of \(G\) is \(n+1\); and for each spine vertex \(s_i\), the \(L_i\) leaves attached on it form an \(L_i\)-tuplet. So, by Theorem 2.1, we know \(IDI(G)\ge \max_{1\le i\le n}L_i\). On the basis of this lower bound, we can determine the exact ID-indices of symmetric caterpillars, where a caterpillar is symmetric if for any \(1\le j\le \lfloor\frac{n}{2}\rfloor\), we have \(L_j=L_{n+1-j}\).
Theorem 2.7. Let \(G=(V,\ E)\) be a symmetric caterpillar with \(n\) spine vertices, and denote \(\max_{1\le i\le n}L_i\) by \(L\). We have \[IDI(G)=\begin{cases} L &if\ L\ge 2, \\ 2 &if\ L=1. \end{cases}\]
Proof. If \(n=1\), then the caterpillar is actually a star, which is just \(K_{1,\ L}\). So we can get our desired conclusion using Theorem 2.5. Now, let us assume there are at least two vertices on the spine, so \(n\ge 2\).
Case 1. \(L\ge 2\).
We already have \(IDI(G)\ge L\), so we only need to check that \(IDI(G)\le L\). We construct a rank assignment \(f:V\longrightarrow \mathbb{Z}\) in the following fashion: For the spine vertices, we let \(f(s_1)=2\), and let \(f(s_i)=1\) for \(2\le i\le n\); for the \(L_i\) leaves attached on \(s_i\), we let their ranks be \(1,\ 2,\ …,\ L_i\). An example is given in Figure 5, where the leftmost spine vertex is \(s_1\), and the rightmost spine vertex is \(s_6\).
The idea of this construction is making almost everything symmetric, but using the only spine vertex with rank \(2\) to “break the balance”. We need to check that, under our \(f\), each vertex has a distinct string.
First, we show that two spine vertices have different strings.
\(\bullet\) If \(p\neq q\) and \(p\neq n+1-q\), then \(s_p\) and \(s_q\) have different strings. In the string of \(s_x\), the first \(\max\{x,\ n+1-x\}\) coordinates are nonzero, and the rest are zero. So if \(p\neq q\) and \(p\neq n+1-q\), then \(s_p\) and \(s_q\) have different numbers of nonzero coordinates in their strings.
\(\bullet\) For any \(1\le k\le \lfloor\frac{n}{2}\rfloor\) with \(k\neq n+1-k\), the string of \(s_k\) and the string of \(s_{n+1-k}\) are different. This is obvious because \(s_k\) and \(s_{n+1-k}\) have different distances from \(s_1\), the only spine vertex with rank \(2\). For example, in Figure 5, the rank of \(s_1\) is counted in the second coordinate in the string of \(s_3\); but it is counted in the third coordinate in the string of \(s_4\). Actually, the string of \(s_3\) is \((5,\ 16,\ 14,\ 3,\ 0,\ 0,\ 0)\), and the string of \(s_4\) is \((5,\ 15,\ 15,\ 3,\ 0,\ 0,\ 0)\).
Second, we show that two attached leaves have different strings. For two leaves \(u\) and \(v\):
\(\bullet\) If they are attached on the same spine vertex, then the second coordinates in their strings are different, because \(f(u)\neq f(v)\), and \(f(u)\) contributes to the second coordinate in the string of \(v\), and vice versa.
\(\bullet\) If \(u\) is attached on \(s_p\), \(v\) is attached on \(s_q\), where \(p\neq q\) and \(p\neq n+1-q\), then they have different numbers of nonzero coordinates in their strings, just like what we have for the spine vertices.
\(\bullet\) If \(u\) is attached on \(s_k\), \(v\) is attached on \(s_{n+1-k}\), for some \(1\le k\le \lfloor\frac{n}{2}\rfloor\), then we know their strings are different because \(u\) and \(v\) have different distances from \(s_1\), the only spine vertex with rank \(2\).
Also, a spine vertex and an attached leaf have different strings.
\(\bullet\) For a leaf \(u\) attached on \(s_j\) with \(2\le j\le n\), the first coordinate in the string of \(u\) is \(1\), because \(s_j\) is the only neighbor of \(u\). For any spine vertex \(s_i\), the first coordinate in the string of \(s_i\) is at least \(2\), because \(s_i\) has at least two neighbors. So the string of \(u\) must be different from the string of any \(s_i\), as their first coordinates vary.
\(\bullet\) If a leaf \(v\) is attached on \(s_1\), then we can see that every coordinate in the string of \(v\) is nonzero. We can also see that the \((n+1)\)-th coordinate in the string of \(s_i\) is zero, for any \(1\le i\le n\). So the string of \(v\) must be different from the string of any \(s_i\), as they have different numbers of nonzero coordinates.
Case 2. \(L=1\).
In this case, we have \(IDI(G)\le 2\), because we can construct a rank assignment \(f\) by letting \(f(s_1)=2\) and \(f(v)=1\) for \(v\in V\) and \(v\neq s_1\). One can readily confirm that this assignment yields the same outcome as that in Case 1.
Also, we have \(IDI(G)\neq 1\), because if every vertex receives the same rank, then it is clear that the string of \(s_1\) is the same as the string of \(s_n\), as the caterpillar is symmetric. Thus, we have \(IDI(G)=2\) for \(L=1\). ◻
The next goal is to determine the ID-indices of non-symmetric caterpillars.
Problem 2.8. Assuming \(G\) is a non-symmetric caterpillar with \(n\) spine vertices, which means we have \(L_j\neq L_{n+1-j}\) for some \(1\le j\le \lfloor\frac{n}{2}\rfloor\), determine \(IDI(G)\).