Co-cliques and star complements in extremal strongly regular graphs

DOI10.1016/J.LAA.2006.04.002MaRDI QIDQ864564zbMATH OpenOpenAlexFDO

Authors P. Rowlinson

Publication date 12 February 2007

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

Full work available at URL https://doi.org/10.1016/j.laa.2006.04.002

zbMATH Keywords

eigenvalueindependence number

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Structural characterization of families of graphs (05C75) Association schemes, strongly regular graphs (05E30)

Review text

The author characterizes the Schläfli graph and the McLaughlin graph as the only extremal strongly regular graphs in which an eigenvalue of largest multiplicity is positive and a corresponding star complement has the form \(K_{1,2} \cup (t-s-1)K_1\) \((2\leq s\leq t-1)\). As a corollary, it is shown that the independence number of an extremal strongly regular graph in which an eigenvalue \(\mu\) of largest multiplicity is positive, is at most \(4\mu^2 + 4\mu - 2\), with equality if and only if the graph is a pentagon, the Schläfli graph, or the McLaughlin graph.

Recommendations

• On joins of a clique and a co-clique as star complements in regular graphs
• Regular star complements in strongly regular graphs
• On graphs whose star sets are (co-)cliques
• Star complementary strongly regular decompositions of strongly regular graphs
• Star complements in regular graphs: old and new results
• An extension of the star complement technique for regular graphs
• Star complements and maximal exceptional graphs
• scientific article; zbMATH DE number 2057962
• scientific article; zbMATH DE number 2115945
• Extremal clique coverings of complementary graphs

Cites work

• Eigenspaces of graphs
• scientific article; zbMATH DE number 3670480 (Why is no real title available?)
• scientific article; zbMATH DE number 50655 (Why is no real title available?)
• scientific article; zbMATH DE number 540115 (Why is no real title available?)
• scientific article; zbMATH DE number 2117218 (Why is no real title available?)
• scientific article; zbMATH DE number 3326519 (Why is no real title available?)
• On rank 3 permutation groups
• ON THE MULTIPLICITIES OF GRAPH EIGENVALUES
• Star complements and switching in graphs
• Strongly regular graphs having strongly regular subconstituents

Cited in

(13)

• A spectral proof of the uniqueness of a strongly regular graph with parameters (81,20,1,6)
• There does not exist a strongly regular graph with parameters \((1911, 270, 105, 27)\)
• On the displacement of eigenvalues when removing a twin vertex
• Eigenvalue multiplicity in regular graphs
• On independent star sets in finite graphs
• Relations between ( , )-regular sets and star complements.
• An example of using star complements in classifying strongly regular graphs
• Graphs with least eigenvalue -2: ten years on
• On edge star sets in trees
• On the multiplicities of digraph eigenvalues
• Pseudogeometric graph for \(pG_{4} (8, 175)\)
• Star complements and exceptional graphs
• Star complements in regular graphs: old and new results

This page was built for publication: Co-cliques and star complements in extremal strongly regular graphs

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