On twin preserving spanning subgraph

Abstract

There are several approaches to lower the complexity of huge networks. One of the key notions is that of twin nodes, exhibiting the same connection pattern to the rest of the network. We extend this idea by defining a twin preserving spanning subgraph (TPS-subgraph) of a simple graph as a tool to compute certain graph related invariants which are preserved by the subgraph. We discuss how these subgraphs preserve some distance based parameters of the simple graph. We introduce a sub-skeleton graph on a vector space and examine its basic properties. The sub-skeleton graph is a TPS-subgraph of the non-zero component graph defined over a vector space. We prove that some parameters like the metric-dimension are preserved by the sub-skeleton graph.

Keywords

Basis graph independent set maximal clique metric-dimension twins 05C12 05C35

1 Introduction

Twin nodes of a graph play a vital role in computing different distance-related parameters like the metric-dimension of a graph[22]. The metric-dimension helps to locate an intruder in a network, optimally[30]. Twin nodes also play an important role in computing some degree based topological indices[7, 24]. One motivation to define TPS-subgraph (see Definition 4 in Section 4) is to reduce the complexity of a network. More precisely, one can reduce the size of a network while keeping twins the same. In[27], Riaza introduces the concept of T-twin and F-twin subgraphs for the same purpose, i.e., for reducing the complexity of a network. It is worth mentioning here that T-twin and F-twin subgraphs differ greatly from TPS-subgraph.

Here we recall some definitions, notations, and basic results. For other basic concepts, we refer the reader to [33].

For a connected simple graph Γ = (V, E), the distance d (s, t) between two nodes s, t ∈ V is the minimum length among all paths between them. For a node s of Γ, the closed neighborhood N [s] of s is the set {t ∈ V| d (s, t) =1} ∪ {s} , and the open neighborhood N (s) of s is the set {t ∈ V| d (s, t) =1} . Define s ≡ t if N [s] = N [t] or N (s) = N (t) for any two nodes s and t in the node set of Γ. In [22], it is given that “ ≡ " is an equivalence relation. The nodes s and t are called twins if s ≡ t. Twins s and t are called true twins if s and t are adjacent, otherwise, they are called false twins. The collection of all twins is called a twin-set. A spanning subgraph of a graph Γ is a subgraph with node set equal to V. An independent set of a graph is a subset I of V if any two nodes in it are pairwise non-adjacent. The maximum cardinality of I is known as the independence number. The chromatic number χ (Γ) of Γ is the minimum number of colors needed for a proper coloring of Γ. A clique is a subset of vertices of a graph Γ such that every two distinct vertices in the clique are adjacent. The cardinality of a maximum clique is called the clique number ω (Γ). A graph is called weakly perfect if the clique number of this graph is equal to its chromatic number. An Eulerian graph contains a cycle which passes through all the arcs exactly once.

For a graph Γ, consider an ordered set W = {w₁, w₂, …, w_k} of its nodes. For any node t of Γ, we have the expression r (t|W) = (d (t, w₁) , d (t, w₂) , …, d (t, w_k)) regarding W. If distinct nodes of Γ have different expression, then W is called a resolving set (see [12, 29]). In other words, two nodes t and s are resolved by a node w ∈ W if d (t, w) ≠ d (s, w). A metric basis B (Γ) of Γ is the minimum (smallest) size of a resolving set. This smallest size of B (Γ) is the metric-dimension dim_Γ of Γ (see [6 , 20]). A number of interesting applications of the concept of a resolving set not just in graph theory, but in many other areas such as combinatorial optimization [28], in coast guard Loran and sonar [30], to name only two.

2 Basic properties of sub-skeleton graph

The research related to graphs defined over various algebraic structures can be traced back to Caley graphs defined in the late 1800s in[8]. These graphs got the attention of researchers due to zero-divisor graph of a ring given by Beck in [5]. Afterwards, considerable research, e.g. [2–4 , 9–11] has been done in studying graphs defined over several algebraic stuctures. Intersection graphs connected to subspaces of vector spaces were explored in [23, 32]. Not long ago, some interesting graphs defined over vectors in finite-dimensional vector spaces have been studied in [15 –19].

From beginning to end of this writing, all vector spaces are defined over a finite field F and finite-dimensional. Let $B = {γ_{1}, γ_{2}, \dots, γ_{n}}$ be a basis of a vector space V and V = V \ {θ}, where θ is a null vector. A node t ∈ V can get a unique form t = a₁γ₁ + a₂γ₂ + ⋯ + a_nγ_n, where γ_i ∈ F. In [15], the non-zero component graph $Γ (V_{B})$ (or simply Γ (V)) is defined over a vector space V as follows: for the basis $B$ , the nodes are the non-zero vectors and two distinct nodes have an arc if there exists a place where both of the vectors have non-zero coordinates.

Definition 2.1. [19] The skeleton $S_{B} (t)$ (or simply S_t) of a vector t is the set of $γ_{i}^{,} s$ in the form t = a₁γ₁ + a₂γ₂ + ⋯ + a_nγ_n with non-zero $a_{i}^{,} s$ .

