Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Introduction Read chapter Read first chapter

2018 | OriginalPaper | Chapter

A Conjecture on Laplacian Eigenvalues of Trees

Authors : David P. Jacobs, Vilmar Trevisan

Published in: Graph Theory

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Motivated by classic tree algorithms, in 1995 we designed a bottom-up O(n) algorithm to compute the determinant of a tree’s adjacency matrix A. In 2010 an O(n) algorithm was found for constructing a diagonal matrix congruent to A + xI n, \(x \in \mathbb {R}\), enabling one to easily count the number of eigenvalues in any interval. A variation of the algorithm allows Laplacian eigenvalues in trees to be counted. We conjecture that for any tree T of order n ≥ 2, at least half of its Laplacian eigenvalues are less than \(\bar {d} = 2 - \frac {2}{n} \), its average vertex degree.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Binding Number, Cycles, and Cliques
next chapter Queens Around the World in Twenty-Five Years
Literature
1.
2.
N. Abreu, Old and new results on algebraic connectivity of graphs. Linear Algebra Appl. 423(1), 53–73 (2007). MR 2312323 (2008b:05096)
3.
N. Abreu, C.M. Justel, O. Rojo, V. Trevisan, Ordering trees and graphs with few cycles by algebraic connectivity. Linear Algebra Appl. 458, 429–453 (2014). MR 3231826MathSciNetMATHCrossRef
4.
Z. Bai, C. Bischof, S. Blackford, J. Demmel, J. Dongarra, J. Du Croz, A. Greenbaum, S. Hammarling, A. McKenney, D. Sorensen, LAPACK User Guide, 3rd edn. (SIAM, Philadelphia, 1999)MATH
5.
6.
P. Bonacich, Power and centrality: a family of measures. Am. J. Soc. 92(5), 1170–1182 (1987)CrossRef
7.
R.O. Braga, V.M. Rodrigues, V. Trevisan, On the distribution of Laplacian eigenvalues of trees. Discrete Math. 313(21), 2382–2389 (2013). MR 3091280MathSciNetMATHCrossRef
8.
A.E. Brouwer, W.H. Haemers, Spectra of Graphs. Universitext (Springer, New York, 2012). MR 2882891MATHCrossRef
9.
P. Bürgisser, M. Clausen, M.A. Shokrollahi, Algebraic complexity theory, in Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 315 (Springer, Berlin, 1997). With the collaboration of Thomas Lickteig. MR 1440179 (99c:68002)
10.
11.
E.J. Cockayne, S.E. Goodman, S.T. Hedetniemi, A linear algorithm for the domination number of a tree. Inf. Proc. Lett. 4, 41–44 (1975)MATHCrossRef
12.
D.M. Cvetković, Graphs and their spectra. Univ. Beograd. Publ. Elektrotehn. Fak. Ser. Mat. Fiz. (354–356), 1–50 (1971). MR 0299508 (45 #8556)
13.
D.E. Daykin, C.P. Ng, Algorithms for generalized stability numbers of tree graphs. J. Aust. Math. Soc. 6, 89–100 (1966). MR 0195756 (33 #3954)MathSciNetMATHCrossRef
14.
M. Fiedler, Algebraic connectivity of graphs. Czechoslovak Math. J. 23(2), 298–305 (1973). MR 0318007 (47 #6556)
15.
M. Fiedler, A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory. Czechoslovak Math. J. 25(4), 619–633 (1975). MR 0387321 (52 #8164)
16.
M. Fiedler, V. Nikiforov, Spectral radius and Hamiltonicity of graphs. Linear Algebra Appl. 432(9), 2170–2173 (2010). MR 2599851 (2011a:05195)MathSciNetMATHCrossRef
17.
G.H. Fricke, S.T. Hedetniemi, D.P. Jacobs, V. Trevisan, Reducing the adjacency matrix of a tree. Electron. J. Linear Algebra 1, 34–43 (1996). MR 1412944 (97g:05122)
18.
E. Fritscher, C. Hoppen, I. Rocha, V. Trevisan, On the sum of the Laplacian eigenvalues of a tree. Linear Algebra Appl. 435(2), 371–399 (2011). MR 2782788 (2012a:05182)MathSciNetMATHCrossRef
19.
R. Grone, R. Merris, V.S. Sunder, The Laplacian spectrum of a graph. SIAM J. Matrix Anal. Appl. 11(2), 218–238 (1990). MR 1041245 (91c:05130)MathSciNetMATHCrossRef
20.
21.
S.T. Hedetniemi, Unsolved algorithmic problems on trees. AKCE Int. J. Graphs Comb. 3(1), 1–37 (2006). MR 2232404 (2007f:05166)
22.
S.T. Hedetniemi, D.P. Jacobs, V. Trevisan, Domination number and laplacian eigenvalue distribution. European Journal of Combinatorics 53, 66–71 (2016)MathSciNetMATHCrossRef
23.
A.J. Hoffman, On eigenvalues and colorings of graphs, in Graph Theory and its Applications,Proceedings of Advanced Seminar conducted by the Mathematics Research Center, University of Wisconsin, Madison, WI, 1969 (Academic Press, New York, 1970), pp. 79–91. MR 0284373 (44 #1601)
24.
25.
D.P. Jacobs, V. Trevisan, Constructing the characteristic polynomial of a tree’s adjacency matrix, in Proceedings of the Twenty-ninth Southeastern International Conference on Combinatorics, Graph Theory and Computing (Boca Raton, FL, 1998), vol. 134 (1998), pp. 139–145. MR 1676541 (99j:05138)
26.
D.P. Jacobs, V. Trevisan, Linear-time LUP decomposition of forest-like matrices. Comput. Math. Appl. 37(10), 37–50 (1999). MR 1687980 (2000a:65032)MathSciNetMATHCrossRef
27.
28.
D.P. Jacobs, C.M.S. Machado, V. Trevisan, An O(n 2) algorithm for the characteristic polynomial of a tree. J. Combin. Math. Combin. Comput. 54, 213–221 (2005). MR 2143242 (2006a:05153)
29.
D.P. Jacobs, C.M.S. Machado, E.C. Pereira, V. Trevisan, Computing the inverse of a tree’s incidence matrix, in Proceedings of the Thirty-Ninth Southeastern International Conference on Combinatorics, Graph Theory and Computing, vol. 189 (2008), pp. 169–176. MR 2489782
30.
D.P. Jacobs, M.O. Rayes, V. Trevisan, Characterization of Chebyshev numbers. Algebra Discrete Math. (2), 65–82 (2008). MR 2484592 (2009j:11199)
31.
D.P. Jacobs, M.O. Rayes, V. Trevisan, Randomized compositeness testing with Chebyshev polynomials. Int. J. Pure Appl. Math. 44(3), 347–362 (2008). MR 2412208
32.
G. Kirchhoff, Über die auflösung der gleichungen, auf welche man bei der untersuchung der linearen verteilung galvanisher ströme gerfuht wird. Ann. Phys. Chem. 72, 497–508 (1847). English transl. IRE Trans. Circuit Theory, CT-5:4–7, 1958CrossRef
33.
M. Lu, H. Liu, F. Tian, Bounds of Laplacian spectrum of graphs based on the domination number. Linear Algebra Appl. 402, 390–396 (2005). MR 2141097 (2006a:05091)MathSciNetMATHCrossRef
34.
35.
R. Merris, Laplacian matrices of graphs: a survey, Linear Algebra Appl. 197–198, 143–176 (1994). Second Conference of the International Linear Algebra Society (ILAS) (Lisbon, 1992). MR 1275613 (95e:05084)MathSciNetMATHCrossRef
36.
H. Minc, M. Marcus, Introduction to Linear Algebra (The Macmillan, New York/Collier-Macmillan, London, 1965). MR 0188221 (32 #5660)
37.
B. Mohar, The Laplacian spectrum of graphs, in Graph Theory, Combinatorics, and Applications, vol. 2, Kalamazoo, MI, 1988 (Wiley, New York, 1991), pp. 871–898. MR 1170831 (93b:05116)
38.
B. Mohar, Laplace eigenvalues of graphs—a survey. Discrete Math. 109(1–3), 171–183 (1992). Algebraic graph theory (Leibnitz, 1989). MR 1192380 (93m:05133)MathSciNetMATHCrossRef
39.
40.
41.
V. Nikiforov, The influence of Miroslav Fiedler on spectral graph theory. Linear Algebra Appl. 439(4), 818–821 (2013). MR 3061737MathSciNetMATHCrossRef
42.
A.J. Schwenk, Almost all trees are cospectral, in New Directions in the Theory of Graphs Proceedings of Third Ann Arbor Conference, University of Michigan, Ann Arbor, MI, 1971 (Academic Press, New York, 1973), pp. 275–307. MR 0384582 (52 #5456)
43.
V. Trevisan, J.B. Carvalho, R.R. Del Vecchio, C.T.M. Vinagre, Laplacian energy of diameter 3 trees. Appl. Math. Lett. 24(6), 918–923 (2011). MR 2776161 (2012g:05144)MathSciNetMATHCrossRef
44.
E.R. van Dam, W.H. Haemers, Which graphs are determined by their spectrum? Linear Algebra Appl. 373, 241–272 (2003). Special issue on the Combinatorial Matrix Theory Conference (Pohang, 2002). MR 2022290 (2005a:05135)
45.
46.
47.
T.V. Wimer, S.T. Hedetniemi, R. Laskar, A methodology for constructing linear graph algorithms, in Proceedings of the Sundance conference on combinatorics and related topics Sundance, Utah, 1985, vol. 50 (1985), pp. 43–60. MR 833536 (87h:68074)
Metadata
Title
A Conjecture on Laplacian Eigenvalues of Trees
Authors
David P. Jacobs
Vilmar Trevisan
Copyright Year
2018
Book
Graph Theory

Print ISBN: 978-3-319-97684-6

Electronic ISBN: 978-3-319-97686-0

Copyright Year: 2018

DOI
https://doi.org/10.1007/978-3-319-97686-0_4

Premium Partner

    Image Credits