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.
This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).
http://creativecommons.org/licenses/by/4.0/
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 , is the graph with the same vertices as G and for any two adjacent vertices u and v in , , where for any vertex , . 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 without loops and multiple edges. will denote the subgraph of G induced by a set of vertices X. For any vertex the open neighborhood of v is the set . The closed neighborhood of v is . The degree of a vertex v in G is . and are the maximum and minimum vertex degree of G respectively. The distance 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 . 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 , is the order of the maximal complete subgraph of G. The Inj-neighborhood of a vertex denoted by is defined as , where is the number of common neighborhood between the vertices u and v. The cardinality of is called injective degree of the vertex u and is denoted by in G. The corona product is obtained by taking one copy of G and copies of H and by joining each vertex of the i-th copy of H to the i-th vertex of G, where . The cartesian product is a graph with vertex set and edge set and , or and . 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 , is the graph with vertex set , 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 , is the graph with vertex set and two vertices u and v are adjacent if and only if [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 be a graph. The injective equitable (Inj-equitable) graph of a graph G, denoted by , is defined as the graph with the same vertices as G and two vertices u and v are adjacent in if
Example 2 Let G be a graph as in Figure 1. Then, .
The Inj-equitable graph of some known graphs are given in the following observation:
Observation 3
(i) For any path with n vertices, .
(ii) For any cycle with n vertices, .
(iii) For any complete graph , .
Proposition 4 For any complete bipartite graph ,
Proof. Let be a complete bipartite graph with partite sets A and B such that , . Clearly for any vertex v from A, and for any vertex u from B, . Therefore, for any two vertices u and v in , . If , then . Otherwise, .
We will generalize Proposition 4 in the following result.
Proposition 5 For any multipartite graph , where ,
Figure 1. A graph G.
, where .
Proof. Let G be a multipartite graph where . Then for every vertex u in G, . Hence, , where .
Bi-star graph is the graph obtained by joining the apex vertices of two copies of star .
Proposition 6 For any bi-star graph ,
Proof. Let be a bi-star graph labeling as in Figure 2. Therefore, , , for , and for , . So, if , then . Otherwise, .
A firefly graph is a graph on 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 , and ,
Proof. Let G be a firefly graph as in Figure 3, where and . Let v be the center vertex, be any vertex from the triangle other than v. be any end vertex in the pendant edge. and be any end vertex and internal vertex respectively in the pendant path. Then, , , , and . There are three cases:
Case 1. Suppose that . Then, ,
, ,
, and
Figure 2. A bi-star graph.
Figure 3. A firefly graph.
. Hence, .
Case 2. Suppose that . Then, ,
, ,
and .
Hence .
Case 3. Suppose that . Then, ,
and .
Hence .
Definition 8 A complete chain graph denoted by is a chain of complete graphs such that there are common vertices between and , for .
Proposition 9 Let G be a graph such that . Then
Proof. Let G be a graph such that . Then there are two cases:
Case 1. If , for all , either or . Therefore, for any two vertices u and v, . Hence, .
Case 2. If , there are 4 vertices with Inj-degree 2, 4 vertices with Inj-degree 3 and vertices with Inj-degree 4. Therefore,
.
Proposition 10 Let G be a graph such that , where . Then
Proof. Suppose that, . Then we have two cases:
Case 1. If , then there are 6 vertices have Inj-degree 3, 4 vertices have Inj-degree 4 and 2 vertices have Inj-degree 5. Therefore, .
Case 2. If , then there are 6 vertices have Inj-degree 3, 4 vertices have Inj-degree 4, vertices have Inj-degree 5 and vertices of degree 6. Therefore, .
Theorem 11 Let G be a graph such that , where . Then .
Proof. Suppose that . Therefore, there are 4 vertices have Inj-degree 3, 8 vertices have Inj-degree 4, have Inj-degree 5, 4 vertices have Inj-degree 6, have Inj-degree 7 and have Inj-degree 8. Hence .
The generalized Petersen graph is defined by taking
and
where the subscripts are integers modulo m, and .
Theorem 12 Let G be a generalized Petersen graph . Then, .
Proof. Let G be a generalized Petersen graph with vertices as in Figure 4. Then, and . Therefore, for , . Hence, .
Proposition 13 Let . Then .
Proof. Let . We have three cases:
Case 1. If , then for all , . Therefore, all the vetrices have the same Inj-degree. Hence, .
Case 2. If , then for all , or 5. Therefore, .
Case 3. If , then for all , or 6. Therefore, for any two vertices u and v in G,
. Hence, .
Theorem 14 For any graph G such that ,
, where .
Proof. Suppose that . Then we have 2m vertices of injective degree 5, 2m vertices of injective degree 7 and vertices of injective degree 8. Hence, .
Figure 4. Generalized Petersen graph .
Proposition 15 For any graph G, such that , .
Proof. Let G be a graph such that . Then every vertex in G has injective degree 8. Hence, .
Proposition 16 .
Proof. Consider the corona . The interior vertices have injective degree and the outer vertices have injective degree . Therefore .
Theorem 17 For any graph G with , if G is k-regular or - biregular, then
where n is the number of vertices in G.
Proof. Let G be a k-regular graph with n vertices and . Suppose that and are the vertex sets of G and , respectively. Therefore, for , and for , . Therefore, . Hence, . Similarly, we can prove if G is -biregular, then .
Proposition 18 For any cycle graph , .
Proof. Let be any vertex on the cycle and be any vertex outside the cycle . Then and . Therefore, .
Definition 19 Let 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 . the minimum cardinality of a maximal degree Inj-equitable set is called the lower degree Inj-equitable number of G and is denoted by .
Observation 20 For any integer , let or . A nonempty subset A of V is a maximal degree Inj-equitable if and only if for some i. Hence, and and and
Observation 21 Let be a graph. The intersection graph of maximal degree Inj-equitable sets denoted by 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,
and
Proof. Since is complete subgraph in and from Observation 20 and , then is the order of the maximum complete subgraph in . Therefore, for any vetrex in the maximum complete subgraph has degree . Hence .
Similarly, we can show that .
The following proposition can be proved straightforward.
Proposition 23 For any graph G,
(i) .
(ii) , where is the clique number of .
Theorem 24 Let G be any graph. The number of edges in is given by:
where or .
Proof. Let G be any graph. Since each is complete subgraph graph in , then has edges. But the edges in are counted twice in . Hence the number of edges in is given by
Theorem 25 Let G be any graph. Then the following are equivalent:
(i) is connected graph.
(ii) The distinct sequence of the Inj-equitable degrees are .
(iii) The intersection graph of maximal degree Inj-equitable sets is a path.
Proof. (i)Þ(ii): Assume to the contrary, that is connected and there exist an integer . Then and has no common vertices, that means is not connected which is a contradiction. Hence, the distinct sequence of the Inj-equitable degrees are .
(ii)Þ(iii): Suppose that the distinct sequence of the Inj-equitable degrees are . Then and if . Hence, the intersection graph of maximal degree Inj-equitable sets is a path.
(iii)Þ(i): Suppose that is a path. Then . Since is complete, then is connected.
Proposition 26 For any graph G, is totally disconnected if and only if .
Proof. Let G be a graph such that is totally disconnected. Therefore, . So, from Theorem 22, . Therefore, . Hence, .
Conversely, suppose that . Therefore, G has only one maximal degree Inj-equitable set of order one. So, . Therefore, . Hence, is totally disconnected.
Theorem 27 For any graph G with n vertices, if and only if G has only one maximal degree Inj-equitable set.
Proof. Let G be a graph of order n and . Therefore, for any vertices u and v in G, . Hence, G has only one maximal degree Inj-equitable set. Conversely, suppose that G has only one maximal degree Inj-equitable set . Since is complete in , then .
Next theorem gives the relation between the , and .
Theorem 28 For any graph G,
Proof. Let G be any graph and consider and . Both graphs have the same vertices. Now, let be any edge in . Then, in G. Since in G is equal in , then, in . Therefore, f is an edge in . Hence is a subgraph of .
Similarly we can show that is a subgraph of .
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 .
For example, any complete graph is IE-graph.
Definition 30 The family of graphs H which satisfy the condition is called the injective equitable family of G and denoted by . i.e,
Example 31 Let and be figures as an Figure 5. Then, for all .
Lemma 32 Any path is not IE-graph.
Proof. Suppose, to the contrary, that such that G is IE-graph. Therefore, there exist a graph H such that . Let and be
Figure 5. .
any vertices in G such that adjacent to and adjacent to . Suppose that in H. Therefore, or i or .
Case 1. . Therefore, or or i. If or i, then and are adjacent which contradicts that G is a path. So, .
Case 2. . Therefore, or i or . So, and are adjacent which contradicts that G is a path. Hence, .
Case 3. . Therefore, or or . If or , then and are adjacent which contradicts that G is a path. So, .
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, is not IE-graph.
Lemma 33 Any cycle is not IE-graph, where .
Proof. Suppose, to the contrary, that G is a cycle such that G is IE-graph. Therefore, there exist a graph H such that . Let and be any vertices in G such that adjacent to and . Let in H. Therefore, or or and or i or .
Case 1. . If or i or then and are adjacent which contradicts that G is a cycle.
Case 2. . If or , then and are adjacent which contradicts that G is a cycle. Therefore, .
Case 3. . If or , then and are adjacent which contradicts that G is a cycle. Therefore, .
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 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 . Let and be any vertices in G such that adjacent to and adjacent to . Let in H. Therefore or i or .
Case 1. . If or i or then and are adjacent in G. So, G contains an odd cycle which contradicts that G is a bipartite graph.
Case 2. . If or , then and are adjacent in G. So, G contains an odd cycle which contradicts that G is a bipartite graph. Therefore, .
Case 3. . If or , then and are adjacent in G. So, G contains an odd cycle which contradicts that G is a bipartite graph. Therefore, .
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 . Each is complete in and there are common vertices between and . Therefore, G is a chain of complete graphs.
4. Conclusion
In this paper, we introduced the injective equitable graph of a graph 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 and relations between the , and 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. 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