A Study on the Inj-Equitable Graph of a Graph

Hanaa Alashwali^1*, Ahmad N. Alkenani¹, A. Saleh², Najat Muthana¹

¹Department of Mathematics, King Abdulaziz University, Jeddah, KSA.
²Department of sMathematics, Jeddah University, Jeddah, KSA.

DOI: 10.4236/am.2018.93020                

Abstract

For any graph G, the Inj-equitable graph of a graph G, denoted by IE (G) , is the graph with the same vertices as G and for any two adjacent vertices u and v in IE (G), ≤ 1, where for any vertex w∈V (G) , deg_in (w) = . In this paper, Inj-equitable graphs of some graphs are obtained, and some properties and results are established. Moreover, complete Inj-equitable graph and the Inj-equitable graph are defined.

Keywords

Domination, Injective Equitable Graph, Equitable Matrix, Injective Matrix

1. Introduction

We consider only finite undirected graphs $G=\left(V\mathrm{,}E\right)$ without loops and multiple edges. $\langle X\rangle$ will denote the subgraph of G induced by a set of vertices X. For any vertex $v\in V\left(G\right)$ the open neighborhood of v is the set $N\left(v\right)=\left\{u\in V\left(G\right)\mathrm{<mo>\; :\; </mo>}uv\in E\right\}$ . The closed neighborhood of v is $N\left[v\right]=N\left(v\right)\cup v$ . The degree of a vertex v in G is $deg\left(v\right)=\left|N\left(v\right)\right|$ . $\Delta \left(G\right)$ and $\delta \left(G\right)$ are the maximum and minimum vertex degree of G respectively. The distance $d\left(u\mathrm{,}v\right)$ between any two vertices u and v in a graph G is the number of the edges in a shortest path. The eccentricity of a vertex u in a connected graph G is $e\left(u\right)=max\left\{d\left(u\mathrm{,}v\right)\mathrm{,}v\in V\right\}$ . The diameter of G is the value of the greatest eccentricity, and the radius of G is the value of the smallest eccentricity. The clique number of G, denoted by $\omega \left(G\right)$ , is the order of the maximal complete subgraph of G. The Inj-neighborhood of a vertex $u\in V\left(G\right)$ denoted by $N_{in}\left(u\right)$ is defined as $N_{in}\left(u\right)=\left\{v\in V\left(G\right)\mathrm{<mo>\; :\; </mo>}\left|\Gamma \left(u\mathrm{,}v\right)\right|\ge 1\right\}$ , where $\left|\Gamma \left(u\mathrm{,}v\right)\right|$ is the number of common neighborhood between the vertices u and v. The cardinality of $N_{in}\left(u\right)$ is called injective degree of the vertex u and is denoted by ${{\displaystyle deg}}_{in}\left(u\right)$ in G. The corona product $G\circ H$ is obtained by taking one copy of G and $\left|V\left(G\right)\right|$ copies of H and by joining each vertex of the i-th copy of H to the i-th vertex of G, where $1\le i\le \left|V\left(G\right)\right|$ . The cartesian product $G\times H$ is a graph with vertex set $V\left(G\right)\times V\left(H\right)$ and edge set $E\left(G\times H\right)=\{\left(\left(u\mathrm{,}{u}^{\prime }\right)\mathrm{,}\left(v\mathrm{,}{v}^{\prime }\right)\right)\mathrm{<mo>\; :\; </mo>}u=v$ and $\left(u^{\prime }\mathrm{,}{v}^{\prime }\right)\in E\left(H\right)$ , or $u^{\prime }=v^{\prime }$ and $\left(u\mathrm{,}v\right)\in E\left(G\right)\}$ . For more terminologies and notations, we refer the reader to [1] [2] [3] and [4] .

The common neighborhood graph (congraph) of a graph G, denoted by $con\left(G\right)$ , is the graph with vertex set $\left\{v_1\mathrm{,}{v}_2\mathrm{,}\cdots \mathrm{,}{v}_n\right\}$ , in which two vertices are adjacent if and only if they have at least one common neighbor in the graph G [5] . The equitable graph of a graph G, denoted by $G^e$ , is the graph with vertex set $V\left(G\right)$ and two vertices u and v are adjacent if and only if $\left|deg\left(u\right)-deg\left(v\right)\right|\le 1$ [6] .

2. IE-Graph of a Graph

The Inj-equitable dominating sets on graphs which introduced in [7] motivated us to define two new graphs: the IE-graph of a graph and the IE-graph. In this section, we define the Inj-equitable graph of a graph and study some properties of this graph. Also, the injective equitable graph of some graph’s families are found.

Definition 1 Let $G=\left(V\mathrm{,}E\right)$ be a graph. The injective equitable (Inj-equitable) graph of a graph G, denoted by $IE\left(G\right)$ , is defined as the graph with the same vertices as G and two vertices u and v are adjacent in $IE\left(G\right)$ if

$\left|de{g}_{in}\left(u\right)-de{g}_{in}\left(v\right)\right|\le 1.$

Example 2 Let G be a graph as in Figure 1. Then, $IE\left(G\right)\cong K_7\cup K_5\cup K_2$ .

The Inj-equitable graph of some known graphs are given in the following observation:

Observation 3

