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 LazzarinI

Oscar Franscisco Másquez SosaII

Fernando Colman TuraIII

IUniversidade Federal de Santa Maria, Santa Maria, Rio Grande do Sul, Brasil - joaolazzarin@gmail.com

IIUniversidade Federal de Santa Maria, Santa Maria, Rio Grande do Sul, Brasil - omskar@gmail.com

IIIUniversidade 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 Kn, i.e., QE(G) = QE(Kn) = 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 Kn, i.e., E(G) = E(Kn) = 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 ≤ q1 q2 q3 ... qn 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(Kn) (QE(G) = QE(Kn), 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 2K2, C4, and P4. 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 (b1b2 ...bn). Here bi = 0 if a vertex vi was added as an isolated vertex, and bi = 1 if vi was added as a dominating vertex. We call our representation a creation sequence, and always take b1 to be zero.

For example, the Figure 1, shows a threshold graph G with creation sequence (00010001) or (031031).

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 (0a1b0c), 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 (0a1b0c) of order n = a + b + c has signless Laplacian spectrum equals

σ(G) = {ba−1,(b + a − 2)b−1,0c,q2,q1}                                                                                 (3)

where  and .

Lemma 1. Let G be a threshold graph with creation sequence (0a1b0c) of order n = a + b + c. Let d be the average degree of G. There exist positive integers a,b,c ≥ 1 satisfying d q1 and đ q2.

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, đ ≤ q1. The proof is similar for đ ≤ q2.

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 = q1 ≤ q2 ≤ ... ≤ qn are the signless Laplacian eigenvalues of G and d is the average degree of G. It is known that the complete graph Kn 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 (0a1b0c) of order n = a + b + c and signless Laplacian eigenvalues given by (3). Let đ be the average degree of G with đ ≤ q1,q2. 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 (0a1b0c) of order n = a + b + c and signless Laplacian eigenvalues given by (3). Let đ be the average degree of G with đ ≤ q1,q2. If there are positive integers a,b,c satisfying

(b2 +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 (0a1b0c) of order n = a + b + c and signless Laplacian eigenvalues given by (3). Let d be the average degree of G with d ≤ q1,q2. 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

0214015

{24, 015, , }

40

28

0314021

{42, 53,021, , }

54

28

0171902

{916, 248,02, , }

54

40

0291803

{828, 357,03, , }

78

40

0301604

{629, 345,04, , }

78

45

03213010

{331, 332,010, , }

88

45

0913033

{38, 102,033, , }

88

51

03811003

{1037, 469,03, , }

100

51

0401605

{639, 445,05, , }

100

64

04713014

{346, 482,014, , }

126

64

01313048

{312, 142,048, , }

126

100

06813002

{3067, 3029,02, , }

198

100

08114015

{480, 1193,015, , }

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

Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

Creative Commons 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.