1 Search Results for "Rangarajan, Bharatram"

Document
DOI: 10.4230/LIPIcs.FSTTCS.2017.46
A Combinatorial Proof of Ihara-Bass's Formula for the Zeta Function of Regular Graphs

Authors: Bharatram Rangarajan

Published in: LIPIcs, Volume 93, 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)

Abstract
We give an elementary combinatorial proof of Bass's determinant formula for the zeta function of a finite regular graph. This is done by expressing the number of non-backtracking cycles of a given length in terms of Chebyshev polynomials in the eigenvalues of the adjacency operator of the graph. A related observation of independent interest is that the Ramanujan property of a regular graph is equivalent to tight bounds on the number of non-backtracking cycles of every length.
Cite as

Bharatram Rangarajan. A Combinatorial Proof of Ihara-Bass's Formula for the Zeta Function of Regular Graphs. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 93, pp. 46:1-46:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{rangarajan:LIPIcs.FSTTCS.2017.46,
  author =	{Rangarajan, Bharatram},
  title =	{{A Combinatorial Proof of Ihara-Bass's Formula for the Zeta Function of Regular Graphs}},
  booktitle =	{37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017)},
  pages =	{46:1--46:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-055-2},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{93},
  editor =	{Lokam, Satya and Ramanujam, R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2017.46},
  URN =		{urn:nbn:de:0030-drops-83861},
  doi =		{10.4230/LIPIcs.FSTTCS.2017.46},
  annote =	{Keywords: non-backtracking, Ihara zeta, Chebyshev polynomial, Ramanujan graph, Hashimoto matrix}
}
  • Refine by Author
  • 1 Rangarajan, Bharatram

  • Refine by Classification

  • Refine by Keyword
  • 1 Chebyshev polynomial
  • 1 Hashimoto matrix
  • 1 Ihara zeta
  • 1 Ramanujan graph
  • 1 non-backtracking

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2018

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact