Bounds on the parameters of non-$L$-borderenergetic graphs

Cahit Dede; Ayşe Dilek Maden

doi:10.3842/umzh.v75i9.7243

Cahit Dede Department of Mathematics, Selçuk University, Konya, Turkey
Ayşe Dilek Maden Department of Mathematics, Selçuk University, Konya, Turkey

DOI: https://doi.org/10.3842/umzh.v75i9.7243

Keywords: Graph energy, Laplacian matrix, borderenergetic graph, Zagreb index

Abstract

UDC 519.17

We consider graphs such that their Laplacian energy is equivalent to the Laplacian energy of the complete graph of the same order, which is called an $L$-borderenergetic graph. Firstly, we study the graphs with degree sequence consisting of at most three distinct integers and give new bounds for the number of vertices of these graphs to be non-$L$-borderenergetic. Second, by using Koolen–Moulton and McClelland inequalities, we give new bounds for the number of edges of a non-$L$-borderenergetic graph. Third, we use recent bounds given by Milovanovic, et al. on Laplacian energy to get similar conditions for non-$L$-borderenergetic graphs. Our bounds depend only on the degree sequence of a graph, which is much easier than computing the spectrum of the graph. In other words, we developed a faster approach to exclude non-$L$-borderenergetic graphs.

References

W. N. Anderson (Jr.), T. D. Morley, Eigenvalues of the Laplacian of a graph, Linear and Multilinear Algebra, 18, № 2, 141–145 (1985). DOI: https://doi.org/10.1080/03081088508817681

D. Cvetković, P. Rowlinson, S. K. Simić, Signless Laplacians of finite graphs, Linear Algebra and Appl., 423, № 1, 155–171 (2007). DOI: https://doi.org/10.1016/j.laa.2007.01.009

K. Ch. Das, S. A. Mojallal, On Laplacian energy of graphs, Discrete Math., 325, 52–64 (2014). DOI: https://doi.org/10.1016/j.disc.2014.02.017

K. Ch. Das, S. A. Mojallal, I. Gutman, On Laplacian energy in terms of graph invariants, Appl. Math. and Comput., 268, 83–92 (2015). DOI: https://doi.org/10.1016/j.amc.2015.06.064

C. Dede, A. D. Maden, Garden of Laplacian borderenergetic graphs, MATCH Commun. Math. Comput. Chem., 86, 597–610 (2021).

Bo Deng, Xueliang Li, On $L$-borderenergetic graphs with maximum degree at most $4$, MATCH Commun. Math. Comput. Chem., 79, 303–310 (2018).

Bo Deng, Xueliang Li, I. Gutman, More on borderenergetic graphs, Linear Algebra and Appl., 497, 199–208 (2016). DOI: https://doi.org/10.1016/j.laa.2016.02.029

H. A. Ganie, B. A. Chat, S. Pirzada, Signless Laplacian energy of a graph and energy of a line graph, Linear Algebra and Appl., 544, 306–324 (2018). DOI: https://doi.org/10.1016/j.laa.2018.01.021

H. A. Ganie, Sh. Pirzada, On the bounds for signless Laplacian energy of a graph, Discrete Appl. Math., 228, 3–13 (2017). DOI: https://doi.org/10.1016/j.dam.2016.09.030

H. A. Ganie, Sh. Pirzada, A. Iv`anyi, Energy, Laplacian energy of double graphs and new families of equienergetic graphs, Acta Univ. Sapientiae, Informatica, 6, № 1, 89–116 (2014). DOI: https://doi.org/10.2478/ausi-2014-0020

Sh. Gong, Xueliang Li, Guanghui Xu, I. Gutman, B. Furtula, Borderenergetic graphs, MATCH Commun. Math. Comput. Chem., 74, № 2, 321–332 (2015).

I. Gutman, The energy of a graph: old and new results, Algebraic Combinatorics and Applications, Springer (2001), p. 196–211. DOI: https://doi.org/10.1007/978-3-642-59448-9_13

I. Gutman, Bo Zhou, Laplacian energy of a graph, Linear Algebra and Appl., 414, № 1, 29–37 (2006). DOI: https://doi.org/10.1016/j.laa.2005.09.008

M. Hakimi-Nezhaad, M. Ghorbani, Laplacian borderenergetic graphs, J. Inform. and Optim. Sci., 40, № 6, 1237–1264 (2019). DOI: https://doi.org/10.1080/02522667.2018.1480468

D. P Jacobs, V. Trevisan, F. Tura, Eigenvalues and energy in threshold graphs, Linear Algebra and Appl., 465, 412–425 (2015). DOI: https://doi.org/10.1016/j.laa.2014.09.043

D. J. Klein, V. R. Rosenfeld, Phased graphs and graph energies, J. Math. Chem., 49, № 7, 1238–1244 (2011). DOI: https://doi.org/10.1007/s10910-011-9814-7

Xueliang Li, Yongtang Shi, I. Gutman, Graph energy, Springer Sci. & Business Media (2012). DOI: https://doi.org/10.1007/978-1-4614-4220-2

R. Merris, Laplacian matrices of graphs: a survey, Linear Algebra and Appl., 197, 143–176 (1994). DOI: https://doi.org/10.1016/0024-3795(94)90486-3

I. Milovanovic, M. Matejic, P. Milosevic, E. Milovanovic, A. Ali, A note on some lower bounds of the Laplacian energy of a graph, Trans. Comb., 8, № 2, 13–19 (2019).

V. Nikiforov, The energy of graphs and matrices, J. Math. Anal. and Appl., 326, № 2, 1472–1475 (2007). DOI: https://doi.org/10.1016/j.jmaa.2006.03.072

S. Pirzada, H. A. Ganie, On the Laplacian eigenvalues of a graph and Laplacian energy, Linear Algebra and Appl., 486, 454–468 (2015). DOI: https://doi.org/10.1016/j.laa.2015.08.032

H. Taheri, G. H. Fath-Tabar, New upper bound on the largest Laplacian eigenvalue of graphs, Facta Univ. Ser. Math. and Inform., 35, № 2, 533–540 (2020). DOI: https://doi.org/10.22190/FUMI2002533T

The Sage Developers, SageMath, the Sage Mathematics Software System (Version 9.1.0), (2021); https// www.sagemath.org.

F. Tura, $L$-borderenergetic graphs, MATCH Commun. Math. Comput. Chem., 77, 37–44 (2017).

S. K. Vaidya, K. M. Popat, Construction of sequences of borderenergetic graphs, Proyecciones, 38, № 4, 837–847 (2019). DOI: https://doi.org/10.22199/issn.0717-6279-2019-04-0055