Hostname: page-component-78c5997874-m6dg7 Total loading time: 0 Render date: 2024-11-17T23:20:27.436Z Has data issue: false hasContentIssue false
  • English
  • Français

A deletion-contraction algorithm for the characteristic polynomial of a multigraph

Published online by Cambridge University Press:  14 November 2011

Peter Rowlinson
Peter Rowlinson
Affiliation:
Department of Mathematics, University of Stirling, Stirling FK9 4LA, Scotland
Get access Rights & Permissions [Opens in a new window]

Synopsis

The characteristic polynomial of a finite multigraph G is expressed in terms of characteristic polynomials oflocal modifications of G. The resulting formula is used to investigate the largest eigenvalues of certain theta graphs.

Type
Research Article
Information
Proceedings of the Royal Society of Edinburgh Section A: Mathematics , Volume 105 , Issue 1 , 1987 , pp. 153 - 160
Copyright
Copyright © Royal Society of Edinburgh 1987

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1Birkhoff, G. D. and Lewis, D.. Chromatic polynomials. Trans. Amer. Math. Soc. 60 (1946), 355–241.Google Scholar
2Cvetković, D. M., Doob, M. and Sachs, H.. Spectra of Graphs (New York: Academic Press, 1979).Google Scholar
3Cvetković, D. M., Doob, M., Gutman, I. and Torgašev, A.. Recent Results in the Theory of Graph Spectra (Amsterdam: North-Holland, 1986).Google Scholar
4Heilbronner, E.. Das Kompositions-Prinzip: eine anschauliche Methode zur elektro-theoretischen Bedhandlung nicht oder niedrig symmetrischer Molekeln im Rahmen der MO-Theorie. Helv. Chim. Acta 36 (1953), 170–188.Google Scholar
5Sachs, H. (ed.). Graphs, Hypergraphs and Applications, Teubner–Texte zur Mathematik, Band 73 (Leipzig: Teubner Verlagsgesellschaft, 1985).Google Scholar
6Schwenk, A. J.. Computing the characteristic polynomial of a graph. In Graphs and Combinatorics, Proceedings of the Capital Conference on Graph Theory and Combinatorics, eds. Bari, R. A. and Harary, F., pp. 153–172. Lecture Notes in Mathematics 406 (New York: Springer, 1974).Google Scholar
7Wilson, R. J. and Beineke, L. W. (eds.). Applications of Graph Theory (New York: Academic Press, 1979).Google Scholar
8Woodall, D. R.. Zeros of chromatic polynomials. In Combinatorial Surveys, Proceedings of the Sixth British Combinatorial Conference, ed. Cameron, P. J., pp. 199–223 (London: Academic Press, 1977).Google Scholar