Classification of divisible design graphs with at most 39 vertices

DOI10.1002/JCD.21818MaRDI QIDQ6378651zbMATH OpenOpenAlexFDO

Authors Dmitry Panasenko, Leonid Viktorovich Shalaginov

Publication date 27 September 2021

Full work available at URL https://doi.org/10.1002/jcd.21818

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph designs and isomorphic decomposition (05C51) Combinatorial aspects of representation theory (05E10) Eigenvalues, singular values, and eigenvectors (15A18)

Abstract: A $k$-regular graph is called a divisible design graph (DDG for short) if its vertex set can be partitioned into $m$ classes of size $n$, such that two distinct vertices from the same class have exactly $lambd{a}_1$ common neighbors, and two vertices from different classes have exactly $lambd{a}_2$ common neighbors. A DDG with $m=1$, $n=1$, or $lambd{a}_1=lambd{a}_2$ is called improper, otherwise it is called proper. We present new constructions of DDGs and, using a computer enumeration algorithm, we find all proper connected DDGs with at most 39 vertices, except for three tuples of parameters: $(32,15,6,7,4,8)$, $(32,17,8,9,4,8)$, $(36,24,15,16,4,9)$.

Recommendations

• Walk-regular divisible design graphs
• Divisible design graphs with parameters (4n,n+2,n-2,2,4,n) and (4n,3n-2,3n-6,2n-2,4,n)
• The vertex connectivity of some classes of divisible design graphs
• Divisible design digraphs
• Divisible design graphs

Cited in

(8)

• The vertex connectivity of some classes of divisible design graphs
• Divisible design graphs from symplectic graphs over rings with a unique non-trivial ideal
• Construction of divisible design graphs using affine designs
• Strongly regular graphs decomposable into a divisible design graph and a Delsarte clique
• On a family of divisible design digraphs
• Divisible design graphs from the symplectic graph
• Divisible design graphs obtained by plugging a difference set into a construction for antipodal distance-regular graphs of diameter 3
• Non-commutative association schemes having divisible design graphs as relations from pseudo-cyclic association schemes

This page was built for publication: Classification of divisible design graphs with at most 39 vertices

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