We define a sub-skeleton graph $Γ_{s} (V_{B}) = (V, E)$ (or simply Γ_s (V)) as: V = V \ {θ} and for t, s ∈ V, t ∼ s or (t, s) ∈ E if S_t ⊆ S_s or S_s ⊆ S_t. For easy writing, we use u to denote γ₁ + γ₂ + ⋯ + γ_n. For some examples of Γ_s (V), see Figure 1. One can see that the graph Γ_s (V) is TPS-subgraph of the graph Γ (V): two nodes in both the graphs Γ (V) and Γ_s (V) are twins if and only if they have the same skeleton.

Fig. 1

Examples of Γ_s (V).

Corresponding to a skeleton S_t, the vector t is not always unique. For two nodes s and t in Γ (V) or in Γ_s (V), there is an equivalence relation: s ≅ t if S_s = S_t. Let Cl_s represent the equivalence class such that s ∈ Cl_s. The length of the class Cl_s is the number of vectors of basis $B$ that the skeleton S_s contains.

Lemma 2.1. [1] The equivalence relations “ ≡ ″ and “ ≅ ″ are equivalent for Γ (V).

The above lemma holds for Γ_s (V) being a TPS-subgraph of Γ (V).

A number of basic properties including completeness and connectedness; a number of distance-related parameters like independence number of Γ (V) were discussed by the first author in [15, 19]. In this section, we investigate these basic properties for Γ_s (V). Most of these results can be recovered for Γ_s (V) and most of our proofs are just an adaptation of the original proofs given in [15, 19] for Γ (V). In other words, Γ_s (V) as a TPS-subgraph of Γ (V) preserves most of the basic properties.

Theorem 2.1. Let $Γ_{s} (V_{B_{1}})$ and $Γ_{s} (V_{B_{2}})$ be two sub-skeleton graphs corresponding to the bases: $B_{1} = {γ_{1}, γ_{2}, \dots, γ_{n}}$ and $B_{2} = {δ_{1}, δ_{2}, \dots, δ_{n}}$ . Then, these two graphs are graph isomorphic.

Proof. There is an isomorphism T : V → V such that T (γ_i) = δ_i, ∀ i ∈ {1, 2, …, n}. The restriction T on non-zero vectors of V, $T : Γ_{s} (V_{B_{1}}) \to Γ_{s} (V_{B_{2}})$ can be shown an isomorphism. The function T is clearly one-one and onto. Let t = a₁γ₁ + a₂γ₂ + ⋯ + a_nγ_n ; s = b₁γ₁ + b₂γ₂ + ⋯ + b_nγ_n with t ∼ s in $Γ_{s} (V_{B_{1}})$ . Then, $S_{B_{1}} (t) \subseteq S_{B_{1}} (s)$ or $S_{B_{1}} (s) \subseteq S_{B_{1}} (t)$ . Also, T (t) = a₁δ₁ + a₂δ₂ + ⋯ + a_nδ_n and T (s) = b₁δ₁ + b₂δ₂ + ⋯ + b_nδ_n. As ${i : γ_{i} \in S_{B_{1}} (t)} = {i : δ_{i} \in S_{B_{2}} (T (t))}$ for all t ∈ V, therefore T (t) ∼ T (s) in $Γ_{s} (V_{B_{2}})$ .

On the same lines, for two non-adjacent nodes t and s in $Γ_{s} (V_{B_{1}})$ , we have non-adjacent nodes T (t) and T (s) in $Γ_{s} (V_{B_{2}})$ . □

Theorem 2.2. A vector space V has dimension 1 if and only if Γ_s (V) is complete.

Proof. If V has dimension 1 and γ is its basis. Then, non-zero nodes t and s can be written as d₁γ and d₂γ respectively for non-zero d₁, d₂ ∈ F. It follows, t is adjacent to s.

Conversely, let Γ_s (V) be complete and dim (V) >1. Then, there exist $γ_{1}, γ_{2} \in B$ which is a basis or part of a basis of V. Consequently, γ₁ and γ₂ are not adjacent nodes in Γ_s (V), a contradiction. □

2.1 Independent sets in Γ_s (V)

Here, we discuss the independent sets of Γ_s (V) and find its independence number. We start by stating a result by E. Sperner which will be crucial in this context.

Definition 2.2 [Sperner Family] A collection of sets is called a Sperner family if it does not contain two sets X and Y such that X ⊆ Y.

Proposition 2.2 [Sperner’s Theorem]. [31] For every Sperner family $S$ whose union has a total of n elements, $| S | \leq (\begin{matrix} n \\ ⌊ n / 2 ⌋ \end{matrix}) .$ Moreover, the equality holds if $S$ is the collection of all ⌊n/2⌋-subsets of a set of n elements.

Theorem 2.3. For n dimensional vector space V, the independence number of Γ_s (V) is equal to $(\begin{matrix} n \\ ⌊ n / 2 ⌋ \end{matrix}) .$

