Interlacing eigenvalues and graphs

From MaRDI portal

Publication:1899437

Jump to:navigation, search

DOI10.1016/0024-3795(95)00199-2zbMath0831.05044OpenAlexW2060493211WikidataQ29041976 ScholiaQ29041976MaRDI QIDQ1899437

Willem H. Haemers

Publication date: 12 February 1996

Published in: Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL: https://pure.uvt.nl/ws/files/519743/675.pdf

zbMATH Keywords

bandwidth diameter adjacency matrix chromatic number regular graph Laplacian matrix clique block designs coclique eigenvalue interlacing

Mathematics Subject Classification ID

Combinatorial aspects of block designs (05B05) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Related Items

Eigenvalues and degree deviation in graphs, A spectral characterization of the \(s\)-clique extension of the square grid graphs, New lower bounds for the Randić spread, Fractional spanning tree packing, forest covering and eigenvalues, On \(\lambda\)-harmonic graphs, A sharp lower bound on the signless Laplacian index of graphs with \((\kappa,\tau)\)-regular sets, Triangle-free induced subgraphs of the unitary polarity graph, Uniqueness of strongly regular graphs having minimal \(p\)-rank, Generalized quadrangles with a regular point and association schemes, Toughness and spectrum of a graph, 5-chromatic strongly regular graphs, A characterization of distance-regular graphs with diameter three, A lower bound for the energy of symmetric matrices and graphs, Large matchings from eigenvalues, The spectra of some families of digraphs, Graphs with constant \(\mu\) and \(\overline{\mu}\), Intriguing sets of vertices of regular graphs, Bounds on special subsets in graphs, eigenvalues and association schemes, Theorems on partitioned matrices revisited and their applications to graph spectra, A recursive construction of the regular exceptional graphs with least eigenvalue \(-2\), Enumeration of Seidel matrices, A note on eigenvalue bounds for independence numbers of non-regular graphs, Spectral classes of regular, random, and empirical graphs, Upper bounds on the (signless) Laplacian eigenvalues of graphs, The spectrum and toughness of regular graphs, Nodal decompositions of graphs, Maximizing the spectral radius of graphs with fixed minimum degree and edge connectivity, Interlacing inequalities for eigenvalues of discrete Laplace operators, Edge-disjoint spanning trees and eigenvalues of regular graphs, Extremal graphs with bounded vertex bipartiteness number, Spectral conditions for edge connectivity and packing spanning trees in multigraphs, Minimum vertex covers and the spectrum of the normalized Laplacian on trees, A relationship between the diameter and the intersection number \(c _{2}\) for a distance-regular graph, The graph with spectrum \(14^{1} 2^{40}( - 4)^{10}( - 6)^{9}\), Spectral radius and Hamiltonian graphs, On the Laplacian spectral ratio of connected graphs, An interlacing technique for spectra of random walks and its application to finite percolation clusters, Distance-regular graphs with or at least half the valency, Graphs with least eigenvalue \(-2\): ten years on, Minimal multiple blocking sets, Graphs and Hermitian matrices: Exact interlacing, On the spectra of simplicial rook graphs, Laplacian spread of graphs: lower bounds and relations with invariant parameters, On the change of distance energy of complete bipartite graph due to edge deletion, Spectral bounds for the \(k\)-independence number of a graph, A lower bound for the Laplacian eigenvalues of a graph-proof of a conjecture by Guo, Spreads in strongly regular graphs, On the spectrum of a random walk on the discrete Heisenberg group and the norm of Harper's operator, An application of Hoffman graphs for spectral characterizations of graphs, Combinatorial and spectral properties of König-Egerváry graphs, Star complements in regular graphs: old and new results, The cyclic edge-connectivity of strongly regular graphs, Graphs and Hermitian matrices: eigenvalue interlacing, On the eigenvalues of distance powers of circuits, Vertex-connectivity and eigenvalues of graphs with fixed girth, Eigenvalues and perfect matchings, Some interlacing results for the eigenvalues of distance-regular graphs, Eigenvalues and diameter, Improving an upper bound on the stability number of a graph, Bounds of Laplacian spectrum of graphs based on the domination number, Eigenvalues and \([1,n\)-odd factors], The vertex (edge) independence number, vertex (edge) cover number and the least eigenvalue of a graph, Shilla distance-regular graphs, On the inverse of the adjacency matrix of a graph, Some results on the bounds of signless Laplacian eigenvalues, Spectral bounds and distance-regularity, Maximum spectral radius of graphs with given connectivity, minimum degree and independence number, Distance spectral spread of a graph, Spectra of large random trees, Which cospectral graphs have same degree sequences, On regular induced subgraphs of generalized polygons, Distance and distance signless Laplacian spread of connected graphs, The largest normalized Laplacian spectral radius of non-bipartite graphs, There is no (75,32,10,16) strongly regular graph, On the spectral gap and the automorphism group of distance-regular graphs, A characterization of weight-regular partitions of graphs, The toughness of Kneser graphs, Matchings in regular graphs from eigenvalues, Sharp bounds on the eigenvalues of trees, The vertex-connectivity of a distance-regular graph, Augmenting the Delsarte bound: a forbidden interval for the order of maximal cliques in strongly regular graphs, Optimization of eigenvalue bounds for the independence and chromatic number of graph powers, A tight lower bound on the matching number of graphs via Laplacian eigenvalues, Graphs in which neighborhoods of vertices are isomorphic to the Hoffman-Singleton graph, Spectral fundamentals and characterizations of signed directed graphs, On a conjecture of Brouwer involving the connectivity of strongly regular graphs, Perron values and classes of trees, Hamiltonian \(s\)-properties and eigenvalues of \(k\)-connected graphs, Spectral characterization of the complete graph removing a path, Graphs \(G\) with nullity \(2c(G) + p(G) - 1\), On the spread of the spectrum of a graph, The signless Laplacian spread, Eigenvalues and edge-connectivity of regular graphs, Signless Laplacian spectral radius and fractional matchings in graphs, Three-class association schemes, Eigenvalue interlacing and weight parameters of graphs, Nonexistence of some antipodal distance-regular graphs of diameter four, Bicliques and eigenvalues, The Hermitian two-graph and its code, A new family of tight sets in \(\mathcal Q^+(5,q)\), Distance mean-regular graphs, Improved sufficient conditions for \(k\)-leaf-connected graphs, Regular Graphs, Eigenvalues and Regular Factors, Multi-attribute community detection in international trade network, Colouring the normalized Laplacian, Characterizing and computing weight-equitable partitions of graphs, Unnamed Item, A clique-free pseudorandom subgraph of the pseudo polarity graph, On the Laplacian Eigenvalues and Metric Parameters of Hypergraphs, Pseudo-Strong Regularity Around a Set, Regular graphs with girth at least 5 and small second largest eigenvalue, Unnamed Item, Laplacian spectral bounds for clique and independence numbers of graphs, Spectral Bounds for the k-Regular Induced Subgraph Problem, Edge-Disjoint Spanning Trees, Edge Connectivity, and Eigenvalues in Graphs, Spectral Radius of Graphs, Handling Biological Complexity Using Kron Reduction, A spectral condition for the existence of the square of a path, Finite Field Kakeya and Nikodym Sets in Three Dimensions, Hoffman's ratio bound, New values for the bipartite Ramsey number of the four-cycle versus stars, Some graphs determined by their (signless) Laplacian spectra, On sensitivity in bipartite Cayley graphs, Lower bounds for the bandwidth problem, Nordhaus-Gaddum type inequalities of the second \(A_\alpha\)-eigenvalue of a graph, A survey on the missing Moore graph, A characterization and an application of weight-regular partitions of graphs, Wiener-type invariants and \(k\)-leaf-connected graphs, A new class of polynomials from the spectrum of a graph, and its application to bound the \(k\)-independence number, Spectral conditions for edge connectivity and spanning tree packing number in (multi-)graphs, An inequality involving the second largest and smallest eigenvalue of a distance-regular graph, An improvement of sufficient condition for \(k\)-leaf-connected graphs, Edge-connectivity and (signless) Laplacian eigenvalue of graphs, Local spectral expansion approach to high dimensional expanders. II: Mixing and geometrical overlapping, Reflexive bipartite regular graphs, On the spectrum of the normalized Laplacian for signed graphs: interlacing, contraction, and replication, Graph toughness from Laplacian eigenvalues, On inertia and ratio type bounds for the \(k\)-independence number of a graph and their relationship, Some interlacing results on weighted adjacency matrices of graphs with degree-based edge-weights, Bounds of signless Laplacian spectrum of graphs based on the \(k\)-domination number, Edge-disjoint spanning trees and eigenvalues, An interlacing approach for bounding the sum of Laplacian eigenvalues of graphs, Spectral lower bounds for the quantum chromatic number of a graph. II, A construction for clique-free pseudorandom graphs, An inequality using perfect matchings and Laplacian spread of a graph, Spectral bisection of graphs and connectedness, Large regular bipartite graphs with median eigenvalue 1, Some graphs determined by their (signless) Laplacian spectra, Unnamed Item, On the sizes of expander graphs and minimum distances of graph codes, Unnamed Item, Penalized likelihood and multiple testing, The extremal spectral radii of the arithmetical structures on paths, The Endogenous Analysis of Flows, with Applications to Migrations, Social Mobility and Opinion Shifts, Connectivity and eigenvalues of graphs with given girth or clique number, On the spectral structure of Jordan-Kronecker products of symmetric and skew-symmetric matrices, The fan graph is determined by its signless Laplacian spectrum, Fractional arboricity, strength and eigenvalues of graphs with fixed girth or clique number, Edge-matching graph contractions and their interlacing properties, The \(A_\alpha\)-spectral radius and perfect matchings of graphs, The Moore-Penrose inverse of symmetric matrices with nontrivial equitable partitions, Note on edge-disjoint spanning trees and eigenvalues, Vertex-connectivity and eigenvalues of graphs, Bounds for different spreads of line and total graphs, Signless Laplacian eigenvalue problems of Nordhaus-Gaddum type, Stability of conjugated carbon nanocones, On the spectrum of an extremal graph with four eigenvalues, Algebraic characterizations of regularity properties in bipartite graphs, On the integrability of strongly regular graphs, SDP Relaxations for Some Combinatorial Optimization Problems, Graph homomorphisms through random walks, The Laplacian spectral radius of graphs, Algebraic conditions for t-tough graphs, On the displacement of eigenvalues when removing a twin vertex, A spectral characterization of the \(s\)-clique extension of the triangular graphs, On graphs with the largest Laplacian index, The maximum clique and the signless Laplacian eigenvalues, Matching extendability and connectivity of regular graphs from eigenvalues, The edge-connectivity of strongly 3-walk-regular graphs, Signed (total) domination numbers and Laplacian spectrum of graphs, On the Cheeger constant for distance-regular graphs, The negative tetrahedron and the first infinite family of connected digraphs that are strongly determined by the Hermitian spectrum, Cut ratios and Laplacian eigenvalues, On the hierarchical product of graphs and the generalized binomial tree, On the fragmentation of a torus by random walk, On the \(k\)-independence number of graphs, Spanning tree packing number and eigenvalues of graphs with given girth, Sharp bounds on the signless Laplacian spread of graphs, Unnamed Item, Fastest mixing reversible Markov chain on friendship graph: trade-off between transition probabilities among friends and convergence rate, A relative bound for independence, Acyclic subgraphs of tournaments with high chromatic number, The least eigenvalue of graphs whose complements have only two pendent vertices, Distance signless Laplacian eigenvalues of graphs, Critical window for the vacant set left by random walk on random regular graphs, Non-bipartite graphs of fixed order and size that minimize the least eigenvalue, Eigenvalue conditions for induced subgraphs, A new eigenvalue bound for independent sets, Approximately strongly regular graphs, On monoid graphs, Fractional matching number and spectral radius of nonnegative matrices of graphs, On outindependent subgraphs of strongly regular graphs, On the Aα-spectral radius of connected graphs, On the spectral radius, energy and Estrada index of the arithmetic–geometric matrix of a graph, On graphs with three distinct signless Laplacian eigenvalues, On the spectral radius, energy and Estrada index of the Sombor matrix of graphs, Symmetric matrices, signed graphs, and nodal domain theorems, The optimal bound on the 3-independence number obtainable from a polynomial-type method, Bounding the sum of the largest signless Laplacian eigenvalues of a graph, The proportion of non-degenerate complementary subspaces in classical spaces, Fractional matching, factors and spectral radius in graphs involving minimum degree, Worst-Case Examples for Lasserre’s Measure–Based Hierarchy for Polynomial Optimization on the Hypercube, Positive and negative square energies of graphs, Nullities of cycle-spliced bipartite graphs, Spectral properties of token graphs, Incidence‐free sets and edge domination in incidence graphs, Spectral bounds for the vulnerability parameters of graphs, Spectral characterization of the complete graph removing a cycle, On the spectra and spectral radii of token graphs, Induced forests in some distance-regular graphs, On the multiplicities of digraph eigenvalues, Explicit non-malleable codes from bipartite graphs, Community detection in attributed networks for global transfer market, DISTRIBUTION OF ACCUMULATION POINTS OF ROOTS FOR TYPE (n - 1, 1) COXETER GROUPS, On finite generalized quadrangles of even order, On spectral invariants of the \(\alpha\)-mixed adjacency matrix, The asymptotics of \(r(4,t)\), Improved incidence bounds over arbitrary finite fields via the VC-dimension theory, The \(A_\alpha\)-spectral radius for path-factors in graphs, Unnamed Item, Unnamed Item, Unnamed Item, Edge connectivity, packing spanning trees, and eigenvalues of graphs, Distance Laplacian eigenvalues and chromatic number in graphs, Deterministic Tensor Completion with Hypergraph Expanders, Spectral upper bound on the quantum k-independence number of a graph, Further results on monotonic graph invariants and bipartiteness number, The pseudo-geometric graphs for generalized quadrangles of order \((3,t)\), Unnamed Item, On the distance and distance Laplacian eigenvalues of graphs, Unnamed Item, Fractional matching number and eigenvalues of a graph, Trace of Products in Finite Fields from a Combinatorial Point of View

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:1899437&oldid=14311430"