﻿ A Study on the Inj-Equitable Graph of a Graph

Applied Mathematics
Vol.09 No.03(2018), Article ID:83428,10 pages
10.4236/am.2018.93020

A Study on the Inj-Equitable Graph of a Graph

Hanaa Alashwali1*, Ahmad N. Alkenani1, A. Saleh2, Najat Muthana1

1Department of Mathematics, King Abdulaziz University, Jeddah, KSA

2Department of Mathematics, Jeddah University, Jeddah, KSA Copyright © 2018 by authors and Scientific Research Publishing Inc.   Received: February 13, 2018; Accepted: March 26, 2018; Published: March 29, 2018

ABSTRACT

For any graph G, the Inj-equitable graph of a graph G, denoted by $IE\left(G\right)$ , is the graph with the same vertices as G and for any two adjacent vertices u and v in $IE\left(G\right)$ , $|de{g}_{in}\left(u\right)-de{g}_{in}\left(v\right)|\le 1$ , where for any vertex $w\in V\left(G\right)$ , $de{g}_{in}\left(w\right)=|\left\{{w}^{\prime }\in V:N\left({w}^{\prime }\right)\cap N\left(w\right)\ne \varphi \right\}|$ . 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,E\right)$ without loops and multiple edges. $〈X〉$ 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):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)=|N\left(v\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,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,v\right),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):|\Gamma \left(u,v\right)|\ge 1\right\}$ , where $|\Gamma \left(u,v\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 ${deg}_{in}\left(u\right)$ in G. The corona product $G\circ H$ is obtained by taking one copy of G and $|V\left(G\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 |V\left(G\right)|$ . The cartesian product $G×H$ is a graph with vertex set $V\left(G\right)×V\left(H\right)$ and edge set $E\left(G×H\right)=\left\{\left(\left(u,{u}^{\prime }\right),\left(v,{v}^{\prime }\right)\right):u=v$ and $\left({u}^{\prime },{v}^{\prime }\right)\in E\left(H\right)$ , or ${u}^{\prime }={v}^{\prime }$ and $\left(u,v\right)\in E\left(G\right)\right\}$ . For more terminologies and notations, we refer the reader to    and  .

The common neighborhood graph (congraph) of a graph G, denoted by $con\left(G\right)$ , is the graph with vertex set $\left\{{v}_{1},{v}_{2},\cdots ,{v}_{n}\right\}$ , in which two vertices are adjacent if and only if they have at least one common neighbor in the graph G  . 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 $|deg\left(u\right)-deg\left(v\right)|\le 1$  .

2. IE-Graph of a Graph

The Inj-equitable dominating sets on graphs which introduced in  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,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

$|de{g}_{in}\left(u\right)-de{g}_{in}\left(v\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({\stackrel{¯}{K}}_{n}\right)=IE\left({K}_{n}\right)={K}_{n}$ .

Proposition 4 For any complete bipartite graph ${K}_{r,s}$ ,

$IE\left({K}_{r,s}\right)\cong \left\{\begin{array}{ll}{K}_{r+s}\hfill & \text{if}\text{\hspace{0.17em}}|r-s|\le 1;\hfill \\ {K}_{r}\cup {K}_{s}\hfill & \text{otherwise}.\hfill \end{array}$

Proof. Let $G\cong {K}_{r,s}$ be a complete bipartite graph with partite sets A and B such that $|A|=r$ , $|B|=s$ . Clearly for any vertex v from A, ${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,s}$ , $|de{g}_{in}\left(u\right)-de{g}_{in}\left(v\right)|=|r-s|$ . If $|r-s|\le 1$ , then $IE\left({K}_{r,s}\right)={K}_{r+s}$ . Otherwise, $IE\left({K}_{r,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},{n}_{2},\cdots ,{n}_{m}}$ , where $m\ge 3$ ,

Figure 1. A graph G.

$IE\left({K}_{{n}_{1},{n}_{2},\cdots ,{n}_{m}}\right)={K}_{r}$ , where $r={\sum }_{i=1}^{m}\text{ }{n}_{i}$ .

Proof. Let G be a multipartite graph ${K}_{{n}_{1},{n}_{2},\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},{n}_{2},\cdots ,{n}_{m}}\right)={K}_{r}$ , where $r={\sum }_{i=1}^{m}\text{ }{n}_{i}$ .

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

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

$IE\left(B\left(s,t\right)\right)=\left\{\begin{array}{ll}{K}_{s+t+2}\hfill & \text{if}\text{\hspace{0.17em}}|s-t|\le 1;\hfill \\ {K}_{s+1}\cup {K}_{t+1}\hfill & \text{otherwise}.\hfill \end{array}$

Proof. Let $G\cong B\left(s,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$ , ${deg}_{in}\left({u}_{i}\right)=s$ and for $j=1,2,\cdots ,t$ , $de{g}_{in}\left({v}_{j}\right)=t$ . So, if $|s-t|\le 1$ , then $IE\left(B\left(s,t\right)\right)={K}_{s+t+2}$ . Otherwise, $IE\left(B\left(s,t\right)\right)={K}_{s+1}\cup {K}_{t+1}$ .

A firefly graph ${F}_{r,s,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,s,t}$ , $r\ge 1,s\ge 1$ and $t\ge 1$ ,

$IE\left({F}_{r,s,t}\right)=\left\{\begin{array}{ll}{K}_{2r+s+2}\cup {K}_{s}\hfill & \text{if}t=1;\hfill \\ {K}_{2r+s+2}\cup {K}_{1,s+2}\cup {K}_{s}\hfill & \text{if}t=2;\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,s,t}$ as in Figure 3, where $r\ge 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, $|de{g}_{in}\left(v\right)-de{g}_{in}\left({v}_{i}\right)|=1$ ,

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

$|de{g}_{in}\left({v}_{i}\right)-de{g}_{in}\left({w}_{i}\right)|=1$ , $|de{g}_{in}\left({v}_{i}\right)-de{g}_{in}\left({{u}^{\prime }}_{i}\right)|=1$ and

Figure 2. A bi-star graph.

Figure 3. A firefly graph.

$|de{g}_{in}\left({w}_{i}\right)-de{g}_{in}\left({{u}^{\prime }}_{i}\right)|=0$ . Hence, $IE\left({F}_{r,s,t}\right)\cong {K}_{2r+s+2}\cup {K}_{s}$ .

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

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

$|de{g}_{in}\left({v}_{i}\right)-de{g}_{in}\left({{u}^{\prime }}_{i}\right)|=1$ and $|de{g}_{in}\left({w}_{i}\right)-de{g}_{in}\left({{u}^{\prime }}_{i}\right)|=0$ .

Hence $IE\left({F}_{r,s,t}\right)\cong {K}_{2r+s+2}\cup {K}_{1,s+2}\cup {K}_{s}$ .

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

$|de{g}_{in}\left({v}_{i}\right)-de{g}_{in}\left({{u}^{\prime }}_{i}\right)|=1$ and $|de{g}_{in}\left({w}_{i}\right)-de{g}_{in}\left({{u}^{\prime }}_{i}\right)|=0$ .

Hence $IE\left({F}_{r,s,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},{s}_{1},{n}_{2},{s}_{2},\cdots ,{s}_{r-1},{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}×{P}_{2}$ . Then

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

Proof. Let G be a graph such that $G\cong {P}_{m}×{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, $|de{g}_{in}\left(u\right)-de{g}_{in}\left(v\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(8,4,2m-4\right)$ .

Proposition 10 Let G be a graph such that $G\cong {P}_{m}×{P}_{3}$ , where $m\ge 4$ . Then

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

Proof. Suppose that, $G\cong {P}_{m}×{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(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(10,4,2m-2,2m-6,3m-10\right)$ .

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

Proof. Suppose that $G\cong {P}_{m}×{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}×{P}_{n}\right)\cong CC\left(12,8,2m+2n-4,2m+2n-12,$ $2m+2n-8,4,2m+2n-8,2m+2n-12,\left(n-2\right)\left(m-2\right)\right)$ .

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

$V\left(GP\left(m,n\right)\right)=\left\{{u}_{i},{v}_{i}:0\le i\le m-1\right\}$

and

$E\left(GP\left(m,n\right)\right)=\left\{{u}_{i}{u}_{i+1},{u}_{i}{v}_{i},{v}_{i}{v}_{i+n}:0\le i\le m-1\right\}$

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

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

Proof. Let G be a generalized Petersen graph $GP\left(m,n\right)$ with vertices as in Figure 4. Then, ${N}_{in}\left({u}_{i}\right)=\left\{{u}_{i+2},{u}_{i-2},{v}_{i+n},{v}_{i-n},{v}_{i-1},{v}_{i+1}\right\}$ and ${N}_{in}\left({v}_{i}\right)=\left\{{u}_{i+1},{u}_{i-1},{u}_{i+n},{u}_{i-n},{v}_{i+2n},{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}×{P}_{3}$ . Then $IE\left(G\right)\cong {K}_{3m}$ .

Proof. Let $G\cong {C}_{m}×{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,

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

Theorem 14 For any graph G such that $G\cong {C}_{m}×{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}×{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,n\right)$ .

Proposition 15 For any graph G, such that $G\cong {C}_{n}×{C}_{m}$ , $IE\left(G\right)\cong {K}_{nm}$ .

Proof. Let G be a graph such that $G\cong {C}_{n}×{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 {\stackrel{¯}{K}}_{m}\right)={K}_{n}\cup {K}_{nm}$ .

Proof. Consider the corona ${K}_{n}\circ {\stackrel{¯}{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 {\stackrel{¯}{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,k+1\right)$ - biregular, then

$IE\left(G\circ {\stackrel{¯}{K}}_{m}\right)={K}_{n}\cup {K}_{mn},$

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},{u}_{2},\cdots ,{u}_{n}\right\}$ and $\left\{{v}_{1},{v}_{2},\cdots ,{v}_{m}\right\}$ are the vertex sets of G and ${\stackrel{¯}{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=1,2,\cdots ,m$ , $de{g}_{in}\left({v}_{j}\right)=k+m-1$ . Therefore, $|de{g}_{in}\left({u}_{i}\right)-de{g}_{in}\left({v}_{j}\right)|=m\left(k-1\right)+1>1$ . Hence, $IE\left(G\circ {\stackrel{¯}{K}}_{m}\right)={K}_{n}\cup {K}_{mn}$ . Similarly, we can prove if G is $\left(k,k+1\right)$ -biregular, then $IE\left(G\circ {\stackrel{¯}{K}}_{m}\right)={K}_{n}\cup {K}_{mn}$ .

Proposition 18 For any cycle graph ${C}_{n}$ , $IE\left({C}_{n}\circ {K}_{1}\right)=2{K}_{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)=2{K}_{n}$ .

Definition 19 Let $G=\left(V,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}=\left\{v\in V:de{g}_{in}\left(v\right)=i$ or $i+1\right\}$ . 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}|:\delta \le i\le \Delta -1$ and ${S}_{i}\ne 0\right\}$ and ${d}_{ie}\left(G\right)=min\left\{|{S}_{i}|:\delta \le i\le \Delta -1$ and ${S}_{i}\ne 0\right\}.$

Observation 21 Let $G=\left(V,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 $〈{S}_{i}〉$ is complete subgraph in $IE\left(G\right)$ and from Observation 20 ${D}_{ie}\left(G\right)=max\left\{|{S}_{i}|:\delta \le i\le \Delta -1$ and ${S}_{i}\ne 0\right\}$ , 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 }{\sum }}\frac{|{S}_{i}|\left(|{S}_{i}|-1\right)}{2}-\stackrel{\Delta -1}{\underset{i=\delta }{\sum }}\frac{|{S}_{i}\cap {S}_{i+1}|\left(|{S}_{i}\cap {S}_{i-1}|-1\right)}{2}$

where ${S}_{i}=\left\{v\in V:{deg}_{in}\left(v\right)=i$ or $i+1\right\}$ .

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

$\stackrel{\Delta -1}{\underset{i=\delta }{\sum }}\frac{|{S}_{i}|\left(|{S}_{i}|-1\right)}{2}-\stackrel{\Delta -1}{\underset{i=\delta }{\sum }}\frac{|{S}_{i}\cap {S}_{i+1}|\left(|{S}_{i}\cap {S}_{i-1}|-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),{\delta }_{i}\left(G\right)+1,{\delta }_{in}\left(G\right)+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),{\delta }_{i}\left(G\right)+1,{\delta }_{in}\left(G\right)+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),{\delta }_{in}\left(G\right)+1,{\delta }_{in}\left(G\right)+2,\cdots ,{\Delta }_{in}\left(G\right)$ . Then ${S}_{i}\cap {S}_{i+1}\ne \varphi$ and ${S}_{i}\cap {S}_{j}=\varphi$ if $|i-j|\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 $〈{S}_{i}〉$ 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, $|de{g}_{in}\left(u\right)-de{g}_{in}\left(v\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 $〈{S}_{i}〉$ 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, $|de{g}_{in}\left(u\right)-de{g}_{in}\left(v\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, $|deg\left(u\right)-deg\left(v\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:IE\left(H\right)\cong G\right\}.$

Example 31 Let ${H}_{1},{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},{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},{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},{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 $〈{S}_{i}〉$ is complete in $IE\left(H\right)$ and there are ${S}_{i}\cap {S}_{i+1}$ common vertices between $〈{S}_{i}〉$ and $〈{S}_{i+1}〉$ . 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.

Cite this paper

Alashwali, H., Alkenani, A.N., Saleh, A. and Muthana, N. (2018) A Study on the Inj-Equitable Graph of a Graph. Applied Mathematics, 9, 264-273. https://doi.org/10.4236/am.2018.93020

References

1. 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. 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. 3. Chartrand, G. and Lesniak, L. (2005) Graphs and Diagraphs. 4th Edition, CRC press, Boca Raton.

4. 4. Harary, F. (1969) Graphs Theory. Addison-Wesley, Reading Mass. https://doi.org/10.21236/AD0705364

5. 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. 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. 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