Proof. Let I be an independent set of maximum cardinality in Γ_s (V). Consider the set S (I) = {S (γ) : γ ∈ I}. As I is a maximum independent set, S (I) forms a maximum anti-chain of subsets of $B$ . Thus, by Sperner’s Theorem, |S (I) | = $(\begin{matrix} n \\ ⌊ n / 2 ⌋ \end{matrix})$ and S (I) is the collection of all subsets of $B$ of size ⌊n/2⌋.

It is obvious that any δ with S (δ) = S (γ) does not belong to I. Thus, there is an one-to-one correspondence between nodes in I and subsets in S (I) and hence $i (Γ_{s} (V)) = | I | = | S (I) | = (\begin{matrix} n \\ ⌊ n / 2 ⌋ \end{matrix}) .$ □

In [15], Theorem 4.5, it is proved that the independence number of Γ (V) is n, whereas the independence number of Γ_s (V) is $(\begin{matrix} n \\ ⌊ n / 2 ⌋ \end{matrix})$ . As Γ_s (V) is a spanning subgraph of Γ (V), the independence number of Γ_s (V) is greater than Γ (V).

Theorem 2.4. Let V and W be two vector spaces defined over the field F with basis $B$ and $B^{'}$ respectively. Then V and W are isomorphic as vector spaces if and only if $Γ_{s} (V_{B})$ and $Γ_{s} (W_{B^{'}})$ are isomorphic as graphs.

