Spectral faux trees

Butler, Steve; D’Avanzo, Elena; Heikkinen, Rachel; Jeffries, Joel; Kruczek, Alyssa; Niergarth, Harper

doi:10.2140/involve.2024.17.651

Download this article
	For screen
	For printing

Recent Issues

The Journal

About the journal

Ethics and policies

Peer-review process

Submission guidelines

ISSN 1944-4184 (online)

ISSN 1944-4176 (print)

Author index

To appear

Other MSP journals

This article is available for purchase or by subscription. See below.

Spectral faux trees

Steve Butler, Elena D’Avanzo, Rachel Heikkinen, Joel Jeffries, Alyssa Kruczek and Harper Niergarth

Vol. 17 (2024), No. 4, 651–668

DOI: 10.2140/involve.2024.17.651

Abstract

A spectral faux tree with respect to a given matrix is a graph which is not a tree but is cospectral with a tree for the given matrix. We consider the existence of spectral faux trees for several matrices, with emphasis on constructions.

For the Laplacian matrix, there are no spectral faux trees. For the adjacency matrix, almost all trees are cospectral with a faux tree. For the signless Laplacian matrix, spectral faux trees can only exist when the number of vertices is of the form $n = 4 k$ . For the normalized adjacency, spectral faux trees exist when the number of vertices, $n$ , is at least 4, and we give an explicit construction for a family whose size grows exponentially with $k$ for $n = α k + 1$ , where $α$ is a fixed integer.

PDF Access Denied

We have not been able to recognize your IP address 18.97.9.172 as that of a subscriber to this journal.
Online access to the content of recent issues is by subscription, or purchase of single articles.

Please contact your institution's librarian suggesting a subscription, for example by using our journal-recommendation form. Or, visit our subscription page for instructions on purchasing a subscription.

You may also contact us at contact@msp.org
or by using our contact form.

Or, you may purchase this single article for USD 30.00:

Keywords

cospectral, trees, faux trees, signless Laplacian matrix, normalized adjacency matrix, characteristic polynomials

Mathematical Subject Classification

Primary: 05C50

Milestones

Received: 13 January 2023

Revised: 23 May 2023

Accepted: 27 May 2023

Published: 2 October 2024

Communicated by Glenn Hurlbert

Authors

Steve Butler
Iowa State University Ames, IA United States

Elena D’Avanzo
Carleton College Northfield, MN United States

Rachel Heikkinen
Augustana College Rock Island, IL United States

Joel Jeffries
Iowa State University Ames, IA United States

Alyssa Kruczek
Susquehanna University Selinsgrove, PA United States

Harper Niergarth
University of Minnesota–Twin Cities Minneapolis, MN United States

Vol. 17, No. 4, 2024