(i) For any path $P_n$ with n vertices, $IE\left(P_n\right)\cong K_n$ .

(ii) For any cycle $C_n$ with n vertices, $IE\left(C_n\right)\cong K_n$ .

(iii) For any complete graph $K_n$ , $IE\left({\bar{K}}_n\right)=IE\left(K_n\right)=K_n$ .

Proposition 4 For any complete bipartite graph $K_{r\mathrm{,}s}$ ,

$IE\left(K_{r\mathrm{,}s}\right)\cong \{\begin{array}{ll}{K}_{r+s}\hfill & \text{if}\left|r-s\right|\le \mathrm{1\; <mo>\; ;\; </mo>}\hfill \\ K_r\cup K_s\hfill & \text{otherwise}\mathrm{.}\hfill \end{array}$

Proof. Let $G\cong K_{r\mathrm{,}s}$ be a complete bipartite graph with partite sets A and B such that $\left|A\right|=r$ , $\left|B\right|=s$ . Clearly for any vertex v from A, ${{\displaystyle deg}}_{in}\left(v\right)=r-1$ and for any vertex u from B, $de{g}_{in}\left(u\right)=s-1$ . Therefore, for any two vertices u and v in $K_{r\mathrm{,}s}$ , $\left|de{g}_{in}\left(u\right)-de{g}_{in}\left(v\right)\right|=\left|r-s\right|$ . If $\left|r-s\right|\le 1$ , then $IE\left(K_{r\mathrm{,}s}\right)=K_{r+s}$ . Otherwise, $IE\left(K_{r\mathrm{,}s}\right)=K_r\cup K_s$ .

We will generalize Proposition 4 in the following result.

Proposition 5 For any multipartite graph $K_{n_1\mathrm{,}{n}_2\mathrm{,}\cdots ,n_m}$ , where $m\ge 3$ ,

Figure 1. A graph G.

$IE\left(K_{n_1\mathrm{,}{n}_2\mathrm{,}\cdots ,n_m}\right)=K_r$ , where $r={\displaystyle {\sum }_{i=1}^m}{n}_i$ .

Proof. Let G be a multipartite graph $K_{n_1\mathrm{,}{n}_2\mathrm{,}\cdots ,n_m}$ where $m\ge 3$ . Then for every vertex u in G, $de{g}_{in}\left(u\right)=n_1+n_2+\cdots +n_m-1$ . Hence, $IE\left(K_{n_1\mathrm{,}{n}_2\mathrm{,}\cdots ,n_m}\right)=K_r$ , where $r={\displaystyle {\sum }_{i=1}^m}{n}_i$ .

Bi-star graph is the graph obtained by joining the apex vertices of two copies of star $K_{\mathrm{1,}n}$ .

Proposition 6 For any bi-star graph $B\left(s\mathrm{,}t\right)$ ,

$IE\left(B\left(s\mathrm{,}t\right)\right)=\{\begin{array}{ll}{K}_{s+t+2}\hfill & \text{if}\left|s-t\right|\le \mathrm{1\; <mo>\; ;\; </mo>}\hfill \\ K_{s+1}\cup K_{t+1}\hfill & \text{otherwise}\mathrm{.}\hfill \end{array}$

Proof. Let $G\cong B\left(s\mathrm{,}t\right)$ be a bi-star graph labeling as in Figure 2. Therefore, $de{g}_{in}\left(u\right)=t$ , $de{g}_{in}\left(v\right)=s$ , for $i=1,2,\cdots ,s$ , ${{\displaystyle deg}}_{in}\left(u_i\right)=s$ and for $j=\mathrm{1,2,}\cdots ,t$ , $de{g}_{in}\left(v_j\right)=t$ . So, if $\left|s-t\right|\le 1$ , then $IE\left(B\left(s\mathrm{,}t\right)\right)=K_{s+t+2}$ . Otherwise, $IE\left(B\left(s\mathrm{,}t\right)\right)=K_{s+1}\cup K_{t+1}$ .

A firefly graph $F_{r\mathrm{,}s\mathrm{,}t}$ is a graph on $2r+2s+t+1$ vertices that consists of r triangles, s pendant paths of length 2 and t pendant edges sharing a common vertex.

Proposition 7 For any firefly graph $F_{r\mathrm{,}s\mathrm{,}t}$ , $r\ge \mathrm{1,}s\ge 1$ and $t\ge 1$ ,

$IE\left(F_{r\mathrm{,}s\mathrm{,}t}\right)=\{\begin{array}{ll}{K}_{2r+s+2}\cup K_s\hfill & \text{if}t=\mathrm{1\; <mo>\; ;\; </mo>}\hfill \\ K_{2r+s+2}\cup K_{\mathrm{1,}s+2}\cup K_s\hfill & \text{if}t=\mathrm{2\; <mo>\; ;\; </mo>}\hfill \\ K_{2r+s+t}\cup K_1\cup K_s\hfill & \text{if}t>2.\hfill \end{array}$

Proof. Let G be a firefly graph $F_{r\mathrm{,}s\mathrm{,}t}$ as in Figure 3, where $r\ge \mathrm{1,}s\ge 1$ and $t\ge 1$ . Let v be the center vertex, $v_i,i=1,2,\cdots ,2r$ be any vertex from the triangle other than v. $w_i,i=1,2,\cdots ,t$ be any end vertex in the pendant edge. $u_i$ and ${u^{\prime }}_i,i=1,2,\cdots ,s$ be any end vertex and internal vertex respectively in the pendant path. Then, $de{g}_{in}\left(v\right)=2r+s$ , $de{g}_{in}\left(v_i\right)=2r+s+t$ , $de{g}_{in}\left(w_i\right)=2r+s+t-1$ , $de{g}_{in}\left({u^{\prime }}_i\right)=2r+s+t-1$ and $de{g}_{in}\left(u_i\right)=1$ . There are three cases:

Case 1. Suppose that $t=1$ . Then, $\left|de{g}_{in}\left(v\right)-de{g}_{in}\left(v_i\right)\right|=1$ ,

$\left|de{g}_{in}\left(v\right)-de{g}_{in}\left(w_i\right)\right|=0$ , $\left|de{g}_{in}\left(v\right)-de{g}_{in}\left({u^{\prime }}_i\right)\right|=0$ ,

$\left|de{g}_{in}\left(v_i\right)-de{g}_{in}\left(w_i\right)\right|=1$ , $\left|de{g}_{in}\left(v_i\right)-de{g}_{in}\left({u^{\prime }}_i\right)\right|=1$ and

Figure 2. A bi-star graph.

Figure 3. A firefly graph.

$\left|de{g}_{in}\left(w_i\right)-de{g}_{in}\left({u^{\prime }}_i\right)\right|=0$ . Hence, $IE\left(F_{r\mathrm{,}s\mathrm{,}t}\right)\cong K_{2r+s+2}\cup K_s$ .

Case 2. Suppose that $t=2$ . Then, $\left|de{g}_{in}\left(v\right)-de{g}_{in}\left(w_i\right)\right|=1$ ,

$\left|de{g}_{in}\left(v\right)-de{g}_{in}\left({u^{\prime }}_i\right)\right|=1$ , $\left|de{g}_{in}\left(v_i\right)-de{g}_{in}\left(w_i\right)\right|=1$ ,

$\left|de{g}_{in}\left(v_i\right)-de{g}_{in}\left({u^{\prime }}_i\right)\right|=1$ and $\left|de{g}_{in}\left(w_i\right)-de{g}_{in}\left({u^{\prime }}_i\right)\right|=0$ .

Hence $IE\left(F_{r\mathrm{,}s\mathrm{,}t}\right)\cong K_{2r+s+2}\cup K_{\mathrm{1,}s+2}\cup K_s$ .

Case 3. Suppose that $t\le 2$ . Then, $\left|de{g}_{in}\left(v_i\right)-de{g}_{in}\left(w_i\right)\right|=1$ ,

$\left|de{g}_{in}\left(v_i\right)-de{g}_{in}\left({u^{\prime }}_i\right)\right|=1$ and $\left|de{g}_{in}\left(w_i\right)-de{g}_{in}\left({u^{\prime }}_i\right)\right|=0$ .

Hence $IE\left(F_{r\mathrm{,}s\mathrm{,}t}\right)\cong K_{2r+s+t}\cup K_1\cup K_s$ .

Definition 8 A complete chain graph denoted by $CC\left(n_1\mathrm{,}{s}_1\mathrm{,}{n}_2\mathrm{,}{s}_2\mathrm{,}\cdots \mathrm{,}{s}_{r-1}\mathrm{,}{n}_r\right)$ is a chain of complete graphs $K_{n_1},K_{n_2},\cdots ,K_{n_r}$ such that there are $s_i$ common vertices between $K_{n_i}$ and $K_{n_{i+1}}$ , for $i=1,2,\cdots ,r-1$ .

Proposition 9 Let G be a graph such that $G\cong P_m\times P_2$ . Then

$IE\left(G\right)=\{\begin{array}{ll}{K}_{2m}\hfill & \text{if}m\le \mathrm{4\; <mo>\; ;\; </mo>}\hfill \\ CC\left(\mathrm{8,4,2}m-4\right)\hfill & \text{if}m\ge 5.\hfill \end{array}$

Proof. Let G be a graph such that $G\cong P_m\times P_2$ . Then there are two cases:

Case 1. If $m\le 4$ , for all $v\in V\left(G\right)$ , either $de{g}_{in}\left(v\right)=2$ or $de{g}_{in}\left(v\right)=3$ . Therefore, for any two vertices u and v, $\left|de{g}_{in}\left(u\right)-de{g}_{in}\left(v\right)\right|\le 1$ . Hence, $IE\left(G\right)\cong K_{2m}$ .

Case 2. If $m\ge 5$ , there are 4 vertices with Inj-degree 2, 4 vertices with Inj-degree 3 and $2m-8$ vertices with Inj-degree 4. Therefore,

$IE\left(G\right)\cong CC\left(\mathrm{8,4,2}m-4\right)$ .

Proposition 10 Let G be a graph such that $G\cong P_m\times P_3$ , where $m\ge 4$ . Then

$IE\left(G\right)=\{\begin{array}{ll}CC\left(\mathrm{10,4,6}\right)\hfill & \text{if}m=\mathrm{4\; <mo>\; ;\; </mo>}\hfill \\ CC\left(\mathrm{10,4,2}m-\mathrm{2,2}m-\mathrm{6,3}m-10\right)\hfill & \text{if}m\ge 5.\hfill \end{array}$

Proof. Suppose that, $G\cong P_m\times P_3$ . Then we have two cases:

Case 1. If $m=4$ , then there are 6 vertices have Inj-degree 3, 4 vertices have Inj-degree 4 and 2 vertices have Inj-degree 5. Therefore, $IE\left(G\right)\cong CC\left(\mathrm{10,4,6}\right)$ .

Case 2. If $m\ge 5$ , then there are 6 vertices have Inj-degree 3, 4 vertices have Inj-degree 4, $2m-6$ vertices have Inj-degree 5 and $m-4$ vertices of degree 6. Therefore, $IE\left(G\right)\cong CC\left(\mathrm{10,4,2}m-\mathrm{2,2}m-\mathrm{6,3}m-10\right)$ .

Theorem 11 Let G be a graph such that $G\cong P_m\times P_n$ , where $m\mathrm{,}n\ge 5$ . Then $IE\left(G\right)\cong CC(\mathrm{12,8,2}m+2n-\mathrm{4,2}m+2n-\mathrm{12,2}m+2n-\mathrm{8,4,2}m+2n-\mathrm{8,2}m+2n-\mathrm{12,}$ $\left(n-2\right)\left(m-2\right))$ .

Proof. Suppose that $G\cong P_m\times P_n$ . Therefore, there are 4 vertices have Inj-degree 3, 8 vertices have Inj-degree 4, $2m+2n-12$ have Inj-degree 5, 4 vertices have Inj-degree 6, $2m+2n-12$ have Inj-degree 7 and $\left(n-4\right)\left(m-4\right)$ have Inj-degree 8. Hence $IE\left(P_m\times P_n\right)\cong CC(\mathrm{12,8,2}m+2n-\mathrm{4,2}m+2n-\mathrm{12,}$ $2m+2n-\mathrm{8,4,2}m+2n-\mathrm{8,2}m+2n-\mathrm{12,}\left(n-2\right)\left(m-2\right))$ .

The generalized Petersen graph $GP\left(m\mathrm{,}n\right)$ is defined by taking

$V\left(GP\left(m\mathrm{,}n\right)\right)=\left\{u_i\mathrm{,}{v}_i\mathrm{<mo>\; :\; </mo>0}\le i\le m-1\right\}$

and

$E\left(GP\left(m\mathrm{,}n\right)\right)=\left\{u_i{u}_{i+1}\mathrm{,}{u}_i{v}_i\mathrm{,}{v}_i{v}_{i+n}\mathrm{<mo>\; :\; </mo>0}\le i\le m-1\right\}$

where the subscripts are integers modulo m, $m\ge 5$ and $1\le n\le \lfloor \frac{m-1}{2}\rfloor$ .

Theorem 12 Let G be a generalized Petersen graph $GP\left(m\mathrm{,}n\right)$ . Then, $IE\left(G\right)\cong K_{m+n}$ .

Proof. Let G be a generalized Petersen graph $GP\left(m\mathrm{,}n\right)$ with vertices as in Figure 4. Then, $N_{in}\left(u_i\right)=\left\{u_{i+2}\mathrm{,}{u}_{i-2}\mathrm{,}{v}_{i+n}\mathrm{,}{v}_{i-n}\mathrm{,}{v}_{i-1}\mathrm{,}{v}_{i+1}\right\}$ and $N_{in}\left(v_i\right)=\left\{u_{i+1}\mathrm{,}{u}_{i-1}\mathrm{,}{u}_{i+n}\mathrm{,}{u}_{i-n}\mathrm{,}{v}_{i+2n}\mathrm{,}{v}_{i-2n}\right\}$ . Therefore, for $0\le i\le m-1$ , $de{g}_{in}\left(u_i\right)=de{g}_{in}\left(v_i\right)=6$ . Hence, $IE\left(G\right)\cong K_{m+n}$ .

Proposition 13 Let $G\cong C_m\times P_3$ . Then $IE\left(G\right)\cong K_{3m}$ .

Proof. Let $G\cong C_m\times P_3$ . We have three cases:

Case 1. If $m=3$ , then for all $v\in V\left(G\right)$ , $de{g}_{in}\left(v\right)=5$ . Therefore, all the vetrices have the same Inj-degree. Hence, $IE\left(G\right)\cong K_{3m}$ .

Case 2. If $m=4$ , then for all $v\in V\left(G\right)$ , $de{g}_{in}\left(v\right)=4$ or 5. Therefore, $IE\left(G\right)\cong K_{3m}$ .

Case 3. If $m\ge 5$ , then for all $v\in V\left(G\right)$ , $de{g}_{in}\left(v\right)=5$ or 6. Therefore, for any two vertices u and v in G,

$\left|de{g}_{in}\left(u\right)-de{g}_{in}\left(v\right)\right|=1$ . Hence, $IE\left(G\right)\cong K_{3m}$ .

Theorem 14 For any graph G such that $G\cong C_m\times P_n$ ,

$IE\left(G\right)\cong K_{2m}\cup K_{m\left(n-2\right)}$ , where $n\ge 5$ .

Proof. Suppose that $G\cong C_m\times P_n$ . Then we have 2m vertices of injective degree 5, 2m vertices of injective degree 7 and $m\left(n-4\right)$ vertices of injective degree 8. Hence, $IE\left(G\right)\cong K_{2m}\cup K_{m\left(n-2\right)}$ .

Figure 4. Generalized Petersen graph $GP\left(m\mathrm{,}n\right)$ .

Proposition 15 For any graph G, such that $G\cong C_n\times C_m$ , $IE\left(G\right)\cong K_{nm}$ .

Proof. Let G be a graph such that $G\cong C_n\times C_m$ . Then every vertex in G has injective degree 8. Hence, $IE\left(G\right)\cong K_{nm}$ .

Proposition 16 $IE\left(K_n\circ {\bar{K}}_m\right)=K_n\cup K_{nm}$ .

Proof. Consider the corona $K_n\circ {\bar{K}}_m$ . The interior vertices have injective degree $\left(n-1\right)\left(m+1\right)$ and the outer vertices have injective degree $n+m-2$ . Therefore $IE\left(K_n\circ {\bar{K}}_m\right)=K_n\cup K_{nm}$ .

Theorem 17 For any graph G with $\delta \ge 2$ , if G is k-regular or $\left(k\mathrm{,}k+1\right)$ - biregular, then

$IE\left(G\circ {\bar{K}}_m\right)=K_n\cup K_{mn}\mathrm{,}$

where n is the number of vertices in G.

Proof. Let G be a k-regular graph with n vertices and $\delta \ge 2$ . Suppose that $\left\{u_1\mathrm{,}{u}_2\mathrm{,}\cdots ,u_n\right\}$ and $\left\{v_1,v_2\mathrm{,}\cdots ,v_m\right\}$ are the vertex sets of G and ${\bar{K}}_m$ , respectively. Therefore, for $i=1,2,\cdots ,n$ , $de{g}_{in}\left(u_i\right)=k\left(m+1\right)$ and for $j=\mathrm{1,2,}\cdots ,m$ , $de{g}_{in}\left(v_j\right)=k+m-1$ . Therefore, $\left|de{g}_{in}\left(u_i\right)-de{g}_{in}\left(v_j\right)\right|=m\left(k-1\right)+1>1$ . Hence, $IE\left(G\circ {\bar{K}}_m\right)=K_n\cup K_{mn}$ . Similarly, we can prove if G is $\left(k\mathrm{,}k+1\right)$ -biregular, then $IE\left(G\circ {\bar{K}}_m\right)=K_n\cup K_{mn}$ .

Proposition 18 For any cycle graph $C_n$ , $IE\left(C_n\circ K_1\right)=2K_n$ .

Proof. Let $u_i$ be any vertex on the cycle $C_n$ and $v_i$ be any vertex outside the cycle $C_n$ . Then $de{g}_{in}\left(u_i\right)=4$ and $de{g}_{in}\left(v_i\right)=4$ . Therefore, $IE\left(C_n\circ K_1\right)=2K_n$ .

Definition 19 Let $G=\left(V\mathrm{,}E\right)$ be a graph. A subset D of V is called degree Inj-equitable set if the difference between the injective degree of any two vertices in D less then or equal one. The maximum cardinality of a degree Inj-equitable set in G is called degree Inj-equitable number of G and is denoted by $D_{ie}\left(G\right)$ . the minimum cardinality of a maximal degree Inj-equitable set is called the lower degree Inj-equitable number of G and is denoted by $d_{ie}\left(G\right)$ .

Observation 20 For any integer $\delta \le i\le \Delta -1$ , let $S_i=\{v\in V\mathrm{<mo>\; :\; </mo>}de{g}_{in}\left(v\right)=i$ or $i+1\}$ . A nonempty subset A of V is a maximal degree Inj-equitable if and only if $A=S_i$ for some i. Hence, $D_{ie}\left(G\right)=max\{\left|S_i\right|\mathrm{<mo>\; :\; </mo>}\delta \le i\le \Delta -1$ and $S_i\ne 0\}$ and $d_{ie}\left(G\right)=min\{\left|S_i\right|\mathrm{<mo>\; :\; </mo>}\delta \le i\le \Delta -1$ and $S_i\ne 0\}.$

Observation 21 Let $G=\left(V\mathrm{,}E\right)$ be a graph. The intersection graph of maximal degree Inj-equitable sets denoted by $G_{in}$ is defined on the family of all maximal degree Inj-equitable sets of G and has the property that any two vertices are adjacent if their intersection is not empty.

Theorem 22 For any graph G,

$\Delta \left(IE\left(G\right)\right)=D_{ie}\left(G\right)-1$

and

$\delta \left(IE\left(G\right)\right)=d_{ie}\left(G\right)-1.$

Proof. Since $\langle S_i\rangle$ is complete subgraph in $IE\left(G\right)$ and from Observation 20 $D_{ie}\left(G\right)=max\{\left|S_i\right|\mathrm{<mo>\; :\; </mo>}\delta \le i\le \Delta -1$ and $S_i\ne 0\}$ , then $D_{ie}\left(G\right)$ is the order of the maximum complete subgraph in $IE\left(G\right)$ . Therefore, for any vetrex in the maximum complete subgraph has degree $D_{ie}\left(G\right)-1$ . Hence $\Delta \left(IE\left(G\right)\right)=D_{ie}\left(G\right)-1$ .

Similarly, we can show that $\delta \left(IE\left(G\right)\right)=d_{ie}\left(G\right)-1$ .

The following proposition can be proved straightforward.

Proposition 23 For any graph G,

(i) $diam\left(IE\left(G\right)\right)={\Delta }_{in}\left(G\right)-{\delta }_{in}\left(G\right)$ .

(ii) $\omega \left(IE\left(G\right)\right)=D_{ie}\left(G\right)$ , where $\omega \left(IE\left(G\right)\right)$ is the clique number of $IE\left(G\right)$ .

Theorem 24 Let G be any graph. The number of edges in $IE\left(G\right)$ is given by:

$\stackrel{\Delta -1}{\underset{i=\delta }{{\displaystyle \sum }}}\frac{\left|S_i\right|\left(\left|S_i\right|-1\right)}{2}-\stackrel{\Delta -1}{\underset{i=\delta }{{\displaystyle \sum }}}\frac{\left|S_i\cap S_{i+1}\right|\left(\left|S_i\cap S_{i-1}\right|-1\right)}{2}$

where $S_i=\{v\in V\mathrm{<mo>\; :\; </mo>}{{\displaystyle deg}}_{in}\left(v\right)=i$ or $i+1\}$ .

Proof. Let G be any graph. Since each $\langle S_i\rangle$ is complete subgraph graph in $IE\left(G\right)$ , then $\langle S_i\rangle$ has $\frac{\left|S_i\right|\left(\left|S_i\right|-1\right)}{2}$ edges. But the edges in $\langle S_{i+1}\cap S_i\rangle$ are counted twice in $\frac{\left|S_i\right|\left(\left|S_i\right|-1\right)}{2}$ . Hence the number of edges in $IE\left(G\right)$ is given by

$\stackrel{\Delta -1}{\underset{i=\delta }{{\displaystyle \sum }}}\frac{\left|S_i\right|\left(\left|S_i\right|-1\right)}{2}-\stackrel{\Delta -1}{\underset{i=\delta }{{\displaystyle \sum }}}\frac{\left|S_i\cap S_{i+1}\right|\left(\left|S_i\cap S_{i-1}\right|-1\right)}{2}.$

Theorem 25 Let G be any graph. Then the following are equivalent:

(i) $IE\left(G\right)$ is connected graph.

(ii) The distinct sequence of the Inj-equitable degrees are ${\delta }_{in}\left(G\right)\mathrm{,}{\delta }_i\left(G\right)+\mathrm{1,}{\delta }_{in}\left(G\right)+\mathrm{2,}\cdots ,{\Delta }_{in}\left(G\right)$ .

(iii) The intersection graph of maximal degree Inj-equitable sets $G_{in}$ is a path.

Proof. (i)Þ(ii): Assume to the contrary, that $IE\left(G\right)$ is connected and there exist an integer ${\delta }_{in}\left(G\right)\le i\le {\Delta }_{in}\left(G\right)$ . Then $S_i$ and $S_{i-1}$ has no common vertices, that means $IE\left(G\right)$ is not connected which is a contradiction. Hence, the distinct sequence of the Inj-equitable degrees are ${\delta }_{in}\left(G\right)\mathrm{,}{\delta }_i\left(G\right)+\mathrm{1,}{\delta }_{in}\left(G\right)+\mathrm{2,}\cdots ,{\Delta }_{in}\left(G\right)$ .

(ii)Þ(iii): Suppose that the distinct sequence of the Inj-equitable degrees are ${\delta }_{in}\left(G\right)\mathrm{,}{\delta }_{in}\left(G\right)+\mathrm{1,}{\delta }_{in}\left(G\right)+\mathrm{2,}\cdots ,{\Delta }_{in}\left(G\right)$ . Then $S_i\cap S_{i+1}\ne \varphi$ and $S_i\cap S_j=\varphi$ if $\left|i-j\right|\ge 2$ . Hence, the intersection graph of maximal degree Inj-equitable sets $G_{in}$ is a path.

(iii)Þ(i): Suppose that $G_{in}$ is a path. Then $S_i\cap S_{i+1}\ne \varphi$ . Since $\langle S_i\rangle$ is complete, then $IE\left(G\right)$ is connected.

Proposition 26 For any graph G, $IE\left(G\right)$ is totally disconnected if and only if $G\cong K_1$ .

Proof. Let G be a graph such that $IE\left(G\right)$ is totally disconnected. Therefore, $\Delta \left(IE\left(G\right)\right)=\delta \left(IE\left(G\right)\right)=0$ . So, from Theorem 22, $D_{ie}\left(G\right)-1=d_{ie}\left(G\right)-1=0$ . Therefore, $D_{ie}\left(G\right)=d_{ie}\left(G\right)=1$ . Hence, $G\cong K_1$ .

Conversely, suppose that $G\cong K_1$ . Therefore, G has only one maximal degree Inj-equitable set of order one. So, $D_{ie}\left(G\right)=d_{ie}\left(G\right)=1$ . Therefore, $\Delta \left(IE\left(G\right)\right)=\delta \left(IE\left(G\right)\right)=0$ . Hence, $IE\left(G\right)$ is totally disconnected.

Theorem 27 For any graph G with n vertices, $IE\left(G\right)\cong K_n$ if and only if G has only one maximal degree Inj-equitable set.

Proof. Let G be a graph of order n and $IE\left(G\right)\cong K_n$ . Therefore, for any vertices u and v in G, $\left|de{g}_{in}\left(u\right)-de{g}_{in}\left(v\right)\right|\le 1$ . Hence, G has only one maximal degree Inj-equitable set. Conversely, suppose that G has only one maximal degree Inj-equitable set $S_i$ . Since $\langle S_i\rangle$ is complete in $IE\left(G\right)$ , then $IE\left(G\right)\cong K_n$ .

Next theorem gives the relation between the $IE\left(G\right)$ , $Con\left(G\right)$ and $G^e$ .

Theorem 28 For any graph G, $IE\left(G\right)\cong {\left(con\left(G\right)\right)}^e.$

Proof. Let G be any graph and consider $con\left(G\right)$ and $IE\left(G\right)$ . Both graphs have the same vertices. Now, let $f=uv$ be any edge in $IE\left(G\right)$ . Then, $\left|de{g}_{in}\left(u\right)-de{g}_{in}\left(v\right)\right|\le 1$ in G. Since $de{g}_{in}\left(u\right)$ in G is equal $\mathrm{deg}\left(u\right)$ in $con\left(G\right)$ , then, $\left|deg\left(u\right)-deg\left(v\right)\right|\le 1$ in $con\left(G\right)$ . Therefore, f is an edge in ${\left(con\left(G\right)\right)}^e$ . Hence $IE\left(G\right)$ is a subgraph of ${\left(con\left(G\right)\right)}^e$ .

Similarly we can show that ${\left(con\left(G\right)\right)}^e$ is a subgraph of $IE\left(G\right)$ .

3. Injective Equitable Graphs

Definition 29 A graph G is said to be injective equitable graph (IE-graph) if there exists a graph H such that $IE\left(H\right)\cong G$ .

For example, any complete graph is IE-graph.

Definition 30 The family of graphs H which satisfy the condition $IE\left(H\right)\cong G$ is called the injective equitable family of G and denoted by $G_{IE}$ . i.e,

$G_{IE}=\left\{H\mathrm{<mo>\; :\; </mo>}IE\left(H\right)\cong G\right\}\mathrm{.}$

Example 31 Let $H_1\mathrm{,}{H}_2$ and $H_3$ be figures as an Figure 5. Then, $IE\left(H_i\right)=K_3$ for all $i=1,2,3$ .

Lemma 32 Any path $P_n$ is not IE-graph.

Proof. Suppose, to the contrary, that $G\cong P_n$ such that G is IE-graph. Therefore, there exist a graph H such that $IE\left(H\right)\cong G$ . Let $v_1\mathrm{,}{v}_2$ and $v_3$ be

Figure 5. $IE\left(H_i\right)=K_3$ .

any vertices in G such that $v_1$ adjacent to $v_2$ and $v_2$ adjacent to $v_3$ . Suppose that $de{g}_{in}\left(v_1\right)=i$ in H. Therefore, $de{g}_{in}\left(v_2\right)=i-1$ or i or $i+1$ .

Case 1. $de{g}_{in}\left(v_2\right)=i-1$ . Therefore, $de{g}_{in}\left(v_3\right)=i-2$ or $i-1$ or i. If $de{g}_{in}\left(v_3\right)=i-1$ or i, then $v_1$ and $v_3$ are adjacent which contradicts that G is a path. So, $de{g}_{in}\left(v_3\right)=i-2$ .

Case 2. $de{g}_{in}\left(v_2\right)=i$ . Therefore, $de{g}_{in}\left(v_3\right)=i-1$ or i or $i+1$ . So, $v_1$ and $v_3$ are adjacent which contradicts that G is a path. Hence, $de{g}_{in}\left(v_2\right)\ne i$ .

Case 3. $de{g}_{in}\left(v_2\right)=i+1$ . Therefore, $de{g}_{in}\left(v_3\right)=i$ or $i+1$ or $i+2$ . If $de{g}_{in}\left(v_3\right)=i$ or $i+1$ , then $v_1$ and $v_3$ are adjacent which contradicts that G is a path. So, $de{g}_{in}\left(v_3\right)=i+2$ .

Hence the graph H has different injective degrees which contradicts that any graph with n vertices has at least two vertices of the same Inj-degree. Therefore, $P_n$ is not IE-graph.

Lemma 33 Any cycle $C_n$ is not IE-graph, where $n\ge 4$ .

Proof. Suppose, to the contrary, that G is a cycle such that G is IE-graph. Therefore, there exist a graph H such that $IE\left(H\right)\cong G$ . Let $v_1\mathrm{,}{v}_2$ and $v_3$ be any vertices in G such that $v_1$ adjacent to $v_2$ and $v_3$ . Let $de{g}_{in}\left(v_1\right)=i$ in H. Therefore, $de{g}_{in}\left(v_2\right)=i$ or $i-1$ or $i+1$ and $de{g}_{in}\left(v_3\right)=i-1$ or i or $i+1$ .

Case 1. $de{g}_{in}\left(v_2\right)=i$ . If $de{g}_{in}\left(v_3\right)=i-1$ or i or $i+1$ then $v_2$ and $v_3$ are adjacent which contradicts that G is a cycle.

Case 2. $de{g}_{in}\left(v_2\right)=i-1$ . If $de{g}_{in}\left(v_3\right)=i$ or $i-1$ , then $v_2$ and $v_3$ are adjacent which contradicts that G is a cycle. Therefore, $de{g}_{in}\left(v_3\right)=i+1$ .

Case 3. $de{g}_{in}\left(v_2\right)=i+1$ . If $de{g}_{in}\left(v_3\right)=i$ or $i+1$ , then $v_2$ and $v_3$ are adjacent which contradicts that G is a cycle. Therefore, $de{g}_{in}\left(v_3\right)=i-1$ .

Hence the graph H has different injective degrees which contradicts that any graph with n vertices has at least two vertices of the same Inj-degree. Therefore, any cycle $C_n$ is not IE-graph.

Lemma 34 Any bipartite graph is not IE-graph.

Proof. Suppose, to the contrary, that G is a bipartite graph such that G is IE-graph. Therefore, there exists a graph H such that $IE\left(H\right)\cong G$ . Let $v_1\mathrm{,}{v}_2$ and $v_3$ be any vertices in G such that $v_1$ adjacent to $v_2$ and $v_2$ adjacent to $v_3$ . Let $de{g}_{in}\left(v_1\right)=i$ in H. Therefore $de{g}_{in}\left(v_2\right)=i-1$ or i or $i+1$ .

Case 1. $de{g}_{in}\left(v_2\right)=i$ . If $de{g}_{in}\left(v_3\right)=i-1$ or i or $i+1$ then $v_2$ and $v_3$ are adjacent in G. So, G contains an odd cycle which contradicts that G is a bipartite graph.

Case 2. $de{g}_{in}\left(v_2\right)=i-1$ . If $de{g}_{in}\left(v_3\right)=i$ or $i-1$ , then $v_2$ and $v_3$ are adjacent in G. So, G contains an odd cycle which contradicts that G is a bipartite graph. Therefore, $de{g}_{in}\left(v_3\right)=i+1$ .

Case 3. $de{g}_{in}\left(v_2\right)=i+1$ . If $de{g}_{in}\left(v_3\right)=i$ or $i+1$ , then $v_2$ and $v_3$ are adjacent in G. So, G contains an odd cycle which contradicts that G is a bipartite graph. Therefore, $de{g}_{in}\left(v_3\right)=i-1$ .

Hence the graph H has different injective degrees which contradicts that any graph with n vertices has at least two vertices of the same Inj-degree. Therefore, any bipartite graph is not IE-graph.

Theorem 35 A connected graph G is IE-graph if G is a chain of complete graphs.

Proof. Suppose that G is a connected IE-graph. Then there exists a graph H such that $IE\left(H\right)\cong G$ . Each $\langle S_i\rangle$ is complete in $IE\left(H\right)$ and there are $S_i\cap S_{i+1}$ common vertices between $\langle S_i\rangle$ and $\langle S_{i+1}\rangle$ . Therefore, G is a chain of complete graphs.

4. Conclusion

In this paper, we introduced the injective equitable graph of a graph $IE\left(G\right)$ and the injective equitable graph IE-graph. We defined these graphs and presented some of their properties. Also, we found the Inj-equitable graph of some graph’s families. The degree injective equitable set, the degree injective equitable number of a graph and the lower degree injective equitable number are defined. Relations on those parameters in terms of maximum vertex degree, minimum vertex degree, diameter and clique number of the injective equitable graph are established. The connectedness of $IE\left(G\right)$ and relations between the $IE\left(G\right)$ , $Con\left(G\right)$ and $G^e$ are studied. In the last of this paper, the sufficient condition for a connected graph G to be IE-graph is presented.

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Alwardi, A., Alqesmah, A. and Rangarajan, R. (2016) Independent Injective Domination of Graphs. International Journal of Applied Mathematics and Mechanics, 3, 142-151.
[2]	Balakrishnan, R. and Ranganathan, K. (2000) A Textbook of Graph Theory. Springer-Velag, New York. https://doi.org/10.1007/978-1-4419-8505-7
[3]	Chartrand, G. and Lesniak, L. (2005) Graphs and Diagraphs. 4th Edition, CRC press, Boca Raton.
[4]	Harary, F. (1969) Graphs Theory. Addison-Wesley, Reading Mass. https://doi.org/10.21236/AD0705364
[5]	Alwardi, A., Arsic, B., Gutman, I. and Soner, N.D. (2012) The Common Neighborhood Graph and Its Energy. Iranian Journal of Mathematical Sciences and Informatics, 7, 1-8.
[6]	Dharmalingam, K.M. (2012) Equitable Graph of a Graph. Proyecciones Journal of Mathematics, 31, 363-372. https://doi.org/10.4067/S0716-09172012000400005
[7]	Alkenani, A., Alashwali, H. and Muthana, N. (2016) On the Injective Equitable Domination of Graphs. Applied Mathematics, 7, 2132-2139. https://doi.org/10.4236/am.2016.717169