Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Introduction Kapitel lesen Erstes Kapitel lesen

2018 | OriginalPaper | Buchkapitel

A Conjecture on Laplacian Eigenvalues of Trees

verfasst von : David P. Jacobs, Vilmar Trevisan

Erschienen in: Graph Theory

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

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.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Vorheriges Kapitel Binding Number, Cycles, and Cliques
Nächstes Kapitel Queens Around the World in Twenty-Five Years
Literatur
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.
E. Hückel, Quantentheoretische beitrage zum benzolproblem. Z. Phys. 70, 204–286 (1931)MATHCrossRef
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.
D.P. Jacobs, V. Trevisan, Locating the eigenvalues of trees. Linear Algebra Appl. 434(1), 81–88 (2011). MR 2737233 (2012b:15017)MathSciNetMATHCrossRef
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.
V. Nikiforov, Chromatic number and spectral radius. Linear Algebra Appl. 426(2–3), 810–814 (2007). MR 2350692 (2008h:05080)MathSciNetMATHCrossRef
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.
H.S. Wilf, The eigenvalues of a graph and its chromatic number. J. Lond. Math. Soc. 42, 330–332 (1967). MR 0207593 (34 #7408)MathSciNetMATHCrossRef
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)
Metadaten
Titel
A Conjecture on Laplacian Eigenvalues of Trees
verfasst von
David P. Jacobs
Vilmar Trevisan
Copyright-Jahr
2018
Buch
Graph Theory

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

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

Copyright-Jahr: 2018

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

Premium Partner

    Bildnachweise