ABSTRACT

Let be a graph. If is a function from the vertex set to the set of positive integers. Then two vertices are -equitable if. By the degree, equitable adjacency between vertices can be redefine almost all of the variants of the graphs. In this paper we study the degree equitability of the graph by defining equitable connectivity, equitable regularity, equitable connected graph and equitable complete graph. Some new families of graphs and some interesting results are obtained.

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 allthen 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

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.

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 andwhere 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, .

REFERENCES