On the $A_{\alpha }$-index of graphs with given order and dissociation number

Abstract

Given a graph $G,$ a subset of vertices is called a maximum dissociation set of $G$ if it induces a subgraph with vertex degree at most 1, and the subset has maximum cardinality. The cardinality of a maximum dissociation set is called the dissociation number of $G$. The adjacency matrix and the degree diagonal matrix of $G$ are denoted by $A(G)$ and $D(G),$ respectively. In 2017, Nikiforov proposed the $A_{\alpha }$-matrix: $A_{\alpha }(G)=\alpha D(G)+(1-\alpha )A(G),$ where $\alpha \in [0,1].$ The largest eigenvalue of this novel matrix is called the $A_{\alpha }$-index of $G.$ In this paper, we firstly determine the connected graph (resp. bipartite graph, tree) having the largest $A_{\alpha }$-index over all connected graphs (resp. bipartite graphs, trees) with fixed order and dissociation number. Secondly, we describe the structure of all the $n$-vertex graphs having the minimum $A_{\alpha }$-index with dissociation number $\tau$, where $\tau ⩾\lceil \frac{2}{3}n\rceil .$ Finally, we identify all the connected $n$-vertex graphs with dissociation number $\tau \in \{2,\lceil \frac{2}{3}n\rceil ,n-1,n-2\}$ having the minimum $A_{\alpha }$-index.

16 pages; 6 figures