1. Spectral radius and clique partitions of graphs
- Author
-
Edwin van Dam, Jiang Zhou, Econometrics and Operations Research, and Research Group: Operations Research
- Subjects
Numerical Analysis ,Algebra and Number Theory ,Degree (graph theory) ,Spectral radius ,Block (permutation group theory) ,Clique partition ,Clique (graph theory) ,Upper and lower bounds ,Graph ,Combinatorics ,TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY ,Steiner 2-design ,FOS: Mathematics ,Clique partition number ,Discrete Mathematics and Combinatorics ,Mathematics - Combinatorics ,Combinatorics (math.CO) ,Geometry and Topology ,05C50, 05C70, 05B20 ,Mathematics ,MathematicsofComputing_DISCRETEMATHEMATICS - 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.
- Published
- 2021