Proof. Obviously, if V and W are isomorphic, then the corresponding graphs $Γ_{s} (V_{B})$ and $Γ_{s} (W_{B^{'}})$ are isomorphic (the proof is similar as that of Theorem 2.1). As far as the converse part is concern, let $Γ_{s} (V_{B})$ and $Γ_{s} (W_{B^{'}})$ be isomorphic. Let dim (V) = n and dim (W) = m. Then, the independence numbers of $Γ_{s} (V_{B})$ and $Γ_{s} (W_{B^{'}})$ are $(\begin{matrix} n \\ ⌊ n / 2 ⌋ \end{matrix})$ and $(\begin{matrix} m \\ ⌊ m / 2 ⌋ \end{matrix})$ respectively cf. Theorem 2.3. Nevertheless, as the two graphs are isomorphic, we have $(\begin{matrix} n \\ ⌊ n / 2 ⌋ \end{matrix})$ = $(\begin{matrix} m \\ ⌊ m / 2 ⌋ \end{matrix})$ . As the function f (n) = $(\begin{matrix} n \\ ⌊ n / 2 ⌋ \end{matrix})$ is injective (See Theorem 5.1 in Appendix), we have n = m. Thus, V and W being defined over the field F, therefore, the vector spaces are isomorphic.□

2.2 The clique and chromatic numbers

Lemma 2.3. For any clique C in Γ_s (V), {S (γ) : γ ∈ C} forms a chain of subsets of {1, 2, …, n}.

Proof. Since C is a clique, for any two γ, δ ∈ Γ_s (V), either S (γ) ⊆ S (δ) or S (δ) ⊆ S (γ). Thus, the skeleton of any two elements in C are comparable and hence the lemma. □

Lemma 2.4. If M is a maximal clique in Γ_s (V) and γ ∈ M, then {δ ∈ V : S (γ) = S (δ)} ⊆ M.

Proof. Since M is a maximal clique and S (γ) = S (δ). Thus, δ is adjacent to those elements to which γ is adjacent.□

Theorem 2.5. If $M = \cup_{i = 1}^{n} V_{i},$ where $V_{i} = {γ \in V : S_{B} (γ) = {γ_{1}, γ_{2}, \dots, γ_{i}}},$ for i = 1, 2, …, n. Then, $M$ is a maximal clique in Γ_s (V).

Proof. Since ${S (γ) : γ \in M}$ is a chain, it is clear that $M$ is a clique in Γ_s (V). If possible, let $M$ be a clique which is not maximal. Then there exist a non-zero vector $\tilde{γ} \in V \ M$ such that $M \cup {\tilde{γ}}$ is a clique. Since $\tilde{γ} \notin M$ , therefore $\tilde{γ} \notin V_{i}$ for all i ∈ {1, 2, …, n}, i.e., there exist a j ∈ {2, 3, …, n} such that $γ_{j} \in S (\tilde{γ})$ but $γ_{j - 1} \notin S (\tilde{γ})$ . Then, $\tilde{γ}$ is not adjacent to the vectors in V_j-1 as $S (\tilde{γ})$ does not contain γ_j-1 and if γ ∈ V_j-1 then S (γ) does not contain γ_j. This contradicts that $M \cup {\tilde{γ}}$ is a clique and hence, $M$ is a maximal clique.

Theorem 2.6. If the base field F is finite with p elements, then the clique number ω (Γ_s (V)) is $| M | = \frac{(p - 1) [(p - 1)^{n} - 1]}{(p - 2)}$

Proof. First, we find the number of elements in $M$ . As $M = \cup_{i = 1}^{n} V_{i}$ and V_i∩ V_j = ∅, we have $| M | = \sum_{i = 1}^{n} | V_{i} | = (p - 1) + (p - 1)^{2} + \dots + (p - 1)^{n}$ , i.e., $| M | = \frac{(p - 1) [(p - 1)^{n} - 1]}{(p - 2)} .$

To prove that $ω (Γ_{s} (V)) = | M |$ , let us consider a maximal clique M′ in Γ_s (V). Then {S (γ) : γ ∈ M′} forms a chain of subsets of {1, 2, …, n}. As there are finitely many subsets of {1, 2, …, n}, we choose exactly one vector δ_i from M′ corresponding to each distinct subset in {S (γ) : γ ∈ M′} such that for any γ ∈ M′, exactly one δ_j is chosen from M′ such that S (γ) = S (δ_j) to get a finite chain of subsets of the form $S (δ_{1}) ⊊ S (δ_{2}) ⊊ \dots ⊊ S (δ_{t}) .$ As all the inclusion in the above chain are proper and S (δ_i) ⊂ {1, 2, …, n} for all i ∈ {1, 2, …, t}, we have 1 ≤ |S (δ₁) | < |S (δ₂) | < ⋯ < |S (δ_t) | ≤ n and hence t ≤ n. Moreover, as M′ is a maximal clique, V (δ_i) = {γ ∈ V : S (γ) = S (δ_i)} ⊆ M. On the other hand, as {S (δ₁) , …, S (δ_t)} is the entire collection of skeletons of elements in M′, we have $M^{'} = \cup_{i = 1}^{t} V (δ_{i})$ . Thus, $| M^{'} | = \sum_{i = 1}^{t} | V (δ_{i}) | \leq \sum_{i = 1}^{n} | V_{i} | = | M | .$ □

Lemma 2.5. There exists a graph homomorphism from Γ_s (V) onto $M$ .

Proof. We construct a map $φ : Γ_{s} (V) \to M$ as follows: Let γ = c₁γ₁ + c₂γ₂ + ⋯ + c_nγ_n be the unique representation of a non-null vector γ in a vector space V with respect to the ordered basis $B = {γ_{1}, γ_{2}, \dots, γ_{n}}$ . Let {c_{i
₁}, c_{i
₂}, …, c_{i
_t}} be the non-zero elements of {c₁, c₂, …, c_n} with i₁ < i₂ < ⋯ < i_t and 1 ≤ t ≤ n. Define $φ : Γ_{s} (V) \to M$ by $\begin{matrix} φ (γ) & = φ (c_{1} γ_{1} + c_{2} γ_{2} + \dots + c_{n} γ_{n}) \\ = c_{i_{1}} γ_{1} + c_{i_{2}} γ_{2} + \dots + c_{i_{t}} γ_{t} \end{matrix}$ $i . e ., (c_{1}, c_{2}, \dots, c_{n}) \mapsto (c_{i_{1}}, c_{i_{2}}, \dots, c_{i_{t}}, 0, \dots, 0)$

Clearly, φ is well-defined, i.e., it maps all non-null vectors into $M$ . It is also to be noted that φ is the identity map when restricted on $M$ , i.e., φ (γ) = γ, for all $γ \in M$ . Thus, φ is an onto map.

To show that φ is a graph homomorphism, we need to show that γ ∼ δ ⇒ φ (γ) ∼ φ (δ). For this, we consider three separate cases:

Case 1: [ $γ, δ \in M$ ] Since φ is the identity map on $M$ , we have γ ∼ δ ⇒ φ (γ) ∼ φ (δ).

Case 2: [ $γ \in M, δ \in Γ_{s} (V) \ M$ ] Since $δ \notin M$ , there exists some j such that c_j ≠ 0 but c_j-1 = 0. Thus, S (γ) ≠ S (δ). Now as γ ∼ δ, either S (γ) ⊊ S (δ) or S (δ) ⊊ S (γ).

Case 2a: [S (γ) ⊊ S (δ)] Let S (γ) = {γ₁, γ₂, …, γ_i}. Since, S (γ) is properly contained in S (δ), there exists k > i such that S (δ) ⊇ {γ₁, γ₂, …, γ_i, γ_k}. Thus, by definition of φ, we have S (φ (δ)) ⊇ {γ₁, γ₂, …, γ_i, γ_i+1} and S (φ (γ)) = S (γ) = {γ₁, γ₂, …, γ_i} and hence S (φ (δ)) ⊃ S (φ (γ)) i.e., φ (γ) ∼ φ (δ).

Case 2b: [S (γ) ⊋ S (δ)] Let S (γ) = {γ₁, γ₂, …, γ_i}. Since S (δ) is properly contained in S (γ), the number of non-zero coefficients in the representation of δ is less than i and hence S (φ (δ)) ⊊ {γ₁, γ₂, …, γ_i} and S (φ (γ)) = S (γ) = {γ₁, γ₂, …, γ_i}. Thus, S (φ (δ)) ⊂ S (φ (γ)) i.e., φ (γ) ∼ φ (δ).

Case 3: [ $γ, δ \in Γ_{s} (V) \ M$ ] Since γ ∼ δ, either S (γ) ⊆ S (δ) or S (δ) ⊆ S (γ). Without loss of generality, we assume that S (γ) ⊆ S (δ).

Case 3a: [S (γ) = S (δ)] Let S (γ) = S (δ) = {γ_{i
₁}, γ_{i
₂}, …, γ_{i
_t}} and let γ = c₁γ_{i
₁} + c₂γ_{i
₂} + ⋯ + c_tγ_{i
_t} and δ = d₁γ_{i
₁} + d₂γ_{i
₂} + ⋯ + d_tγ_{i
_t}. Since γ ≠ δ, there exists k ∈ {1, 2, …, t} such that c_k ≠ d_k. Now, φ (γ) = c₁γ₁ + c₂γ₂ + ⋯ + c_tγ_t and φ (δ) = d₁γ₁ + d₂γ₂ + ⋯ + d_tγ_t. Thus, φ (γ) ≠ φ (δ) but S (φ (γ)) = S (φ (δ)) and hence φ (γ) ∼ φ (δ).

Case 3b: [S (γ) ⊊ S (δ)] Let S (γ) = {γ_{i
₁}, γ_{i
₂}, …, γ_{i
_t}}. Since S (γ) is properly contained in S (δ), the number of non-zero coefficients in the representation of δ is greater than t. Hence by definition of φ, S (φ (δ)) ⊋ {γ₁, γ₂, …, γ_t} and S (φ (γ)) = {γ₁, γ₂, …, γ_t}. Thus, S (φ (δ)) ⊃ S (φ (γ)) i.e., φ (γ) ∼ φ (δ).

Combining all the three cases, φ is a graph homomorphism and hence the theorem follows. □

Theorem 2.7. Let the dimension of V be an n defined over F with p elements. Then, chromatic number of Γ_s (V) is equal to $\frac{(p - 1) [(p - 1)^{n} - 1]}{(p - 2)}$

Proof. By Theorem 2.6, the clique number ω (Γ_s (V)) is $\frac{(p - 1) [(p - 1)^{n} - 1]}{(p - 2)} .$ As the clique number of a graph is equal or less than its chromatic number, we have ω (Γ_s (V)) ≤ χ (Γ_s (V)). There exists a graph homomorphism from Γ_s (V) onto $M$ cf. Lemma 2.2, in particular, Γ_s (V) is $M$ -colourable, and hence the chromatic number $χ (Γ_{s} (V)) \leq | M |$ . Thus, we have $ω (Γ_{s} (V)) \leq χ (Γ_{s} (V)) \leq | M | = ω (Γ_{s} (V)),$ $i . e ., χ (Γ_{s} (V)) = \frac{(p - 1) [(p - 1)^{n} - 1]}{(p - 2)} .$ □

Due to Theorem 2.6 and 2.7, the clique number and the chromatic number of Γ_s (V) are the same. In [25], Corollary 5 and 6, the authors have shown that the clique number and the chromatic number of Γ (V) are the same. In other words, both Γ (V) and Γ_s (V) are weakly perfect. The graph Γ_s (V), being a spanning subgraph of Γ (V), has smaller chromatic and clique number than that of Γ (V).

3 Other results

In this section, we find the degree of a node in Γ_s (V) for the base field F with p elements and hence show that Γ_s (V) is never Eulerian. Also, we find the size of Γ_s (V).

Theorem 3.1. For a vector space V defined over a finite field F with p elements and Γ_s (V) be its associated graph with respect to a basis $B = {γ_{1}, γ_{2}, \dots, γ_{n}}$ . Then, the degree of the node γ = c₁γ_{i
₁} + c₂γ_{i
₂} + ⋯ + c_kγ_{i
_k} is (p - 1) ^k [p^n-k - 1] + p^k - 2, where c₁c₂ ⋯ c_k ≠ 0.

Proof. Clearly S (γ) = {γ_{i
₁}, γ_{i
₂}, …, γ_{i
_k}}. Let δ = d₁γ₁ + d₂γ₂ + ⋯ + d_nγ_n be adjacent to γ. Therefore, either S (δ) ⊆ {γ_{i
₁}, γ_{i
₂}, …, γ_{i
_k}} or S (δ) ⊋ {γ_{i
₁}, γ_{i
₂}, …, γ_{i
_k}}.

The number of δ’s (other than γ) with S (δ) ⊆ {γ_{i
₁}, γ_{i
₂}, …, γ_{i
_k}} is $\begin{matrix} (\begin{matrix} k \\ 1 \end{matrix}) (p - 1) + (\begin{matrix} k \\ 2 \end{matrix}) (p - 1)^{2} + \dots \\ + (\begin{matrix} k \\ k \end{matrix}) (p - 1)^{k} - 1 = p^{k} - 2, \end{matrix}$ and the number of δ’s with S (δ) ⊋ {γ_{i
₁}, γ_{i
₂}, …, γ_{i
_k}} is $\begin{matrix} (\begin{matrix} n - k \\ 1 \end{matrix}) (p - 1)^{k + 1} + (\begin{matrix} n - k \\ 2 \end{matrix}) (p - 1)^{k + 2} + \dots \\ + (\begin{matrix} n - k \\ n - k \end{matrix}) (p - 1)^{n} \\ = (p - 1)^{k} [(\begin{matrix} n - k \\ 1 \end{matrix}) (p - 1) + (\begin{matrix} n - k \\ 2 \end{matrix}) (p - 1)^{2} \\ + \dots + (\begin{matrix} n - k \\ n - k \end{matrix}) (p - 1)^{n - k}] \\ = (p - 1)^{k} [(p - 1 + 1)^{n - k} - 1] \\ = (p - 1)^{k} [p^{n - k} - 1] . \end{matrix}$ Therefore, deg (γ) = (p - 1) ^k [p^n-k - 1] + p^k - 2.

□

As a consequence of Theorem 3.1, we have

Corollary 3.1. The maximum degree of Γ_s (V) is Δ = pⁿ - 2.

Corollary 3.2. Γ_s (V) is never Eulerian.

Proof. If p is odd, then Γ_s (V) is not Eulerian as Δ = pⁿ - 2 is odd. From Theorem 3.1, we see that degree of the node γ = c₁γ_{i
₁} + c₂γ_{i
₂} + ⋯ + c_kγ_{i
_k} is (p - 1) ^k [p^n-k - 1] + p^k - 2, is odd if k ≠ n and p is even. Thus, the graph is never Eulerian. □

The following result computes the size (number of arcs) of the graph Γ_s (V).

Theorem 3.2. The size of the graph is $\frac{1}{2} [2 (p^{2} - p + 1)^{n} - (p^{2} - 2 p + 2)^{n} - 3 p^{n} + 2]$ .

Proof. Let m be the number of arcs. Then 2m = degree-sum of the nodes. Hence, using Theorem 3.1,

$2 m = \sum_{k = 1}^{n} (\begin{matrix} n \\ k \end{matrix}) (p - 1)^{k} {(p - 1)^{k} (p^{n - k} - 1) + p^{k} - 2}$ $= \sum_{k = 1}^{n} (\begin{matrix} n \\ k \end{matrix}) (p - 1)^{2 k} p^{n - k} - \sum_{k = 1}^{n} (\begin{matrix} n \\ k \end{matrix}) (p - 1)^{2 k}$ $+ \sum_{k = 1}^{n} (\begin{matrix} n \\ k \end{matrix}) p^{k} (p - 1)^{k} - 2 \sum_{k = 1}^{n} (\begin{matrix} n \\ k \end{matrix}) (p - 1)^{k}$ $= {(p^{2} - p + 1)^{n} - p^{n}} - {(p^{2} - 2 p + 2)^{n} - 1}$ $+ {(p^{2} - p + 1)^{n} - 1} - 2 {p^{n} - 1}$ $= 2 (p^{2} - p + 1)^{n} - (p^{2} - 2 p + 2)^{n} - 3 p^{n} + 2 .$

Thus, the theorem follows.

4 Twin preserving subgraph

We give the following key definition of this paper.

Definition 4.1. A connected spanning subgraph Γ_s of a graph Γ is called twin preserving spanning subgraph (TPS-subgraph) if two nodes s and t are twins in Γ if and only if they are twins in Γ_s.

A path P_n with n nodes has no proper TPS-subgraph. A cycle C_n for n > 4 has n proper TPS-subgraphs, each isomorphic to a path P_n. Note that, not every connected spanning subgraph is a TPS-subgraph. For example, the complete graph C₃ has three isomorphic connected spanning subgraphs and no one is TPS-subgraph.

Theorem 4.1. [1] Let $B = {γ_{1}, γ_{2}, \dots, γ_{n}}$ . Then, the following hold

a) dim_Γ(V)= 1, for p = 2 and n = 2;

b) dim_Γ(V) = n, for p = 2 and n ≥ 3; and

c) $\dim_{Γ (V)} = \sum_{k = 1}^{n} (\begin{matrix} n \\ k \end{matrix}) ((p - 1)^{k} - 1)$ , for p ≥ 3

