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

DOI10.1016/J.JDA.2014.08.006MaRDI QIDQ2018544zbMATH OpenOpenAlexFDO

Authors Hongliang Lu, Yuqing Lin

Publication date 24 March 2015

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

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)

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})$.

Recommendations

• The minimum spectral radius of graphs with a given independence number
• Maximum spectral radius of graphs with connectivity at most \(k\) and minimum degree at least \(\delta\)
• Maximizing the spectral radius of graphs with fixed minimum degree and edge connectivity
• The spectral radius of graphs with given independence number
• Maximizing the spectral radius of k-connected graphs with given diameter
• Graphs with small independence number minimizing the spectral radius
• On the spectral radius of graphs with connectivity at most \(k\)
• Maximal graphs and graphs with maximal spectral radius
• Maximum degree and minimum degree spectral radii of some graph operations
• Connectivity, diameter, independence number and the distance spectral radius of graphs

Cites work

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

Cited in

(18)

• Graphs with small independence number minimizing the spectral radius
• On the spectral radius of bi-block graphs with given independence number \(\alpha\)
• Independence number and spectral radius of cactus graphs
• The spectral radius of graphs with given independence number
• On the spectral radius of block graphs having all their blocks of the same size
• On the spectral radius of graphs with connectivity at most \(k\)
• Maximum spectral radius of graphs with connectivity at most \(k\) and minimum degree at least \(\delta\)
• Maximizing the spectral radius of graphs with fixed minimum degree and edge connectivity
• On the spectral radius of block graphs with prescribed independence number \(\alpha\)
• Connectivity, diameter, independence number and the distance spectral radius of graphs
• Maximizing the spectral radius of \(k\)-connected graphs with given diameter
• On the spectral radius of trees with given independence number
• The maximum radius of graphs with given order and minimum degree
• Graphs with given degree sequence and maximal spectral radius
• \(l\)-connectivity, \(l\)-edge-connectivity and spectral radius of graphs
• The sharp lower bound for the spectral radius of connected graphs with the independence number
• On the (signless Laplacian) spectral radius of minimally \(k\)-(edge)-connected graphs for small \(k\)
• scientific article; zbMATH DE number 6870678 (Why is no real title available?)

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)