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 Marquez Sosa^II

Fernando Colman Tura^III

^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 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 = µ₁ ≤ µ₂ ≤ ... ≤ µ_n and 0 ≤ q₁ ≤ q₂ ≤ q₃ ≤ ... ≤ 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₂, C₄, and P₄. 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₁b₂ ...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₁ to be zero.

For example, the Figure 1, shows a threshold graph G with creation sequence (00010001) or (0³10³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^a1^b0^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^a1^b0^c) of order n = a + b + c has signless Laplacian spectrum equals

σ(G) = {b^a−1,(b + a − 2)^b−1,0^c,q₂,q₁}                                                                                 (3)

where  and .

Lemma 1. Let G be a threshold graph with creation sequence (0^a1^b0^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₁ and đ ≤ q₂.

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₁. The proof is similar for đ ≤ q₂.

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₁ ≤ q₂ ≤ ... ≤ 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^a1^b0^c) of order n = a + b + c and signless Laplacian eigenvalues given by (3). Let đ be the average degree of G with đ ≤ q₁,q₂. 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^a1^b0^c) of order n = a + b + c and signless Laplacian eigenvalues given by (3). Let đ be the average degree of G with đ ≤ q₁,q₂. If there are positive integers a,b,c satisfying

(b² +2ab − b)c = (a + b + c)² − (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^a1^b0^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₁,q₂. 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.