Thin Lehman matrices and their graphs (Q612952): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 08:52, 30 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Thin Lehman matrices and their graphs |
scientific article |
Statements
Thin Lehman matrices and their graphs (English)
0 references
16 December 2010
0 references
Summary: Two square \(0,1\)-matrices \(A\), \(B\) are a pair of Lehman matrices if \(AB^T= J+dI\), where \(J\) is the matrix of all 1s and \(d\) is a positive integer. It is known that there are infinitely many such matrices when \(d=1\), and these matrices are called thin Lehman matrices. An induced subgraph of the Johnson graph may be defined given any Lehman matrix, where the vertices of the graph correspond to rows of the matrix. These graphs are used to study thin Lehman matrices. We show that any connected component of such a graph determines the corresponding rows of the matrix up to permutations of the columns. We also provide a sharp bound on the maximum clique size of such graphs and give a complete classification of Lehman matrices whose graphs have at most two connected components. Some constraints on when a circulant matrix can be Lehman are also provided. Many general classes of thin Lehman matrices are constructed in the paper.
0 references
thin Lehmann matrix
0 references
Johnson graph
0 references