Annals of Mathematical Sciences and Applications

Volume 2 (2017)

Number 2

Guest Editors: Tai-Chia Lin (National Taiwan University), Wen-Wei Lin (National Chiao Tung University), Tony Wen-Hann Sheu (National Taiwan University), Weichung Wang (National Taiwan University), Chih-wen Weng (National Chiao Tung University), and Salil Vadhan (Harvard University).

Spectral characterizations of two families of nearly complete bipartite graphs

Pages: 241 – 254

DOI: https://dx.doi.org/10.4310/AMSA.2017.v2.n2.a2

Authors

Chia-An Liu (Department of Financial and Computational Mathematics, I-Shou University, Kaohsiung, Taiwan)

Chih-Wen Weng (Department of Applied Mathematics, National Chiao-Tung University, Hsinchu, Taiwan)

Abstract

It is not hard to find many complete bipartite graphs which are not determined by their spectra. We show that the graph obtained by deleting an edge from a complete bipartite graph is determined by its spectrum. We provide some graphs, each of which is obtained from a complete bipartite graph by adding a vertex and an edge incident on the new vertex and an original vertex, which are not determined by their spectra.

Keywords

bipartite graph, adjacency matrix, determined by the spectrum (DS)

2010 Mathematics Subject Classification

Primary 05C50. Secondary 15A18.

Received 3 March 2016

Published 10 August 2017