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:
![](//html.scirp.org/file/1-7402761x11.png)
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.