Spectral extremal graphs for the bowtie

Abstract

Let F k be the (friendship) graph obtained from k triangles by sharing a common vertex. The F k -free graphs of order n which attain the maximal spectral radius was firstly characterized by Cioabă, Feng, Tait and Zhang [Electron. J. Combin. 27 (4) (2020)], and later uniquely determined by Zhai, Liu and Xue [Electron. J. Combin. 29 (3) (2022)] under the condition that n is sufficiently large. In this paper, we get rid of the condition on n being sufficiently large if k = 2 . The graph F 2 is also known as the bowtie. We show that the unique n -vertex F 2 -free spectral extremal graph is the balanced complete bipartite graph adding an edge in the vertex part with smaller size if n ≥ 7 , and the condition n ≥ 7 is tight. Our result is a spectral generalization of a theorem of Erdős, Füredi, Gould and Gunderson [J. Combin. Theory Ser. B 64 (1995)], which states that ex ( n , F 2 ) = ⌊ n 2 / 4 ⌋ + 1 . Moreover, we study the spectral extremal problem for F k -free graphs with given number of edges. In particular, we show that the unique m -edge F 2 -free spectral extremal graph is the join of K 2 with an independent set of m − 1 2 vertices if m ≥ 8 , and the condition m ≥ 8 is tight.

Topics & Concepts