1. Introduction
All the graphs considered here are finite and undirected with no loops and multiple edges. As usual 
and 
denote the number of vertices and edges of a graph
, respectively. In general, we use 
to denote the subgraph induced by the set of vertices 
and 
and 
denote the open and closed neighbourhoods of a vertex
, respectively. The degree of the vertex 
in 
is denoted by 
or
. For graph theoretic terminology, we refer to Harary [1]. The degree equitable domination has been studied in [2]. A subset 
of 
is called an equitable dominating set of a graph 
if for every
, there exists a vertex 
such that 
and
. The minimum cardinality of such a dominating set is denoted by 
and is called the equitable domination number of
. The set 
is minimal if for any vertex
, 
is not an equitable dominating set of
. The equitable neighbourhood of 
denoted by 
is defined as
and
. The cardinality of 
is denoted by 
and it is called equitable degree of the vertex 
in
. The maximum and minimum equitable degree of 
are denoted respectively by 
and
. That is
,
. An edge 
is called an equitable edge if
. A subset 
of
is called an equitable independent set, if 
contains no vertices 
such that
. If a vertex
satisfies 
for all
then 
is in the equitable dominating set. Such vertices are called equitable isolated vertices.
Let 
be a simple graph with 
vertices
. Then its adjacency matrix 
is a 
matrix whose entries 
are given by
In the same way, the degree equitable adjacency matrix denoted by 
is a 
matrix whose entries 
are given by
where The equitable adjacency between any two vertices 
in 
is defined as follows: the vertex 
is equitable adjacent to 
if and only if 
is adjacent to
and also
.
Degree equitable adjacency has interesting applications in the context of social networks. In a network, nodes with nearly equal capacity may interact with each other in a better way. In society, persons with nearly equal status, tend to be friendly. In industry, employees with nearly equal powers form associations and move closely. Equitability among citizens in terms of wealth, health, status, etc is the goal of a democratic nation. These ideas motivated us in this paper to study the degree equitability of a graph by defining and studying some basic properties of degree equitable connectivity, degree equitable regularity, and degree equitable completeness of a graph. Some new families of graphs and some interesting results are obtained. In this paper for brevity we use equitable instead of degree equitable.
2. Elementary Results
Let 
be a graph. An equitable walk is defined as a finite alternating sequence of vertices and equitable edges, beginning and ending with vertices, such that each equitable edge is incident with the vertices preceding and following it. No equitable edge appears (is covered or traversed) more than once in the equitable walk. A vertex, however, may appear more than once. An equitable walk which begin and end at the same vertex called closed equitable walk. An equitable walk is not closed if the terminal vertices are distinct. An open equitable walk in which no vertex appears more than once is called an equitable path. The number of edges in an equitable path is called the length of the equitable path. A closed equitable walk in which no vertex (except the initial and the final vertex) appears more than once is called an equitable circuit.
Now, we prove some results representing the relations between the sum of the equitable degree of the vertices, the number of edges and the number of equitable edges.
Theorem 2.1. For any graph 
with 
vertices 
and 
edges,
.
Further, the equality hold if and only if every edge in 
is equitable edge.
Proof. We have
, for any vertex 
in a graph
. Then it is clear that 
and we have:
similarly,
which implies
Hence
. Further, if every edge in 
is equitable edge, then 
for any vertex 
in 
that means
. The converse is obvious, if
, then every edge in 
is equitable edge.
For any graph
, the number of equitable edge denoted by 
is called the equitable size. The vertex 
is called equitable odd vertex (equitable even vertex) if 
is odd number (even number).
Theorem 2.2. The sum of the equitable degrees of a graph is twice the number of equitable edges in it, that is
.
Proof. Let 
be a graph. Then any equitable edge contributes to the equitable degrees of two distinct vertices. Thus when the equitable degrees of the vertices are added, each equitable edge is counted exactly two times. Thus the sum of the equitable degrees is twice the equitable size of the graph, that is
.
Theorem 2.3. Every graph has an even number of equitable odd vertices.
Proof. Suppose that the sum of the equitable degrees of the equitable odd vertices is 
and the sum of the equitable degrees of the equitable even vertices is
. The number 
is even, and the number 
is even. Hence 
is even. If there are 
equitable odd vertices, the even number 
is the sum of 
odd numbers. So 
is even.
We can define the equitable complete graph 
as a connected graph which all its edges are equitable edges. and analogous to the equitable complete graph we can defined the equitable complement graph of a graph 
as following:
Definition 2.4. For any graph
, the equitable complement graph of 
denoted by 
is the graph with the same vertices as 
and any two vertices 
are adjacent if 
and 
are not equitable adjacent in
.
The relation between the complement of the graph and the equitable complement graph of a graph can be found in the following theorem.
Theorem 2.5. For any graph
,
.
Proof. Let 
be any edge in
. Then 
and 
are not-adjacent vertices in
, which implies 
and 
are not equitable adjacent in
. Hence 
is an edge in the graph
. Therefore
.
Theorem 2.6. For any graph 
with 
vertices, 
if and only if 
is isomorphic to an equitable complete Graph.
Proof. Let 
be an equitable complete Graph and let 
be any edge in the graph
. Then 
is nonadjacent to 
in
. Hence 
is an edge in
, and since from the previous theorem we have
. Hence
. Conversely, suppose that 
and 
is not an equitable complete graph. Then there exists at least one edge 
in 
which is not equitable edge. That means 
and 
are not equitable adjacent, which implies that 
is an edge in
. But clearly 
and 
are not adjacent in
, a contradiction.
A graph 
is called an equitable edge-free graph if for any two adjacent vertices 
and 
in
,
.
Proposition 2.7. For any graph 
with 
vertices, 
if and only if 
is an equitable edge-free.
Proof. Let 
be an equitable edge-free graph with 
vertices. Then any two vertices in 
are adjacent. Hence
.
Conversely, suppose
. Hence any two vertices in 
are adjacent, then 
has no any equitable edge. Therefore 
is equitable edge-free.
Theorem 2.8. For any graph 
with 
vertices, 
if and only if 
is isomorphic to the complete Graph
.
Proof. Let
. Then any two vertices
are equitable adjacent. Hence 
does not contain any edge. Therefore
.
Conversely, suppose that
, and if possible 
is not complete Graph. This implies that there exist at least two nonadjacent vertices 
and 
in 
which are adjacent in
. Thus 
and 
are adjacent in
, a contradiction. Hence 
is complete graph
.
Corollary 2.9. For any equitable edge-free graph 
with 
vertices, 
.
Theorem 2.10. Let 
be a graph with p vertices and contains at least one non equitable edge with the property that any two vertices 
in
, we have
. Then 
.
Proof. Let 
be any two vertices in
. Then we have two cases:
Case 1: If 
and 
are adjacent vertices in
, then we have two subcases:
a) If 
is equitable edge, then 
and 
are not adjacent in
. Thus 
and 
are adjacent in
.
b) If 
is not equitable edge that means 
and since
. Then 
and 
are adjacent but not equitable adjacent in
. Therefore, 
and 
are adjacent in
.
Case 2: If 
and 
are nonadjacent vertices in
, then 
and 
are adjacent vertices in
. Since
, we get 
and 
are not equitable adjacent in
. Hence 
is adjacent to 
in
. Therefore any two vertices in 
are adjacent. Hence
.
3. Equitable Connectivity and Equitable Regularity
A graph 
is said to be equitable connected if there is at least one equitable path between every pair of vertices in
. Otherwise, 
is equitable disconnected. It is easy to see that an equitable disconnected graph consists of two or more equitable connected graphs. Each of these equitable connected subgraphs is called equitable component. Clearly any equitable connected graph is connected but the converse is not true equitable in general. For example, the graph
, where 
is connected but not equitable connected.
Theorem 3.1. The isomorphism between the graphs preserve the number of equitable component.
Proof. Let 
and 
be isomorphic graphs. Let 
be an isomorphism. If 
is an equitable path in 
from 
to
, then 
is an equitable path in 
from 
to
. Thus, 
and 
are in the same equitable component of 
if and only if 
to 
are in the same component of H.
Theorem 3.2. A graph 
is equitable disconnected if and only if its vertex set 
can be partitioned into two nonempty, disjoint subsets 
and 
such that there exists no equitable edge in 
whose one end vertex is in subset 
and the other in subset 
.
Proof. Suppose that we have the partition of 
into disjoint subsets 
and 
such that there exists no equitable edge in 
whose one end vertex is in subset 
and the other in subset
. Consider two arbitrary vertices 
and 
of
, such that 
and
. Then there is no equitable path between the vertices 
and
. Hence, if a partition exists, 
is not equitable connected.
Conversely, let 
be a disconnected graph. Consider 
to be a vertex in
. Let 
be the set of all vertices that are joined by equitable paths to
. Since 
is equitable disconnected, 
does not include all vertices of
. The remaining vertices will form a (nonempty) set
. No vertex in 
is joined to any in 
by an equitable edge. Hence the partition.
Theorem 3.3. If a graph (equitable connected or equitable disconnected) has exactly two vertices of odd equitable degree, then there exists an equitable path joining these two vertices.
Proof. Let 
be a graph with all even vertices except vertices 
and
, which are odd. From Theorem 2.3, no graph can have an odd number of equitable odd vertices. Therefore, in graph
, 
and 
must belong to the same equitable component, and hence must have equitable path between them.
Definition 3.4. Let 
be a graph on 
vertices. An equitable disconnecting set of edges is a subset 
such that 
is equitable disconnected. The edge equitable connectivity, 
, is the smallest number of edges in any equitable disconnecting set.
We adopt the convention that
. Thus 
if and only if 
or 
is equitable disconnected. If 
then 
is a connected graph having an equitable edge 
such that 
is equitable disconnected. An equitable edge whose removal increases the number of equitable components is called equitable cut-edge (equitable bridge) of
.
Example. In the graph 
in Figure 1, the edge (12) is equitable cut edge but not cut edge. So we have 
but
.
Proposition 3.5. If 
is a graph, then 
. That is, the edge equitable connectivity of 
can be no larger than the minimum equitable degree of
.
Proof. let 
be an equitable connected graph on 
vertices and suppose 
is a vertex of equitable degree
. Since
is an equitable disconnecting set of edges,
.
The following result is straightforward.
Proposition 3.6. Suppose G is an equitable connected graph. Let 
be equitable edge. Then 
is an equitable cut-edge of 
if and only if 
is the only equitable path in 
from 
to
.
Definition 3.7. Let 
be an equitable connected graph. An equitable vertex cut (or an equitable separateing set) of 
is a set 
such that 
is equitable disconnected. The connectivity, 
, is the smallest number of vertices in any equitable vertex cut of
. A vertex whose removal increases the number of equitable components of 
is called equitable cut-vertex (or point of equitable articulation). For the graph in Figure 1, 
but
.
The maximal equitable connected subgraph of 
that has no equitable cut-vertex is called an equitable block of
.
Theorem 3.8. For any graph
,
.
Proof. If
, then 
is equitable disconnected and
. If
, then this
Figure 1. Equitable cut edge but not cut edge.
graph is equitable connected with equitable bridge
, that means 
or one of the vertices which incident with 
is equitable cut vertex. Therefore,
. If
, then removal 
edges results in equitable disconnected graph, that means the removal 
of this edges results in a graph 
with an equitable bridge
. For each of these 
edges select an incident vertex different from 
or
. The removal of these 
vertices remove all the 
edges. If the resulting graph is disconnected, then
. If not, 
is equitable bridge of this subgraph and hence the removal of 
or 
results in an equitable disconnected. Hence,
.
Definition 3.9. A graph 
is called 
-equitable regular graph if
.
Observation 3.10. Every 
-regular graph is 
-equitable regular graph but the converse is not true, in general.
Example. The graph in the Figure 2 is 2-equitable regular graph but not regular.
4. An Equitable Line Graph and an Equitable Total Graph
Definition 4.1. Given a graph
, its equitable line graph 
is a graph such that 1) Each vertex of 
represents an equitable edge of
; and 2) Two vertices of 
are adjacent if and only if their corresponding equitable edges share a common endpoint (are adjacent) in
.
Proposition 4.2. The line graph of equitable connected graph is connected.
Proof. If 
is equitable connected, it contains equitable path connecting any two of its edges, which translates into a path in 
containing any two of the vertices of
. Hence 
is connected.
Observation 4.3. Let 
be any graph. Then 
.
Remark. The equitable line graph of equitable connected graph is connected but not equitable connected in general. In Figure 3, the equitable line graph of equitable connected graph is connected but not equitable connected.
Figure 2. 2-equitable regular graph but not regular.
Figure 3. Equitable line graph of equitable connected graph.
Definition 4.4. Let 
be a graph. The equitable graph 
of 
is defined as the graph with vertex set 
and two vertices
, 
are adjacent if and only if 
and 
are equitable adjacent in
.
The following result is immediate.
Proposition 4.5. For any graph 
with at least one equitable edge, the following hold.
1)
.
2) 
if and only if 
is an equitable complete graph.
3) If
, then 
but the converse is not true.
Theorem 4.6. If 
is a graph and
, 
whose vertices have equitable degree
, then
has 
vertices and
where 
is the number of equitable edges in
.
Proof. Clearly from the definition of equitable line graph 
has 
vertices the 
equitable edges incident with a point 
contribute 
to
, so
Proposition 4.7. If 
is a graph, then 
if and only if 
is an equitable complete graph.
Proof. If 
is an equitable complete graph then clearly
.
Conversely, let
. Then 
and 
have the same number of vertices that means
. Hence 
is an equitable complete graph.
Theorem 4.8. A connected graph is isomorphic to its equitable line graph if and only if it is a cycle.
Proof. If 
is cycle, then clearly
. Conversely, if 
is isomorphic to
, that means 
is an equitable complete graph, and by Proposition 4.7.
. Hence
. Therefore 
is cycle.
Definition 4.9. The equitable total graph 
of a graph 
is a graph such that 1) The vertex set of 
corresponds to the vertices and equitable edges of 
and 2) Two vertices are adjacent in 
if and only if their corresponding elements are either adjacent or incident in
.
Observation 4.10. For any graph 
the equitable total graph is a subgraph of the total graph of a graph
.
Proposition 4.11. If 
is a vertex and 
be equitable edge in a graph
, then the degree of the vertex 
is 
and the degree of 
is 
in
.
Proposition 4.12. If 
is a graph with 
vertices and 
edges and its vertices have equitable degree
, then 
has 
vertices and
where 
is the number of equitable edges in
.
Proof. The number of vertices of the graph 
is the sum of number of equitable edge and number of vertices in
, that is 
has 
vertices. By the definition of total graph of
, the number of edges in 
is the sum of edges in 
and the number of edges in the equitable line graph of 
and twice the number equitable edges in
, that is;
. Hence, 
.