Lemma 4.1. [22] For two twin nodes s, t and a resolving set W in a connected graph Γ, at least s ∈ W or t ∈ W. Moreover, if t ∈ W and s ∉ W, then (W \ {t}) ∪ {s} is also a resolving set for Γ.

Below, we give the main result of this paper.

Theorem 4.2. Let $B = {γ_{1}, γ_{2}, \dots, γ_{n}}$ . Then, the following hold

a) dim_{Γ_s(V)}= 1, for p = 2 and n = 2;

b) dim_{Γ_s(V)} = n, for p = 2 and n ≥ 3; and

c) $\dim_{Γ_{s} (V)} = \sum_{k = 1}^{n} (\begin{matrix} n \\ k \end{matrix}) ((p - 1)^{k} - 1)$ , for p ≥ 3

Proof. a) The node γ₁ resolves the two nodes γ₂ and γ₁ + γ₂. Therefore, B (Γ_s (V)) (metric basis) = {γ₁}.

b) For p = 2, a twin-set Cl_t has length 1 for all nodes t. The set $B$ is a resolving set because some $γ_{i} \in B$ can resolve any two nodes. To get that $B$ is a B (Γ_s (V)), it is enough to show: dim_{Γ_s(V)} ≥ n. Let the node u has $B$ as a skeleton, i.e., u = γ₁ + γ₂ + ⋯ + γ_n and X = {t₁, t₂, …, t_n}, where $S_{t_{i}} = B \ {γ_{i}}$ for 1 ≤ i ≤ n.

