Computing the maximal signless Laplacian index among graphs of prescribed order and diameter

Authors

  • Nair Abreu Universidade Federal do Rio de Janeiro.
  • Eber Lenes Universidad del Sinu.
  • Óscar Rojo Universidad Católica del Norte.

DOI:

https://doi.org/10.4067/S0716-09172015000400006

Keywords:

Signless Laplacian index, Diameter, Bug, H-join.

Abstract

A bug Bugp,r1r2 is a graph obtained from a complete graph Kp by deleting an edge uv and attaching the paths Priand Pr2 by one of their end vertices at u and v, respectively. Let Q(G) be the signless Laplacian matrix of a graph G and q1(G) be the spectral radius of Q(G). It is known that the bug maximizes q1(G) among all graphs G of order n and diameter d. For a bug B of order n and diameter d, n - d is an eigenvalue of Q(B) with multiplicity n - d - 1. In this paper, we prove that remainder d +1 eigenvalues of Q(B), among them q1(B), can be computed as the eigenvalues of a symmetric tridiagonal matrix of order d +1. Finally, we show that q1(B0) can be computed as the largest eigenvalue of a symmetric tridiagonal matrix of order whenever d is even.

Author Biographies

Nair Abreu, Universidade Federal do Rio de Janeiro.

Production Engineering Program, PEP/COPPE.

Eber Lenes, Universidad del Sinu.

Departamento de Investigaciones.

Óscar Rojo, Universidad Católica del Norte.

Departamento de Matemáticas.

References

[1] D. M. Cardoso, M. A. A. de Freitas, E. Martins., M. Robbiano, Spectra of graphs obtained by a generalization of the join graph operation, Discrete Mathematics 313, pp. 733-741, (2013).

[2] D. M. Cardoso, E. Martins., M. Robbiano, O. Rojo, Eigenvalues of a H-generalized operation constrained by vertex subsets, Linear Algebra Appl. 438, pp. 3278-3290, (2013).

[3] H. Liu, M. Lu, A conjecture on the diameter and signless Laplacian index of graphs, Linear Algebra Appl. 450, pp. 158-174, (2014).

[4] D. Cvetkovi´c, P. Rowlinson, S.K. Simi´c, Eigenvalue bounds for the signless Laplacian, Publications de L’Institute Math´ematique, Nouvelle série, tome 81 (95), pp. 11-27, (2007).

[5] P. Hansen, C. Lucas, Bounds and conjectures for the signless Laplacian index of graphs, Linear Algebra Appl. 432, pp. 3319-3336, (2010).

[6] Miao-Lin Ye, Yi-Zheng Fan, Hai Feng Wang, Maximizing signless Laplacian or adjacency spectral radius of graphs subject to fixed connectivity, Linear Algebra Appl. 433, pp. 1180-1186, (2010).

[7] G. Yu, On the maximal signless Laplacian spectral radius of graphs with given matching number, Proc. Japan Acad. Ser. A 84, pp. 163- 166, (2008).

How to Cite

[1]
N. Abreu, E. Lenes, and Óscar Rojo, “Computing the maximal signless Laplacian index among graphs of prescribed order and diameter”, Proyecciones (Antofagasta, On line), vol. 34, no. 4, pp. 379-390, 1.

Issue

Section

Artículos