Triangle-free graphs with six non-zero eigenvalues

ABSTRACT

A graph G is called triangle-free if G does not contain a triangle as an induced subgraph. Let ${\mathcal{H}}_n$ be the set of triangle-free graphs of order n with six non-zero eigenvalues. In this paper, we find 19 graphs of ${\mathcal{H}}_n$, and we show that the other graphs of ${\mathcal{H}}_n$ can be constructed from these 19 graphs by adding some congruent vertices. Hence we completely characterize the triangle-free graphs with six non-zero eigenvalues.

Keywords:

• Triangle-free graph
• rank
• congruent vertex

2010 Mathematics Subject Classification:

• 05C50

Acknowledgements

This work is supported by the Doctoral Scientific Research Foundation of Xinjiang Normal University (No. XJNUBS2009 and No. XJNUBS2001), the Scientific Research Projects of Universities in Xinjiang Province (No. XJEDU2019Y030) and the NSFC (No. 11761071).

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

This work is supported by the Doctoral Scientific Research Foundation of Xinjiang Normal University (Grant Numbers XJNUBS2009 and XJNUBS2001), the Scientific Research Projects of Universities in Xinjiang Province (Grant Number XJEDU2019Y030) and the NSFC (Grant Number 11761071).