Case 1 Let U be a B (Γ_s (V)) and assume that u ∉ U. Then, only the node γ_i + y (where y is some other node) can resolve the node u and a node t_i ∈ X because d (u, t) = d (t_i, t) for all t ≠ γ_i + y. As a compulsion, U must contain, at least, one node from each pair (γ_i + y, t_i). The number of such pairs is n, hence dim_{Γ_s(V)} ≥ n.

Case 2 Assume u ∈ U. Then, any two nodes t_j, t_k ∈ X can only be resolved either by y = γ_j + y₁ or by z = γ_k + z₁ for some nodes y and z, because d (t_j, t) = d (t_k, t) for t ≠ γ_j + y, γ_k + z. Therefore, at least, one node from each pair of type (y, t_i) out of n - 1 pairs must belong to U along with the element u. Therefore, U must have, at least, n elements.

c) We have p ≥ 3 and so ∣Cl_t ∣ ≥2 for all t ∈ V, further, all twin-sets are non-singleton. Due to Lemma4.1, a resolving set contains all nodes of a twin-set Cl_t of length k for 1 ≤ k ≤ n, except one node; there are (p - 1) ^k nodes in Cl_t of length k; and the number of distinct twin-sets for a fixed k is $(\begin{matrix} n \\ k \end{matrix})$ . Therefore, the minimum number of nodes contained in a resolving set W is $\sum_{k = 1}^{n} (\begin{matrix} n \\ k \end{matrix}) ((p - 1)^{k} - 1)$ . The number of distinct twin-sets of length 1 is n, and W contains the set D = {a₁γ₁, a₂γ₂, …, a_nγ_n} for a_i ∈ F cf. Lemma4.1. The set D can resolve any two nodes with distinct skeletons. Therefore, the minimum (smallest) size of W is $\sum_{k = 1}^{n} (\begin{matrix} n \\ k \end{matrix}) ((p - 1)^{k} - 1)$ .

