Universidade Federal de Santa Maria
Ci. e Nat., Santa Maria v.42, e91, 2020
DOI:10.5902/2179460X39755
ISSN 2179-460X
Received: 29/08/2019 Accepted: 22/01/2020 Published: 14/12/2020
Matemática
Q-borderenergetic threshold graphs
João Roberto Lazzarin^{I}
Oscar Franscisco Másquez Sosa^{II}
Fernando Colman Tura^{III}
^{I}Universidade Federal de Santa Maria, Santa Maria, Rio Grande do Sul, Brasil - joaolazzarin@gmail.com
^{II}Universidade Federal de Santa Maria, Santa Maria, Rio Grande do Sul, Brasil - omskar@gmail.com
^{III}Universidade Federal de Santa Maria, Santa Maria, Rio Grande do Sul, Brasil - fernandotura@gmail.com
ABSTRACT
A graph G is said to be borderenergetic (L-borderenergetic, respectively) if its energy (Laplacian energy, respectively) equals the energy (Laplacian energy, respectively) of the complete graph. Recently, this concept was extend to signless Laplacian energy (see Tao e Hou (2018)). A graph G is called Q-borderenergetic if its signless Laplacian energy is the same of the complete graph K_{n}, i.e., QE(G) = QE(K_{n}) = 2n −2. In this paper, we investigate Q-borderenergetic graphs on the class of threshold graphs. For a family of threshold graphs of order n ≤ 100, we find out exactly 13 graphs such that QE(G) = 2n −2.
Keywords: Signless laplacian energy; Threshold graph
1 Introduction
Throughout this paper, all graphs are assumed to be finite, undirected and without loops or multiple edges. If G is a graph of order n then the energy of G denoted by E(G) is
where λ_{i }are the eigenvalues of adjacency matrix A of G. There are many results on energy and its applications in several areas, including in chemistral see Li et al. (2012). If a graph G on n vertices has the same energy as the complete graph K_{n}, i.e., E(G) = E(K_{n}) = 2n − 2, then G is said borderenergetic graph. For more details and the references Yu et al. (2016); Jacobs et al. (2015); Gong et al. (2015); Hou e Tao (2016); Li et al. (2015); Shao e Deng (2016).
Let A be the adjacency matrix and D diagonal matrix of vertex degrees of G, respectively, then L = D − A and Q = D + A are called the Laplacian matrix and signless Laplacian matrix of G, respectively. The Laplacian energy and signless Laplacian energy of G are defined, respectively, by
(1)
and
(2)
where 0 = µ_{1 }≤ µ_{2 }≤ ... ≤ µ_{n }and 0 ≤ q_{1 }≤ q_{2 }≤ q_{3 }≤ ... ≤ q_{n }are the Laplacian and signless Laplacian eigenvalues of G, respectively, and d is the average degree of G.
Of course the concept of borderenergetic graph has been extended to Laplacian energy and signless Laplacian energy. Using (1) and (2), we say that a graph G is L-bordernergetic (Q-borderenergetic, respectively) if LE(G) = LE(K_{n}) (QE(G) = QE(K_{n}), respectively). For more details see the references Tao e Hou (2018); Tura (2017).
In this paper we investigate Q-borderenergetic graphs on the class of threshold graphs. A threshold graph is a graph with no induced subgraph isomorphic to the 2K_{2}, C_{4}, and P_{4}. This class of graphs admits several equivalent definitions. For example, a threshold graph has a recursive definition based on binary sequence that will be describe in the next Section. For other combinatorial characterizations of threshold graphs, we refer to reader to see Mahadev e Peled (1995) and the references given therein.
The paper is organized as follows. In Section 2 we describe the class of threshold graphs and some known results. In Section 3 we investigate Q-borderenergetic graphs on the class of threshold graphs. For a family of threshold graphs of order n ≤ 100, we find out exactly 13 graphs such that QE(G) = 2n − 2.
2 Preliminaries
A threshold graph can be characterized in many ways. One way to characterize threshold graphs is through an iterative process which starts with an isolated vertex, and where, at each step, either a new isolated is added, or a dominating vertex (adjacent to all previous vertices) is added. We represent a threshold graph G on n vertices using a binary sequence (b_{1}b_{2 }...b_{n}). Here b_{i }= 0 if a vertex v_{i }was added as an isolated vertex, and b_{i }= 1 if v_{i }was added as a dominating vertex. We call our representation a creation sequence, and always take b_{1 }to be zero.
For example, the Figure 1, shows a threshold graph G with creation sequence (00010001) or (0^{3}10^{3}1).
Let a,b,c be positive integers. In this paper, we deal with the following family of threshold graph G of order n which has creation sequence as (0^{a}1^{b}0^{c}), where n = a + b + c.
Let denote a signless Laplacian eigenvalue q with multiplicity the signless Laplacian spectrum of G.
Theorem 1. (Fritscher e Trevisan (2016), Theorem 32) Let a,b,c be positive integers, the threshold graph G with creation sequence (0^{a}1^{b}0^{c}) of order n = a + b + c has signless Laplacian spectrum equals
σ(G) = {b^{a−1},(b + a − 2)^{b−1},0^{c},q_{2},q_{1}} (3)
where and .
Lemma 1. Let G be a threshold graph with creation sequence (0^{a}1^{b}0^{c}) of order n = a + b + c. Let d be the average degree of G. There exist positive integers a,b,c ≥ 1 satisfying d ≤ q_{1 }and đ ≤ q_{2}.
Proof: Let a,b,c be positive integers such that đ ≤ b + a − 2. We have that
.
Since that đ ≤ 3b + a − 2 follows 2đ ≤+3b + a − 2, and therefore, đ ≤ q_{1}. The proof is similar for đ ≤ q_{2}.
Figura 1 - The threshold graph G
3 Q-borderenergetic graphs
Recall that the signless Laplacian energy QE(G) of G is defined to be , where 0 = q_{1} ≤ q_{2} ≤ ... ≤ q_{n} are the signless Laplacian eigenvalues of G and d is the average degree of G. It is known that the complete graph K_{n} has signless Laplacian energy 2(n − 1). We exhibit many threshold graphs which are Q-borderenergetic graphs.
Theorem 2. Let G be a threshold graph with creation sequence (0^{a}1^{b}0^{c}) of order n = a + b + c and signless Laplacian eigenvalues given by (3). Let đ be the average degree of G with đ ≤ q_{1},q_{2}. Then the signless Laplacian energy of G is given by
.
Proof: Using that and Theorem 1, follows
Since that , follows that , we have that
and so the result follows.
Theorem 3. Let G be a threshold graph with creation sequence (0^{a}1^{b}0^{c}) of order n = a + b + c and signless Laplacian eigenvalues given by (3). Let đ be the average degree of G with đ ≤ q_{1},q_{2}. If there are positive integers a,b,c satisfying
(b^{2} +2ab − b)c = (a + b + c)^{2} − (a + b + c) (4) then G is Q-borderenergetic graph.
QE(G) = 2(a + b + c − 1) (5)
According Theorem 2, we have
(6)
Equating the equations (5) and (6) and, using (4), we have the result.
Corollary 1. Let G be a threshold graph with creation sequence (0^{a}1^{b}0^{c}) of order n = a + b + c and signless Laplacian eigenvalues given by (3). Let d be the average degree of G with d ≤ q_{1},q_{2}. For n ≤ 100, there are totally 13 Q-borderenergetic threshold graphs which are listed in the below table, with their signless Laplacian spectrum and energies.
n |
G |
σ(G) |
E(G) |
21 |
0^{2}1^{4}0^{15} |
{2^{4}, 0^{15}, , } |
40 |
28 |
0^{3}1^{4}0^{21} |
{4^{2}, 5^{3},0^{21}, , } |
54 |
28 |
0^{17}1^{9}0^{2} |
{9^{16}, 24^{8},0^{2}, , } |
54 |
40 |
0^{29}1^{8}0^{3} |
{8^{28}, 35^{7},0^{3}, , } |
78 |
40 |
0^{30}1^{6}0^{4} |
{6^{29}, 34^{5},0^{4}, , } |
78 |
45 |
0^{32}1^{3}0^{10} |
{3^{31}, 33^{2},0^{10}, , } |
88 |
45 |
0^{9}1^{3}0^{33} |
{3^{8}, 10^{2},0^{33}, , } |
88 |
51 |
0^{38}1^{10}0^{3} |
{10^{37}, 46^{9},0^{3}, , } |
100 |
51 |
0^{40}1^{6}0^{5} |
{6^{39}, 44^{5},0^{5}, , } |
100 |
64 |
0^{47}1^{3}0^{14} |
{3^{46}, 48^{2},0^{14}, , } |
126 |
64 |
0^{13}1^{3}0^{48} |
{3^{12}, 14^{2},0^{48}, , } |
126 |
100 |
0^{68}1^{30}0^{2} |
{30^{67}, 30^{29},0^{2}, , } |
198 |
100 |
0^{81}1^{4}0^{15} |
{4^{80}, 119^{3},0^{15}, , } |
198 |
Referências
Fritscher, E., Trevisan, V. (2016). Exploring symmetries to decompose matrices and graphs preserving the spectrum. SIAM J Matrix Anal Appl, 37, 260–289.
Gong, S., Li, X., Xu, G., Gutman, I., Furtula, B. (2015). Borderenergetic graphs. MATCH Commun Math Comput Chem, 74, 321–332.
Hou, Y., Tao, Q. (2016). Borderenergetic threshold graphs. MATCH Commun Math Comput Chem, 75, 253–262.
Jacobs, D. P., Trevisan, V., Tura, F. (2015). Eigenvalues and energy in threshold graphs. Lin Algebra Appl, 465, 412–425.
Li, X., Shi, Y., Gutman, I. (2012). Graph Energy. Springer, New York.
Li, X., Wei, M., Gong, S. (2015). A computer search for the borderenergetic graphs of order 10. MATCH Commun Math Comput Chem, 74, 333–342.
Mahadev, N. V. R., Peled, U. N. (1995). Threshold graphs and related topics. Elsevier.
Shao, Z., Deng, F. (2016). Correcting the number of borderenergetic graphs of order 10. MATCH Commun Math Comput Chem, 75, 263–266.
Tao, Q., Hou, Y. (2018). Q-borderenergetic graphs. AKCE International Journal of Graphs and Combinatorics.
Tura, F. (2017). L-borderenergetic graphs. MATCH Commun Math Comput Chem, 77, 37–44.
Yu, L., Zhang, Y., Jian, G., Gutman, I. (2016). More on borderenergetic graphs. Lin Algebra Appl, 497, 199–208.
Copyright (c) 2020 Ciência e Natura
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
DEAR AUTHORS,
PLEASE, CHECK CAREFULLY BEFORE YOUR SUBMISSION:
1. IF ALL AUTHORS "METADATA" (ORCID, LINK TO LATTES, SHORT BIOGRAPHY, AFFILIATION) WERE ADDED,
2. THE CORRECT IDIOM YOUR SECTION,
3 IF THE HIGHLIGHTS WERE ADDED,
4. IF THE GRAPHIC ABSTRACTS WAS ADDED,
5. IF THE REVIEWERS INDICATION WAS DONE,
6. IF THE REFERENCES FORMAT ARE CORRECT(ABNT)
7. IF THE RESOLUTION YOUR FIGURES (600 DPI) ARE SUITABLE
8. IF THE STATEMENT BY THE ETHICS COMMITTEE (IF IT INVOLVES HUMANS) WAS ADDED;
9. IF THE DECLARATION OF ORIGINALITY WAS ADDED.
10. IF THE TEXT IS ORIGINAL. IF THE IDEA HAS ALREADY BEEN REGISTERED IN SUMMARY FORM, OR PUBLISHED IN CONGRESS ANNUALS, PLEASE INFORM THE EDITOR.