On graphs in which the Hoffman bound for cocliques equals the Cvetcovich bound (Q656337)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On graphs in which the Hoffman bound for cocliques equals the Cvetcovich bound |
scientific article |
Statements
On graphs in which the Hoffman bound for cocliques equals the Cvetcovich bound (English)
0 references
17 January 2012
0 references
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.
0 references
Cvetkovic bound
0 references
Hoffman bound
0 references
Krein conditions
0 references
Strongly regular graphs
0 references