Maximum spectral radius of graphs with given connectivity, minimum degree and independence number

DOI10.1016/J.JDA.2014.08.006zbMATH Open1325.05107arXiv1107.5359OpenAlexW2043005319MaRDI QIDQ2018544FDOQ2018544

Hongliang Lu, Yuqing Lin

Publication date: 24 March 2015

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Abstract: Shiu, Chan and Chang [On the spectral radius of graphs with connectivity at most $k$, J. Math. Chem., 46 (2009), 340-346] studied the spectral radius of graphs of order $n$ with $kappa(G)leqk$ and showed that among those graphs, the maximum spectral radius is obtained uniquely at $K_k^n$, which is the graph obtained by joining $k$ edges from $k$ vertices of $K_{n-1}$ to an isolated vertex. In this paper, we study the spectral radius of graphs of order $n$ with $kappa(G)leqk$ and minimum degree $delta(G)geqk$. We show that among those graphs, the maximum spectral radius is obtained uniquely at $K_k+(K_{delta-k+1}cup{K}_{n-delta-1})$.

Full work available at URL: https://arxiv.org/abs/1107.5359

zbMATH Keywords

connectivityindependence numbermaximum spectral radius

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Connectivity (05C40)

Cites Work

• Some Inequalities for the Largest Eigenvalue of a Graph
• On the Spectral Radius of Complementary Acyclic Matrices of Zeros and Ones
• Interlacing eigenvalues and graphs
• The spectral radius of trees on \(k\) pendant vertices
• On the spectral radius of graphs with cut vertices
• More on Graph Perturbations
• On the first eigenvalue of bipartite graphs
• On the spectral radius of graphs with connectivity at most \(k\)
• Spectral bounds for the clique and independence numbers of graphs
• Extreme eigenvalues of nonregular graphs
• On the spectral radius of graphs with cut edges
• The spectral radius and the maximum degree of irregular graphs
• On the largest eigenvalue of non-regular graphs
• Spectral radius of graphs with given matching number

Cited In (12)

• On the spectral radius of block graphs with prescribed independence number \(\alpha\)
• Graphs with given degree sequence and maximal spectral radius
• Title not available (Why is that?)
• Maximizing the spectral radius of \(k\)-connected graphs with given diameter
• On the spectral radius of trees with given independence number
• On the (signless Laplacian) spectral radius of minimally \(k\)-(edge)-connected graphs for small \(k\)
• On the spectral radius of block graphs having all their blocks of the same size
• \(l\)-connectivity, \(l\)-edge-connectivity and spectral radius of graphs
• Independence number and spectral radius of cactus graphs
• Connectivity, diameter, independence number and the distance spectral radius of graphs
• On the spectral radius of bi-block graphs with given independence number \(\alpha\)
• The maximum radius of graphs with given order and minimum degree

Recommendations

• Maximal graphs and graphs with maximal spectral radius 👍 👎
• On the spectral radius of graphs with connectivity at most \(k\) 👍 👎
• Graphs with small independence number minimizing the spectral radius 👍 👎
• The minimum spectral radius of graphs with a given independence number 👍 👎
• Maximizing the spectral radius of graphs with fixed minimum degree and edge connectivity 👍 👎
• Maximum Spectral Radius of Graphs with Connectivity at Most k and Minimum Degree at Least δ 👍 👎
• Maximizing the spectral radius of \(k\)-connected graphs with given diameter 👍 👎
• Maximum degree and minimum degree spectral radii of some graph operations 👍 👎
• Connectivity, diameter, independence number and the distance spectral radius of graphs 👍 👎
• The spectral radius of graphs with given independence number 👍 👎

This page was built for publication: Maximum spectral radius of graphs with given connectivity, minimum degree and independence number

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2018544)