Laplacian integral graphs with a given degreee sequence constraint

Authors

  • Anderson Fernandes Fernandes Novanta Centro Federal de Educación Tecnológica Celso Suckow da Fonseca.
  • Carla Silva Oliveira Escola Nacional de Ciências Estatísticas.
  • Leonardo de Lima Universidade Federal do Parana.

DOI:

https://doi.org/10.22199/issn.0717-6279-4735

Keywords:

Laplacian matrix, Eigenvalues, L-integral graphs

Abstract

Let G be a graph on n vertices. The Laplacian matrix of G, denoted by L(G), is defined as L(G) = D(G) − A(G), where A(G) is the adjacency matrix of G and D(G) is the diagonal matrix of the vertex degrees of G. A graph G is said to be L-integral is all eigenvalues of the matrix L(G) are integers. In this paper, we characterize all L-integral non-bipartite graphs among all connected graphs with at most two vertices of degree larger than or equal to three.

Author Biography

Anderson Fernandes Fernandes Novanta, Centro Federal de Educación Tecnológica Celso Suckow da Fonseca.

Programa de Pós-Graduação em Engenharia de Produção e Sistemas.

References

A. E. Brouwer and W. H. Haemers, Spectra of graphs. New York,NY: Springer, 2012.

M. Fiedler. “Algebraic connectivity of graphs”, Czechoslovak mathematical journal, vol. 23, pp. 298-305, 1973.

R. Grone and R. Merris, “The laplacian spectrum of a graph”, SIAM Journal discrete mathematics, vol. 7, pp. 221-229, 1994.

J. van den Heuvel, “Hamilton cycles and eigenvalues of graphs”, Linear algebra and its applications, vol. 226-228, pp. 723-730, 1995.

R. A. Horn and C. R. Johnson, Matrix analysis, 2nd ed. Cambridge: Cambridge University Press, 2013.

P. Hof and D. Paulusma, “A new characterization of P6-free graphs”, Discrete applied mathematics, vol. 158, pp. 731-740, 2010.

S. J. Kirkland, J. J. Molitierno, M. Neumann, and B. L. Shader, “On graphs with equal algebraic and vertex connectivity”, Linear algebra and its applications, vol. 341, pp. 45-56, 2002.

S. J. Kirkland, “Constructably laplacian integral graphs”, Linear algebra and its applications, vol. 423, pp. 3-21, 2007.

S. J. Kirkland, “Laplacian integral graphs with maximum degree 3”, The electronic journal of combinatorics, vol. 15, Art. ID. 120, 2008.

L. S. de Lima, N. M. de Abreu, and C. S. Oliveira, “Laplacian integral graphs in S(a,b)”, Linear algebra and its applications, vol. 423, pp. 136-145, 2007.

R. Merris, “Degree maximal graphs are laplacian integral”, Linear algebra and its applications, vol. 199, pp. 381-389, 1994.

R. Merris, “Laplacian graph eigenvectores”, Linear algebra and its applications, vol. 278, pp. 221-236, 1998.

A. F. Novanta, L. S. de Lima, and C. S. Oliveira, “Q-integral graphs with at most two vertices of degree greater than or equal to three”, Linear algebra and its applications, vol. 614, pp. 144-163, 2021.

Published

2021-06-24

How to Cite

[1]
A. F. Fernandes Novanta, C. Silva Oliveira, and L. de Lima, “Laplacian integral graphs with a given degreee sequence constraint”, Proyecciones (Antofagasta, On line), vol. 40, no. 6, pp. 1431-1448, Jun. 2021.

Issue

Section

Artículos

Most read articles by the same author(s)