For a finite simple undirected graph \(G=(V,E)\), a subset \(C\subseteq V\) is called an identifying code of \(G\) if the closed neighborhood of every vertex has a nonempty and unique intersection with \(C\). The minimum cardinality of such a set is denoted by \(\gamma^{ID}(G)\). In this paper, we strengthen the previously known results of Nadimi Dafrazi and Vatandoost on the identifying-code number of middle graphs, which were established for bipartite graphs and certain other classes, by proving the exact value for every finite simple graph \(G\) of order at least one. By establishing a new lower bound, we show that the identifying-code number of the middle graph \(M(G)\) is equal to its independence number; specifically, \(\gamma^{ID}(M(G))=\alpha(M(G))=|V(G)|.\)
All graphs considered in this paper are non-empty, finite, undirected, and simple. For standard graph theory terminology not given here, we refer to [18]. For a simple graph \(G=(V(G),E(G))\), we denote the open neighbourhood and the closed neighbourhood of a vertex \(v \in V(G)\) by \( N_G(v)=\{u \in V(G)\mid uv \in E(G)\} \) and \( N_G[v]=N_G(v)\cup\{v\}, \) respectively. We denote the minimum and maximum degree of \(G\) by \(\delta=\delta(G)\) and \(\Delta=\Delta(G)\), respectively, and the induced subgraph by \(S \subseteq V(G)\) by \(G[S]\). An independent set is a set of vertices in \(G\) no two of which are adjacent. A maximum independent set is an independent set of largest possible size for a given graph \(G\). This size is called the independence number of \(G\) and it is denoted by \(\alpha(G)\). A dominating set, briefly DS, of a graph \(G\) is a set \(S \subseteq V(G)\) such that \( N_G[v]\cap S \neq \emptyset, \) for any vertex \(v \in V(G)\). The domination number of \(G\) is the minimum cardinality of a DS of \(G\) and it is denoted by \( \gamma(G). \) Moreover, a dominating set of \(G\) of cardinality \(\gamma(G)\) is called a \(\gamma\)-set of \(G\). The notion of domination is well studied in graph theory, and the literature on this subject has been surveyed in the two books [7, 6].
A subset \(C\) of \(V(G)\) is an identifying code of \(G\) if \(C\) is a dominating set of \(G\) and for every pair \(u,v\) of vertices of \(G\), \( N_G[u]\cap C \neq N_G[v]\cap C. \) We say that \(G\) is an identifiable graph if \(G\) has an identifying code. For the graph \(G\), the identifying code number of \(G\), denoted by \(\gamma^{ID}(G)\), is
Two distinct vertices \(u,v \in V(G)\) are called closed twins if \( N_G[u]=N_G[v]. \) A graph \(G\) is said to be closed-twin-free if it contains no pair of closed twins. It is well-known that a graph \(G\) admits an identifying code if and only if \(G\) is closed-twin-free. Note that the existence of open twins (vertices with \( N_G(u)=N_G(v) \) does not prevent a graph from being identifiable.
Identifying codes were introduced in 1998 [9], motivated by fault-detection in multiprocessor networks. Since then, numerous other applications of identifying codes have been discovered, such as threat location in facilities using sensor networks [16], logical definability of graphs [15], or canonical labeling of graphs for the graph isomorphism problem [2]. Besides, since the 1960s and long before the introduction of identifying codes of graphs, many related concepts such as separating systems or test covers have been independently studied. All of them put together form the general area of identification problems in graphs and other discrete structures. Karpovsky et al. [9] in 1998 introduced the identifying code concept. Later, several various families of graphs have been studied such as paths and cycles [3, 4], trees [1], triangular and square grids [8]. Also identifying codes have found applications in various fields.
The study of identifying codes in middle graphs \(M(G)\) has garnered attention due to their structural properties. To contextualize our results, it is essential to distinguish between established findings and the contributions of this paper. First, it is known that every middle graph \(M(G)\) is identifiable, a property derived from the nature of the closed neighborhoods in such graphs. Second, the construction \(C=V(G)\) is a standard approach that yields the upper bound \( \gamma^{ID}(M(G)) \leq |V(G)|. \) Recently, Nadimi Dafrazi and Vatandoost [14] have determined the identifying-code number for specific families, such as bipartite graphs, the generality of this result remained to be fully addressed. In this work, we prove that this equality holds for any arbitrary finite simple graph \(G\) with at least one vertex. Specifically, our primary contribution is the establishment of a new lower bound that confirms \( \gamma^{ID}(M(G))=|V(G)|, \) thus extending the known results for bipartite and special graph classes to the entire class of finite simple graphs. Furthermore, the study of identifying codes has recently expanded to include various graph operations. Recent research has investigated identifying codes under operations such as subdivision, corona products, and graph products [14, 17, 12, 13]. These developments underscore the importance of characterizing identifying codes for fundamental graph classes, which remains a central theme in the current literature.
Historically, finding classes of graphs for which certain graph parameters coincide has been a subject of significant interest. In this paper, we address this theme by investigating whether the known upper bound \(\gamma^{ID}(M(G)) \leq |V(G)|\) is attained for all finite simple graphs \(G\) with at least one vertex, rather than only for the previously studied bipartite and special families of graphs. We show that a positive answer to this question, combined with the well-known independence-number formula \(\alpha(M(G)) = |V(G)|\), establishes the precise relationship:
for any finite simple graph \(G\) with \(|V(G)| \geq 1\).
In [5], the authors introduced the notion of the middle graph \(M(G)\) of a graph \(G\) as an intersection graph on \(V (G)\).
Definition 1.1. Let \(G = (V(G), E(G))\) be a simple graph with \(V(G) = \{v_1, \dots, v_n\}\). The middle graph \(M(G)\) is the graph whose vertex set is \( V(M(G)) = V(G) \cup \mathcal{M}, \) where \(\mathcal{M} = \{m_{ij} \mid v_iv_j \in E(G), i < j\}\). Two vertices \(x, y \in V(M(G))\) are adjacent in \(M(G)\) if one of the following conditions holds:
It is obvious that \(M(G)\) contains the line graph \(L(G)\) as an induced subgraph, and that if \(G\) is a graph of order \(n = |V(G)|\) and size \(m = |E(G)|\), then \(M(G)\) is a graph of order \(n+m\) and size \(2m+|E(L(G))|\), which is obtained by subdividing each edge of \(G\) exactly once and joining all the adjacent edges of \(G\) in \(M(G)\). In order to avoid confusion throughout the paper, we fix a “standard” notation for the vertex set and the edge set of \(M(G)\). Assume \(V(G)=\{v_1,\dots,v_n\}\), then we set \( V(M(G)) = V(G) \cup \mathcal{M}, \) where \( \mathcal{M} = \{m_{ij} : v_iv_j \in E(G),\, i<j\}, \) and
The goal of this paper is to study the identifying code number of middle graphs.
Theorem 2.1. [10] Let \(G\) be a graph with \(n \geq 2\) vertices. Assume \(G\) has no isolated vertices. Then
Observation 2.2. By the definition of \(M(G)\), the edge set of \(M(G)\) is
For every vertex \(v_i \in V(G)\), the closed neighborhood is
For every edge-vertex \(m_{ij} \in M\) (where \(i<j\)), the closed neighborhood is
Lemma 2.3. Let \(G\) be a finite simple graph of order \(n\). The equality
holds.
Proof. This equality was previously established in [11] under the assumption that \(G\) is connected. Here, we remove this restriction and provide a concise, alternative matching-based proof for any arbitrary finite simple graph. Since no two vertices of \(V(G)\) are adjacent in \(M(G)\), the set \(V(G)\) is independent in \(M(G)\). Hence,
Conversely, let \(S\) be an arbitrary independent set of \(M(G)\), and partition it into
Because \(S\) is independent, no two edge-vertices in \(S_1\) can be adjacent in \(M(G)\). Consequently, the edges of \(G\) corresponding to \(S_1\) are pairwise nonincident, meaning they form a matching in \(G\). Thus, these edges have exactly \(2|S_1|\) distinct endpoints in \(V(G)\). Furthermore, none of these \(2|S_1|\) endpoints can belong to \(S_0\), because in \(M(G)\) each edge-vertex is adjacent to its endpoints. It follows that
Therefore, we obtain
This shows that
Combining the two bounds, we conclude that \( \alpha(M(G)) = n.\) \(\square\)
Theorem 2.4. Let \(G\) be a graph of order \(n \geq 1\). Then \(M(G)\) is an identifiable graph. Consequently, the set \(V(M(G))\) is an identifying code for \(M(G)\).
Proof. The identifiability of \(M(G)\) has been established in previous literature [14]. For completeness, we provide a concise alternative proof by showing that \(M(G)\) is closed-twin-free. Let \(u,v \in V(M(G))\) be distinct vertices. We show that \( N[u] \neq N[v] \) by considering the symmetric difference \( (N[u] \setminus N[v]) \cup (N[v] \setminus N[u]). \)
Since \(M(G)\) is closed-twin-free, the entire vertex set \(V(M(G))\) acts as an identifying code for \(M(G)\). \(\square\)
Theorem 2.5. Let \(G\) be a graph of order \(n \ge 2\). If \(C\) is an identifying code of \(M(G)\) and \(v \in V(G)\) satisfies \(\deg_G(v)\le 1\), then \(v\in C\).
Proof. The degree-zero case is immediate because an isolated original vertex can only be dominated by itself. Now suppose that \(\deg_G(v)=1\), and let \(u\) be the unique neighbor of \(v\) in \(G\). Let \(m_{uv}\) denote the edge-vertex corresponding to the edge \(uv\). Then in \(M(G)\) we have
Assume, to the contrary, that \(v\notin C\). Since \(C\) is a dominating set of \(M(G)\) and \(N_{M(G)}[v]=\{v,m_{uv}\}\), it follows that \(m_{uv}\in C\). By (2) and the assumption \(v\notin C\), we obtain
which contradicts the fact that \(C\) is an identifying code. Therefore, \(v\in C\). \(\square\)
Lemma 3.1. Let \(C\) be an identifying code of \(M(G)\), and let \(A=V(G)\setminus C\). For each \(v_i\in A\), define
Then \(B_i\neq\varnothing\) and in fact \(|B_i|\ge 2\).
Proof. Since \(C\) is a dominating set of \(M(G)\) and \(v_i\notin C\), the vertex \(v_i\) must be dominated by at least one code vertex. Because the only neighbors of \(v_i\) in \(M(G)\) are the edge-vertices corresponding to edges incident with \(v_i\), it follows that \(B_i\neq\varnothing\). Now suppose, for a contradiction, that \(B_i=\{m_{ij}\}\). Then \(m_{ij}\in C\), while no other edge-vertex incident with \(v_i\) belongs to \(C\). Since \(v_i\notin C\), we have
On the other hand, the closed neighborhood of \(m_{ij}\) in \(M(G)\) can only contain code vertices coming from \(v_i\), \(v_j\), or from edge-vertices incident with \(v_i\) or \(v_j\). Under the assumption \(B_i=\{m_{ij}\}\), none of the additional vertices incident with \(v_i\) belongs to \(C\), so the trace of \(m_{ij}\) on \(C\) is also
Thus
which contradicts the identifying property of \(C\). Therefore, \(|B_i|\ge 2\). \(\square\)
Theorem 3.2. Let \(G\) be a graph of order \(n \ge 1\). Then
Proof. Let \(V(G)=\{v_1,v_2,\ldots,v_n\}\), and let \( V(M(G))=V(G)\cup M, \) where \( \mathcal{M}=\{m_{ij}\mid v_iv_j\in E(G),\, i<j\}. \)
Upper bound. We first show that \(V(G)\) is an identifying code of \(M(G)\). Indeed, for each \(1\le i\le n\), \( N_{M(G)}[v_i]\cap V(G)=\{v_i\}, \) and for every edge-vertex \(m_{ij}\in \mathcal{M}\), \( N_{M(G)}[m_{ij}]\cap V(G)=\{v_i,v_j\}. \) Since \(G\) is simple, distinct edge-vertices correspond to distinct pairs of endpoints, and therefore these traces are nonempty and pairwise distinct for all vertices of \(M(G)\). Hence \(V(G)\) is an identifying code of \(M(G)\), and so
Lower bound. Now suppose, to the contrary, that \(C\) is an identifying code of \(M(G)\) with
Set
Then
Since
we obtain
and hence
By Theorem 2.5, every vertex of degree at most \(1\) in \(G\) belongs to every identifying code of \(M(G)\). Therefore every vertex in \(A\) has degree at least \(2\) in \(G\). For each \(v_i\in A\), define
By Lemma 3.1, we have
Now define the incidence set
Then
On the other hand, each edge-vertex \(m_{ij}\in B\) is adjacent to exactly two original vertices, namely \(v_i\) and \(v_j\). Thus each \(m_{ij}\in B\) can contribute to at most two pairs in \(I\), so
Combining the two inequalities yields
and therefore
This contradicts \(|A|\ge |B|+1\). Hence no identifying code of size at most \(n-1\) exists, and so
Together with the upper bound, we conclude that
\(\square\)
By Lemma 2.3 and Theorem 3.2 we obtain the following result.
Corollary 3.3. Let \(G\) be a finite simple graph of order \(n\ge 1\). Then
Example 3.4. Let \(G=K_5\). Consider \(C=V(K_5)\). For each \(v_i \in V(K_5)\), we have \(N_{M(K_5)}[v_i]\cap C=\{v_i\}\), and for each edge-vertex \(m_{ij}\), \(N_{M(K_5)}[m_{ij}]\cap C=\{v_i, v_j\}\). These traces are pairwise distinct, which implies that \(C\) is an identifying code of \(M(K_5)\). Thus, \(\gamma^{ID}(M(K_5)) \le |V(K_5)| = 5\). By Theorem 3.2, we have \(\gamma^{ID}(M(K_5)) = |V(K_5)| = 5\).
By Theorem 3.2, \( \gamma^{ID}(M(G))=|V(G)|=n. \) On the other hand, by Theorem 2.1, if \(G\) has no isolated vertices, then
Therefore,
We obtain the following result.
Corollary 3.5. Let \(G\) be a finite simple graph of order \(n \ge 2\) without isolated vertices. Then
In this paper, we have established the exact value of the identifying-code number for the class of middle graphs \(M(G)\). Specifically, we proved that for every finite simple graph \(G\) of order \(n \ge 1\), the equality \(\gamma^{ID}(M(G)) = |V(G)|\) holds. This result provides a complete answer to the question of when the identifying-code number of a middle graph coincides with the independence number of the same graph, i.e., \(\gamma^{ID}(M(G)) = \alpha(M(G)) = n\). The primary contribution of this work lies in providing a universal lower bound \(\gamma^{ID}(M(G)) \ge n\) for any finite simple graph, regardless of its structure. This generalizes the results of Nadimi Dafrazi and Vatandoost [14] (2026), which focused on specific classes such as trees and bipartite graphs. Our incidence-counting approach allowed us to treat the problem globally, including non-bipartite graphs and graphs with multiple odd cycles (see the example of \(K_5\)). Furthermore, our formulation explicitly accounts for disconnected graphs. If a graph \(G\) is disconnected with components \(G_1, \dots, G_k\), it follows that \(M(G)\) is also disconnected with components \(M(G_1), \dots, M(G_k)\), and the result remains valid by summing over the components. Regarding isolated vertices, if \(G\) contains \(k\) isolated vertices, these vertices become isolated in \(M(G)\) as well; since an isolated vertex must be in any identifying code and contributes \(1\) to both \(\gamma^{ID}\) and \(n\), the equality holds. Future research could explore identifying codes in other graph operations, such as total graphs or line graphs of higher-order structures, to determine if similar universal equalities exist between their identifying-code numbers and other structural parameters like the independence number or clique number.
The authors declare no conflicts of interest.
This research received no external funding.
This study is theoretical and does not involve the generation or analysis of datasets.
All the authors contributed equally. All authors have read and agreed to the published version of the manuscript.