On graphs in which the Hoffman bound for cocliques equals the Cvetcovich bound
Let \(\Gamma\) be a strongly regular graph with parameters \((v,k,\lambda,\mu)\) and eigenvalues \(k,r\) and \(l\) (\(l<0\)) of multiplicities \(1,f\), and \(g\), respectively. It is known that for any coclique \(C\) in \(\Gamma\) the following inequalities hold: \(|C|\leq v(-l)/(k-l)\) (the Hoffman bound) and \(|C|\leq g= k(r+1)(k-r)/[(k+rl)(r-l)]\) (the Cvetković bound). Pseudogeometric graphs for which the bound are equal were studied by \textit{A. A. Makhnev} in [Usp. Mat. Nauk 54, No. 5, 25--76 (1999; Zbl 0974.51003)]. In this paper, general strongly regular graphs with the bound equality are studied. Several necessary conditions are derived and relations to special graphs are presented.
- Hoffman's coclique bound for normal regular digraphs, and nonsymmetric association schemes
- Bounds related to Coxeter spectral measures of graphs
- The clique and coclique numbers' bounds based on the H-eigenvalues of uniform hypergraphs
- scientific article; zbMATH DE number 1934396
- On hypohamiltonian and almost hypohamiltonian graphs
- On almost hypohamiltonian graphs
- Spectral bounds for the clique and independence numbers of graphs
- Application of hypergraph Hoffman's bound to intersecting families
- Erdős-Hajnal conjecture for graphs with bounded VC-dimension
This page was built for publication: On graphs in which the Hoffman bound for cocliques equals the Cvetcovich bound
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q656337)
