Received 20 May 2015; accepted 30 June 2015; published 3 July 2015

ABSTRACT

In this paper, we introduce a new type of graph energy called the non-common-neighborhood energy, NCN-energy for some standard graphs is obtained and an upper bound for is found when G is a strongly regular graph. Also the relation between common neigh- bourhood energy and non-common neighbourhood energy of a graph is established.

Keywords:

NCN-Eigenvalues (of Graph), NCN-Energy (of Graph), NCN-Adjacency Matrix (of Graph)

1. Introduction

Let G be a simple graph with n vertices, and let be its adjacency matrix. The eigenvalues of are the (ordinary) eigenvalues of the graph G [1] . Since is a symmetric matrix with zero trace, these eigenvalues are real with sum equal to zero.

The energy of the graph G is defined [2] as the sum of the absolute values of its eigenvalues:

Details on the theory of graph energy can be found in the reviews [3] -[5] , whereas details on its chemical applications in the book [6] and in the review [7] . Let G be simple graph with vertex set.

For, the common neighborhood of the the vertices and, denoted by, is the set of

vertices, different from and, which are adjacent to both and. The common-neighborhood matrix of G is then, where

The common-neighborhood energy (or, shorter, CN-energy) of the graph G is

where are the eigenvalues of the, for more details about CN-energy, see [9]

Theorem 1. [8] For almost all n-vertex graphs

Theorem 1 immediately implies that almost all graphs are hyperenergetic, making any further search for them pointless.

In what follows we shall need a few auxiliary results.

Lemma 1. [1] Let G be a connected k-regular graph with n vertices and. Let be its eigenvalues. Then the eigenvalues of the line graph of G are, and with multiplicity.

Lemma 2. [1] Let G be a graph with an adjacency matrix A and with eigenvalues, then the

, for any polynomial, is an eigenvalue of and hence.

Corollary 1. [9] Let G be a connected k-regular graph and let be its eigenvalues.

1) The common-neighborhood eigenvalues of the complement of G are

2) The common-neighborhood eigenvalues of the line graph of G are

where the CN-eigenvalue has multiplicity.

Definition. A strongly regular graph with parameters is a k-regular graph with n vertices, such that any two adjacent vertices have common neighbors, and any two non-adjacent vertices have common neighbors.

2. Non-Common Neighbourhood Energy of Graphs

Definition. Let G be simple graph with vertex set. For, the non-common neigh-

borhood set of the the vertices and, denoted by, is the set of vertices, different from and

, which are not adjacent to both and. The non-common neighborhood matrix of G is then

, where

According to the above definition, the non-common neighborhood matrix is a real symmetric matrix. Therefore its eigenvalues are real numbers. Since the trace of is zero, the sum of its eigenvalues is also equal to zero. the eigenvalues of the matrix are called the CNC- eigenvalues of G

Definition. The non-common neighborhood energy (or, shorter, CNC-energy) of the graph G is

We will Denote by the unit matrix of order n, and by the square matrix of order n whose all elements are equal to unity. Let further 0 stand for a matrix (or pertinent dimension) whose all elements are equal to zero.

Proposition 2., where is the complete graph of order n.

Proof. Observing that, we get.

Proposition 3. , where is the complete bipartite graph of order.

Proof. First observe that if the vertices of are labeled so that all vertices are adjacent to all vertices, then

Observing that and, we have

Which implies.

Corollary 2.

Proposition 4., where is the complete bipartite graph of order.

Proposition 5. For any totally disconnected graph,.

Proof. Observing that for any two vertices u and v in there are vertices not adjacent to

both vertices u and v. Therefore, where is the adjacency matrix of the

complete graph with n vertices. Hence,.

The complete multipartite graph is a graph on vertices. The set of vertices is

partitioned into parts of cardinalities; an edge joins two vertices if and only if they belong to different parts. Thus is the complete graph. In the following proposition we get the CNC-energy of

the multipartite graph.

Proposition 6. Let be The complete multipartite graph on vertices, where. Then,

Proof. Let be a complete multipartite graph with vertices. From the definition

of complete multipartite graph we observe for any two distinct vertices if they belong to the same partite set with, then. But if the two vertices belongs to different partite sets we have. Hence the NCN-matrix of is of the following form.

where is the adjacency matrix of the complete graphs. Hence,

Corollary 3. For graph we have,

Corollary 4. For any cocktail party graph G which is the complement of,

The proof of the following result is straightforward.

Proposition 7. If the graph G consists of (disconnected) components, then

Theorem 8. Let G be a graph on n vertices, and let is the adjacency matrix of G, and, where

and Let. Then,

Proof. Since is equal to size of the set. Therefore

and as we know that. Hence

Lemma 3. Let be k-regular graph and, where

Then

Proof. Observing that if is k-regular, then, where

Therefore,

Hence

Proposition 9. For any k-regular graph G,

Proof. By Theorem 8 and Lemma 3, we have

Hence

Theorem 10. For any graph G,.

Proof. Since for is the number of vertices which not adjacent to both and and it is

equal to the number of vertices which adjacent to both and in, that means.

Theorem 11. Let G be a connected k-regular graph with eigenvalues. Then the NCN-eigenvalues

of G are.

Proof. Theorem 11 follows from Proposition 8 and Lemma 2 or by applying Theorem 10 and Corollary 1

Theorem 12. Let G be a connected k-regular graph and let be its eigenvalues. Then The NCN- eigenvalues of the line graph of G are

Proof. Theorem 12 follows from Proposition 8 and Lemma 2 or by applying Theorem 10 and Corollary 1

Theorem 13. For any connected graph G, if and only if G is complete multi bipartite graph for some positive integer, where for.

Proof. Let for some positive integer, where for. Suppose that u and v any two vertices in G, if u and v adjacent, then does not exists any vertex in G which is not adjacent to both of u and v, similarly if u and v are not adjacent that means is zero matrix. Therefore

and Corollary 2 are spacial cases of multi bipartite graph for some positive integer

, where for.

Conversely, if G is connected graph and, then by Theorem 10. Therefore

for some positive integers. Hence G is complete multi bipartite graph

for some positive integer, where for.

Lemma 4. If G is a strongly regular graph with parameters, then

(1)

Proof. If and are adjacent vertices of G, then. If and are non-adjacent ver-

tices of G, then. Since G has pairs of adjacent vertices, and pairs of

non-adjacent vertices,

from which Equation (1) follows straightforwardly.

Theorem 14. If G is a strongly regular graph with parameters, then

(2)

Proof. follows an idea first used by Koolen and Moulton [10] [11] . Let be the common neigh- borhood eigenvalues of G, and let be the greatest eigenvalue. Because the greatest ordinary eigenvalue of G is equal to k, by Theorem 14,.

The Cauchy-Schwarz inequality states that if and are n-vectors, then

Now, by setting and, , in the above inequality, we obtain

Therefore

i.e.,

i.e.,

By using Lemma 4,

Acknowledgements

We thank the Editor and the referee for their comments.

References