□

The TPS-subgraph Γ_s (V) is a metric-dimension preserving subgraph of Γ (V) cf. Theorem4.1 and Theorem 4.2.

Note that the metric-dimension is not always preserved by every TPS-subgraph of a simple graph. For example, a path P_n as TPS-subgraph of a cycle C_n has different metric-dimension than C_n.

5 Discussion and future directions

We can see in Figure 2 that the nodes v₁ and v₂ are true twins in the original graph, while false twins in the TPS-subgraph. Therefore, it will be interesting and non-trivial to define True TPS-subgraph and False TPS-subgraph: a TPS-subgraph is called true if two nodes s and t are true twins in Γ if and only if they are true twins in Γ_s. Similarly, a TPS-subgraph is called false if two nodes s and t are false twins in Γ if and only if they are false twins in Γ_s. In the future, we intend to investigate these TPS-subgraphs for different families of graphs. The Ve-degree and Ev-degree based topological indices introduced in[7], depend on twin nodes. It will be important to study the relationship of these topological indices for graphs with their TPS-subgraphs. This novel tool can be used to explore graph-theoretic properties related to other distance based invariants as well.

Fig. 2

A graph and its TPS-subgraph.

There are various other questions that need further investigation. For example, the following question does make sense.

Question. What are the properties of a simple graph which are always preserved by all of its TPS-subgraphs?

Footnotes

Appendix

Theorem 5.1. The function $f : ℕ \to ℕ$ given by $f (n) = (\begin{matrix} n \\ ⌊ n / 2 ⌋ \end{matrix}) is injective .$

Proof. Consider the ratio $\begin{matrix} \frac{f (n + 1)}{f (n)} = \frac{(\begin{matrix} n + 1 \\ ⌊ (n + 1) / 2 ⌋ \end{matrix})}{(\begin{matrix} n \\ ⌊ n / 2 ⌋ \end{matrix})} \\ = \frac{| \underline{n + 1}}{| \underline{⌊ (n + 1) / 2 ⌋} \cdot | \underline{⌈ (n + 1) / 2 ⌉}} \cdot \frac{| \underline{⌊ n / 2 ⌋} \cdot | \underline{⌈ n / 2 ⌉}}{| \underline{n}} \end{matrix}$

Case 1: If n is even, i.e., n = 2m. Then $\frac{f (n + 1)}{f (n)} = \frac{| \underline{2 m + 1}}{| \underline{m} \cdot | \underline{m + 1}} \cdot \frac{| \underline{m} \cdot | \underline{m}}{| \underline{2 m}} = \frac{2 m + 1}{m + 1} > 1$

Case 2: If n is odd, i.e., n = 2m + 1. Then $\frac{f (n + 1)}{f (n)} = \frac{| \underline{2 m + 2}}{| \underline{m + 1} \cdot | \underline{m + 1}} \cdot \frac{| \underline{m} \cdot | \underline{m + 1}}{| \underline{2 m + 1}} = 2 > 1$

