Spectral radius and clique partitions of graphs

DOI10.1016/J.LAA.2021.07.025zbMATH Open1473.05195arXiv2111.02734OpenAlexW3191908787MaRDI QIDQ820994FDOQ820994

Authors: N. E. Zubov 

Publication date: 29 September 2021

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

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.

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

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

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)

Cites Work

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

Cited In (9)

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

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)