Two conjectures on the cospectrality of complete tripartite graphs are false
Abstract
For a graph G of order n with adjacency eigenvalues lambda_1(G) >= ... >= lambda_n(G), the cospectrality of G within the set G of all graphs of order n is the smallest spectral distance from G to another graph of G. Abdollahi and Zakeri conjectured that for every n >= 4 the cospectrality of the complete tripartite graph K_{n,n,n}, both in the Manhattan and in the Euclidean spectral distance, is attained precisely at K_{n-1,n,n+1}. We show that both conjectures are false for every n >= 4, that is, in the whole range in which they are stated. The counterexample is the graph H_n obtained from K_{n-1,n,n} by adding a vertex adjacent to the part of cardinality n - 1, and it is the natural generalization of the graph which the authors themselves exhibited for n = 3 and considered to be exceptional. We determine the spectrum of H_n in a closed form, and we show that the two spectral distances tend to 1 and to 1/2 respectively, instead of to (2*sqrt(3))/3 and to 2/3 as conjectured. On the other hand, we show that in the Euclidean distance the conjecture becomes asymptotically true when the competing graphs are restricted to complete multipartite graphs, so that it fails because a graph of rank four beats the conjectured minimizer.
Related
- Strong Lefschetz property of the Kirchhoff algebra of the complete tripartite graph K1,1,n
- On the maximum number of triangles in tripartite graphs with no $4$-cycles between any two parts
- On the minimum number of triangles in balanced tripartite graphs with large minimum degree
- Counterexamples to two conjectures on the diameter of clique-free graphs
- Admissibility and Complete Classes for False Discovery Rate Control with E-values
BibTeX
@misc{jovanovic2026conjectures,
title = {{Two conjectures on the cospectrality of complete tripartite graphs are false}},
author = {Irena M. Jovanović and Jelena Sedlar and Riste Škrekovski},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.18636},
eprint = {2610.18636},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.18636},
}
RIS
TY - UNPB
TI - Two conjectures on the cospectrality of complete tripartite graphs are false
AU - Irena M. Jovanović
AU - Jelena Sedlar
AU - Riste Škrekovski
PY - 2026
DA - 2026/10/13
PB - arXiv
DO - 10.48550/arxiv.2610.18636
UR - https://arxiv.org/abs/2610.18636
AB - For a graph G of order n with adjacency eigenvalues lambda_1(G) >= ... >= lambda_n(G), the cospectrality of G within the set G of all graphs of order n is the smallest spectral distance from G to another graph of G. Abdollahi and Zakeri conjectured that for every n >= 4 the cospectrality of the complete tripartite graph K_{n,n,n}, both in the Manhattan and in the Euclidean spectral distance, is attained precisely at K_{n-1,n,n+1}. We show that both conjectures are false for every n >= 4, that is, in the whole range in which they are stated. The counterexample is the graph H_n obtained from K_{n-1,n,n} by adding a vertex adjacent to the part of cardinality n - 1, and it is the natural generalization of the graph which the authors themselves exhibited for n = 3 and considered to be exceptional. We determine the spectrum of H_n in a closed form, and we show that the two spectral distances tend to 1 and to 1/2 respectively, instead of to (2*sqrt(3))/3 and to 2/3 as conjectured. On the other hand, we show that in the Euclidean distance the conjecture becomes asymptotically true when the competing graphs are restricted to complete multipartite graphs, so that it fails because a graph of rank four beats the conjectured minimizer.
ER -