On spectral extrema of graphs with given order and dissociation number

摘要

Identifying the graph with maximum or minimum spectral radius among a given class of graphs is a central problem in extremal spectral graph theory, known as the Brualdi- Solheid problem. For a graph G = (V-G, E-G), a subset S subset of V-G is called a maximum dissociation set if the induced subgraph G[S] does not contain P-3 as its subgraph, and the subset has maximum cardinality. The dissociation number of G is the number of vertices in a maximum dissociation set of G. In this paper, we first characterize all the connected graphs (resp. bipartite graphs, trees) having maximum spectral radius among connected graphs (resp. bipartite graphs, trees) with given order and dissociation number. Secondly, we show that the connected n-vertex graph with dissociation number phi having minimum spectral radius is a tree, where phi >= [2/3n] . Finally, we determine the graphs having minimum spectral radius with fixed order n and dissociation number phi is an element of {2, [2n/3], n - 1, n - 2}.

关键词