Spectral radius and clique partitions of graphs

DOI10.1016/J.LAA.2021.07.025MaRDI QIDQ820994zbMATH OpenOpenAlexFDO

Authors N. E. Zubov

Publication date 29 September 2021

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

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

zbMATH Keywords

spectral radiusclique partitionSteiner 2-designclique partition number

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: We give lower bounds on the size and total size of clique partitions of a graph in terms of its spectral radius and minimum degree, and derive a spectral upper bound for the maximum number of edge-disjoint $t$-cliques. The extremal graphs attaining the bounds are exactly the block graphs of Steiner $2$-designs and the regular graphs with $K_t$-decompositions, respectively.

Recommendations

• Cleavages of graphs: the spectral radius
• Clique number and distance spectral radii of graphs.
• On the spectral radius of bipartite graphs
• On the spectral radius of bipartite graphs
• Spectral radius of bipartite graphs
• On the maximum spectral radius of multipartite graphs
• On the spectral radius of graphs
• Cliques and the spectral radius
• Eigenvalues and clique partitions of graphs
• Bounds on the spectral radius of general hypergraphs in terms of clique number

Cites work

• scientific article; zbMATH DE number 3582190 (Why is no real title available?)
• scientific article; zbMATH DE number 790476 (Why is no real title available?)
• An introduction to the theory of graph spectra
• Asymptotic values of clique partition numbers
• Clique partitions and clique coverings
• Decomposing graphs into edges and triangles
• Eigenvalue inequalities and equalities
• Eigenvalues and clique partitions of graphs
• Eigenvalues and partitionings of the edges of a graph
• Extremal clique coverings of complementary graphs
• On NP-hard graph properties characterized by the spectrum
• On a problem of G. O. H. Katona and T. Tarján
• On the Decomposition of Graphs
• Proof of a conjecture of Katona and Tarjan
• Short proofs of some extremal results
• Some observations on the smallest adjacency eigenvalue of a graph
• Spectra of graphs
• The Representation of a Graph by Set Intersections
• The enumeration of spanning tree of weighted graphs
• The graphs with all but two eigenvalues equal to \(\pm 1\)

Cited in

(9)

• Cliques and the spectral radius
• The number of maximal cliques and spectral radius of graphs with certain forbidden subgraphs
• Spectral extrema of graphs with bounded clique number and matching number
• Spectral extremal graphs for disjoint cliques
• scientific article; zbMATH DE number 5280010 (Why is no real title available?)
• Eigenvalues and clique partitions of graphs
• Network partition via a bound of the spectral radius
• Sharp bounds on the least eigenvalue of a graph determined from edge clique partitions
• A theory of spectral partitions of metric graphs

This page was built for publication: Spectral radius and clique partitions of graphs

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