Abstract
Semigraph is a generalization of graph. We introduce the concept of energy in a semigraph in two ways, one, the matrix energy , as summation of singular values of the adjacency matrix of a semigraph, and the other, polynomial energy , as energy of the characteristic polynomial of the adjacency matrix. We obtain some bounds for and show that is never a square root of an odd integer and cannot be an odd integer. We investigate matrix energy of a partial semigraph and change in the matrix energy due to edge deletion.
1 Introduction
Let be a graph of order and let be the adjacency matrix of . The eigenvalues of are called eigenvalues of . The energy of a graph is defined as the sum of the absolute values of its eigenvalues [Citation1] and it is an extensively studied quantity [Citation2,Citation3]. There are two generalizations of graph energy. Nikiforov [Citation4] generalized the concept of graph energy to that of the energy of any matrix. He defined the energy of a matrix as the sum of the singular values of . Another generalization of the graph energy is due to Mateljevic [Citation5] who defined the energy of an arbitrary polynomial such that Coulson integration formula remains valid.
Sampathkumar [Citation6] generalized the definition of a graph to a semigraph in the following way.
Definition 1
A is an ordered pair of two sets and , where is a non-empty set whose elements are called vertices of and is a set of -tuples, called edges of , of distinct vertices, for various ( at least ) satisfying the following conditions:
1. | (SG1) — Any two edges have at most one vertex in common. |
2. | (SG2) — Two edges () and () are considered to be equal if
|
Clearly the edge is same as . For the edge , and are called the end vertices of and are called the middle vertices of . A subedge of an edge is a -tuple , where . We say that is the subedge induced by the set of vertices . A partial edge of is a -tuple , where . A semigraph is a subsemigraph (partial semigraph) of a semigraph if and the edges in are the subedges (partial edges) of the edges in .
Example 1
Consider a semigraph in , where , , and , , In , vertices and are the end vertices, is a middle vertex, and are the middle-end vertices and is an isolated vertex.
The adjacency matrix of a semigraph is defined as follows [Citation7].
Definition 2
Let be a semigraph with vertex set and edge set . The adjacency matrix of is an matrix defined as follows:
1. | for every edge of of cardinality, say , let such that are distinct vertices in , for all
| ||||||||||||||||
2. | All the remaining entries of are zero. |
Example 2
For the semigraph given in , the adjacency matrix of is
A matrix is said to be semigraphical if there exists a semigraph such that the adjacency matrix of is . The cardinality of an edge is the number of vertices on that edge and is denoted by . In [Citation8], the expanse of a semigraph is defined as . For the terms not defined here, the reader may refer to [Citation6Citation9Citation[10]–Citation11].
In this paper, we define the polynomial energy of a semigraph using the concept of energy of a polynomial. Also, we define the matrix energy of a semigraph using the singular values of its adjacency matrix. For the graphs, these two definitions coincide with the definition of graph energy. Bapat et al. [Citation12] proved that the energy of a graph is never an odd integer. This holds for our definition of . It has been proved that the energy of a graph is never the square root of an odd integer [Citation13]. This holds for our definition of . In Section 2, we obtain some bounds for and prove that is never the square root of an odd integer and in Section 3, we prove that is never an odd integer. In Section 4, we discuss the energy of partial semigraphs and change in the matrix energy due to edge deletion.
2 Matrix energy of a semigraph
Nikiforov defined the energy of a general matrix (not necessarily square) as the summation of the singular values of that matrix.
Definition 3
Let be the adjacency matrix of a semigraph . The matrix energy of a semigraph , denoted by , is defined as the summation of the singular values of .
We observe the following.
1. | is a positive semidefinite matrix. So its eigenvalues , are non-negative and therefore the singular values of are non-negative real numbers. Thus, . In fact, if and only if the number of edges in is zero. |
2. | If is a semigraph obtained by relabeling of the vertices of , then is obtained by interchanging the rows and the corresponding columns of . Therefore the eigenvalues of and are same and thus the singular values of and are same. Hence the energy of a semigraph is well defined. |
In [Citation14], we see that for a graph with non-empty edge set, the energy of is greater or equal to 2. For a semigraph , we obtain a similar bound. First, we note that if is an edge of a semigraph , then the principal submatrix of induced by the rows and columns is the adjacency matrix of the edge induced partial semigraph . Let , denote the singular values of a matrix .
Theorem 1
If is a semigraph with nonempty edge set, then .
Proof
If the expanse of a semigraph is , then there exists an edge with cardinality . The adjacency matrix is a principal submatrix of and each of the two nonzero singular values is greater than . As, , the result follows.
In fact, the singular values of are and , hence . □
From the fact that the adjacency matrix of a graph is a symmetric matrix, its singular values are same as eigenvalues. Thus for a graph , its energy is same as .
Corollary 1
For a graph with nonempty edge set, .
Proof
The result follows as . □
If the cardinality of an edge of a semigraph is denoted by , then clearly . Now we have the following lemma.
Lemma 1
If is the adjacency matrix of a semigraph on vertices and , are the eigenvalues of , then
Proof
Corresponding to every edge of cardinality , there is a sequence in the rows corresponding to the end vertices of that edge. So every edge contributes to the trace of .
Thus, .
Hence, . □
The following result gives the bounds for .
Theorem 2
For a semigraph on vertices
Proof
Let be the eigenvalues of and be the singular values of . Consider the two vectors and . By Cauchy–Schwarz’s inequality, we have
As for every edge of a graph, we have the following observation.
Corollary 2
If is a graph on vertices and edges, then
Theorem 3
For a semigraph on vertices, where .
Proof
Let , be the singular values of . We have
Therefore, arithmetic mean of geometric mean of implies
Thus, (4) (4) where . From Eqs. (3), (Equation4(4) (4) ) and Lemma 1 the result follows. □
Corollary 3
If is a graph on vertices and edges, then .
For a matrix , the norm is defined as . The following lemma can be seen in [Citation4].
Lemma 2
If is any non-constant matrix and are singular values of , then (5) (5)
Now, we obtain a lower bound for .
Theorem 4
If is a semigraph on vertices having largest singular value and second largest singular value , then
Proof
By substituting and using Lemma 1 and, we get the result. □
Example 3
If is a path semigraph, and , then the nonzero singular values of are and . The energy of is Thus the bound given in Theorem 4 is attained.
Theorem 5
is never the square root of an odd integer.
Proof
As , we have , where is a positive integer. If are the singular values of , then (6) (6)
Therefore, . If is an integer, then is an even integer. Thus is never the square root of an odd integer. □
3 Polynomial energy of a semigraph
The energy of a polynomial is defined as , where ’s are the roots of (see [Citation5]). The eigenvalues of a semigraph are the zeros of the characteristic polynomial of its adjacency matrix.
Definition 4
Let be a semigraph on vertices with eigenvalues , . The polynomial energy of the semigraph , denoted by , is defined as .
If a semigraph is a graph, then , where ’s are the eigenvalues of .
Let and be matrices of order and , respectively. The Krönecker product of and , denoted by , is the block matrix . We have the following lemma.
Lemma 3
If and are two semigraphs of orders and respectively, and and are the adjacency matrices of and with eigenvalues and respectively, then is a semigraphical matrix, where are the identity matrices of appropriate sizes. Further, , where are the eigenvalues of .
Proof
Let and be the vertex sets of the semigraphs and , respectively. Let . Consider the semigraph with vertex set . is an edge of if and only if is an edge of and ; or is an edge of and . is called the product of the semigraphs and , and is denoted by . We observe that the adjacency matrix of is . Hence the eigenvalues of are , where . □
The following lemma can be seen in [Citation9].
Lemma 4
[Citation9]
If is a zero of a monic polynomial with integer coefficients, then is an integer.
Thus we have the following result.
Theorem 6
is never an odd integer.
Proof
Let be the adjacency matrix of a semigraph and be the eigenvalues of . Since the trace of is zero, we have (7) (7) Let be the set of ’s having positive real part, and be the set of ’s having negative real part.
If is an eigenvalue of , then is also an eigenvalue of . Further, both (or ). Therefore, and are real numbers and , .
From Eq. (Equation7(7) (7) ), we have , that is, .
Suppose . Therefore (8) (8) By Lemma 3, is an eigenvalue of the semigraph ( times). Thus is a zero of a monic polynomial with integer coefficients. Therefore, if is a rational number then it is an integer. Hence the result follows from Eq. (Equation8(8) (8) ). □
Not only is never an odd integer, but also every even integer is a polynomial energy of some semigraph as shown in the example below.
Example 4
Consider , with vertex set and edge set . The eigenvalues of are . Thus, .
4 Matrix energy and partial semigraphs
For a graph , we know . Now we obtain a similar bound for a semigraph. It is easy to observe that if is an edge of , then the adjacency matrix of the edge induced partial semigraph is a principal submatrix of . For a semigraph , let denote the singular values of .
Theorem 7
If is a semigraph with expanse , then .
Proof
If expanse of is , then contains an edge of cardinality . The adjacency matrix of , the edge induced partial semigraph is
The positive singular values of are greater than . Since , we have . □
Theorem 8
If is a partial semigraph of and is a cut set consisting of only graphical edges such that is a component of the semigraph obtained by deleting from , then .
Proof
Let and be the components obtained by deleting edges of from . As , so , where .
Therefore, . Hence, . □
Corollary 4
If is a bridge, then .
If a bridge is deleted, the energy of a semigraph always decreases. But edge deletion does not always imply the same. In fact, may increase or decrease if an edge is deleted from a semigraph. In the example given below, one edge deletion decreases , while when the other edge is deleted increases.
Example 5
Consider the semigraph with the vertex set , and the edge set , . The adjacency matrix of is
Clearly the energy of .
If we delete any edge joining a vertex of a semigraphical edge , and any of the vertices , the energy increases. Whereas if any edge between the vertices or a partial/full edge is deleted then the energy decreases.
The following are some examples where energy increases. , .
If we delete any of the edges decreases. .
Now we find some partial semigraphs of a given semigraph such that matrix energy of partial semigraph is necessarily less than or equal to the matrix energy of . If is a principal submatrix of a square matrix , then (see [Citation14]). However not all the principal submatrices of are semigraphical. Also, every partial semigraph of does not have adjacency matrix which is a principal submatrix of .
Definition 5
Let be a nonempty subset of the edges of a semigraph and be the set of the vertices belonging to the edges in . The semigraph with vertex set and edge set is called the edge induced partial semigraph of , induced by . Further, this edge induced partial semigraph of , induced by , is called the edge induced complete semigraph if every edge containing two or more vertices of is in .
Example 6
Consider a semigraph with , . A semigraph with and is an edge induced complete semigraph of the semigraph . But with , is not an edge induced complete semigraph of , as contains the edge but does not contain even though the vertices .
Definition 6
Let be a subset of . Edge induced complete closure of is the smallest subset of containing such that the edge induced partial semigraph of is an edge induced complete semigraph.
Edge induced complete closure of is denoted by .
Algorithm to find edge induced complete closure:
Algorithm 1
Given: A nonempty subset of (full) edges of a semigraph , to find .
1. | If , then . |
2. | If , then let set of vertices on the edges of . If such that belong to an edge and , then add to . such that u,v are vertices of e and . |
3. | In general such that belong to and and set of vertices on the edges of . If then . |
4. | As has finitely many edges, the above process halts. □ |
Lemma 5
If is an edge induced complete semigraph of , then is a principal submatrix of .
Proof
Proof is clear from the definition of edge induced complete semigraph. □
Theorem 9
If is an edge induced complete semigraph of , then .
Proof
The proof follows from Lemma 5. □
The above condition is sufficient, but not necessary for a partial semigraph of to have energy .
Example 7
Consider the semigraph with , . The adjacency matrix of is
.
Consider the edge induced partial semigraph of with . Here is not an edge induced complete semigraph of and .
Notes
Peer review under responsibility of Kalasalingam University.
References
- Gutman I. The energy of a graph Ber. Math. Statist Sekt. Forshungsz. Graz 103 1978 1 22
- Cvetkovic D. Doob M. Sachs H. Spectra of Graphs-Theory and Applications 1980 Academic Press New York
- Li X. Shi Y. Gutman I. Graph Energy 2012 Springer New York
- Nikiforov V. The energy of graphs and matrices J. Math. Anal. Appl. 326 2007 1472 1475
- Mateljevic M. Bozin V. Gutman I. Energy of a polynomial and the coulson integral formula J Math. Chem. 48 2010 1062 1068
- E. Sampathkumar, Semigraphs and their applications, Report on the DST project, Department of Science and Technology (DST), India, May-2000.
- Gaidhani Y.S. Deshpande C.M. Athawale B.P. Adjacency matrix of a semiraph Electronic Notes Disc. Math. 63 2017 399 406
- Deshpande C.M. Gaidhani Y.S. Athawale B.P. Chromatic numbers of semigraphs Indian J. Disc. Math. 1 1 Special Issue: Special Issue: International Conference on Discrete Mathematics 2014 1 12
- Bapat R.B. Graphs and Matrices first ed. 2012 Hindustan Book Agency New Delhi
- Harary F. Graph Theory 1988 Narosa Publishing House New Delhi
- Pirzada S. An Introduction to Graph Theory 2012 Universities Press OrientBlackSwan, Hyderabad
- Bapat R.B. Pati S. Energy of a graph is never an odd integer Bull. Kerala Math. Assoc. 1 2004 129 132
- Pirzada S. Gutman I. Energy of a graph is never the square of an odd integer Appl. Anal. Disc. Math. 2 2008 118 121
- Day J. So W. Graph energy change due to edge deletion Linear Algebra Appl. 428 2008 2070 2078