As in both the cases, $\frac{f (n + 1)}{f (n)}$ is greater than, we conclude that f is a strictly increasing function and hence f is injective. □

References

Ali

, Bokhary

S.A.

, Wahid

and Abbas

, On Resolvability of a Graph Associated to a Finite Vector Space, J Algebra Appl 19(2) (2019), 1950029 (10 pages).

Amini

, Amini

, Momtahan

and Haghighi

M.H.S

, On a Graph of Ideals, Acta Math Hungar 134(3) (2012), 369–384.

Anderson

D.F.

and Livingston

P.S.

, The zero-divisor graph of a commutative ring, J Algebra 217 (1999), 434–447.

Badawi

, On the Dot Product Graph of a Commutative Ring, Comm Algebra 43(1) (2015), 43–50.

Beck

, Coloring of commutative rings, J Algebra 116 (1988), 208–226.

Buczkowski

P.S.

, Chartrand

, Poisson

and Zhang

, On k-dimensional graphs and their bases, Period Math Hungar 46 (2003), 9–15.

Cancan

, On Ev-degree and Ve-degree topological properties of Tickysim spiking neural network, Comput Intell Neurosci 8 (2019), 11–31.

Caley

, Desiderata and suggestions: No. 2. The Theory of groups: graphical representation, Am J Math 1(2) (1878), 174–176.

Cameron

P.J.

and Ghosh

, The power graph of a finite group, Discrete Math 311 (2011), 1220–1222.

10.

Chakrabarty

, Ghosh

, Mukherjee

T.K.

and Sen

M.K.

, Intersection graphs of ideals of rings, Discrete Math 309(17) (2009), 5381–5392.

11.

Chakrabarty

, Ghosh

and Sen

M.K.

, Undirected power graphs of semigroups, Semigroup Forum 78 (2009), 410–426.

12.

Chartrand

, Eroh

, Johnson

A.M.

and Oellermann

R.O.

, Resolvability in graphs and metric dimension of a graph, Discrete Appl Math 105 (2000), 99–133.

13.

Chartrand

, Salehi

and Zhang

, The partition dimension of a graph, Aequationes Math 59 (2000), 45–54.

14.

Charttrand

and Zhang

, The theory and application of resolvability in graphs, A Survey, Congr Numer 160 (2003), 47–68.

15.

Das

, Non-zero component graph of a finite dimensional vector space, Comm Algebra 44(9) (2016), 3918–3926.

16.

Das

, Non-zero component union graph of a finite dimensional vector space, Linear Multilinear Algebra 65(6) (2017), 1276–1287.

17.

Das

, Subspace inclusion graph of a vector space, Comm Algebra 44(11) (2016), 4724–4731.

18.

Das

, On subspace inclusion graph of a vector space, Linear Multilinear Algebra 66(3) (2018), 554–564.

19.

Das

, On non-zero component graph of vector spaces over finite fields, J Algebra Appl 16 (2016), 1750007.

20.

Harary

and Melter

R.A.

, On the metric dimension of a graph, Ars Comb 2 (1976), 191–195.

21.

Henning

M.A.

, and Oellermann, Metric-locationg-dominating sets in graphs, Ars Comb 73 (2004), 129–141.

22.

Hernando

, Mora

, Pelaya

I.M.

, Seara

and Wood

D.R.

, Extremal graph theory for metric dimension and diameter, Electron Notes Discrete Math 29 (2007), 339–343.

23.

Rad

N.J.

and Jafari

S.H.

, Results on the intersection graphs of subspaces of a vector space, http://arxiv.org/abs/1105.0803v1

24.

Maji

and Ghorai

, A novel graph invariant: The third leap Zagreb index under several graph operations, Discret Math Algorithms Appl 11(05) (2019), 1950054.

25.

Nikandish

, Maimani

H.R.

and Khaksari

, Coloring of a non-zero component graph associated with a finite dimensional vector space, J Algebra Appl 16 (2017), 1750173.

26.

Plesnik

, Critical graphs of given diameter, Acta Fac Rerum Natur Univ Comenian Math 30 (1975), 71–93.

27.

Riaza

, Twin subgraphs and core-semiperiphery-periphery structures, Complexity Article ID 2547270 (2018), 71–93.

28.

Sebö

and Tannier

, On metric generators of graph, Math Oper Res 29(2) (2004), 383–393.

29.

Slater

P.J.

, Dominating and reference sets in graphs, J Math Phys Sci 22 (1988), 445–455.

30.

Slater

P.J.

, Leaves of trees, Congress Numer 14 (1975), 549–559.

31.

Sperner

, Ein Satz "uber Untermenger einer endlichen Menge, Math Z 27 (1928), 544–548.

32.

Talebi

, Esmaeilifar

M.S.

and Azizpour

, A kind of intersection graph of vector space, J Discrete Math Sci Cryptogr 12(6) (2009), 681–689.

33.

West

D.B.

, Introduction to Graph Theory, Prentice Hall, 2001.