Minimum spectral radius of graphs of fixed order and dissociation number and its connection to Turán problems
Preprint
Abstract
Let $\mathcal{D}_{n,τ}$ be the set of all simple connected graphs of order $n$ and dissociation number $τ.$ In this paper, we study the minimum size and the minimum spectral radius of graphs in $\mathcal{D}_{n,τ}$ in connection with Turán-type problems for complete multipartite graphs. We characterize the Tur\' an graphs for several complete multipartite graphs where the size of one of the partite sets is much smaller than the size of the remaining partites. This extends a result of Erdős and Simonovits [16]. Additionally, we prove some stability results to get the structure of graphs without such a forbidden complete multipartite subgraph, and close to Turán number of edges. As an application, we show that a graph with the minimum spectral radius in $\mathcal{D}_{n,τ}$ must be a graph with the minimum size in $\mathcal{D}_{n, τ}$ when $n$ is sufficiently large and satisfies some parity conditions. We then describe a few structural properties of graphs with the minimum spectral radius in $\mathcal{D}_{n,τ}$. For even dissociation numbers and any order $n$, we compute the minimum size of a graph in $\mathcal{D}_{n,τ}$ and use it to characterize the graphs in $\mathcal{D}_{n, 4}$ that attain the minimum size and the minimum spectral radius. We also apply the stability results to upper bound the minimum number of edges and spectral radius for connected graphs with a given $d$-independence number when the order of the graph is sufficiently large. Finally, we derive two new bounds on the value of $τ(G)$ for a given graph $G$.
Keywords
All Related Versions
This publication has 20 references indexed in Scilit:
- Induced forests in some distance-regular graphsDiscrete Applied Mathematics, 2023
- On spectral extrema of graphs with given order and dissociation numberDiscrete Applied Mathematics, 2023
- On the spectral radius of bi-block graphs with given independence numberApplied Mathematics and Computation, 2021
- Norm-graphs and bipartite tur n numbersCombinatorica, 1996
- On the maximal index of connected graphsLinear Algebra and its Applications, 1991
- On the maximal index of graphs with a prescribed number of edgesLinear Algebra and its Applications, 1988
- On graphs with randomly deleted edgesActa Mathematica Hungarica, 1981
- On the eigenvalues of treesPeriodica Mathematica Hungarica, 1973
- An extremal graph problemActa Mathematica Hungarica, 1972
- On extremal problems of graphs and generalized graphsIsrael Journal of Mathematics, 1964