English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Open

Presents the pdf analysis as premium feature

PDF Analysis

Insights

Presents the summarisation as premium feature

Summarisation

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Graphs with high symmetry or regularity are the main source forexperimentally hard instances of the notoriously difficult graph isomorphismproblem. In this paper, we study the computational complexity of isomorphismtesting for line graphs of $t$-$(v,k,\lambda)$ designs. For this class ofhighly regular graphs, we obtain a worst-case running time of $O(v^{\log v +O(1)})$ for bounded parameters $t,k,\lambda$. In a first step, our approachmakes use of the Babai--Luks algorithm to compute canonical forms of$t$-designs. In a second step, we show that $t$-designs can be reconstructedfrom their line graphs in polynomial-time. The first is algebraic in nature,the second purely combinatorial. For both, profound structural knowledge indesign theory is required. Our results extend earlier complexity results aboutisomorphism testing of graphs generated from Steiner triple systems and blockdesigns.

Computational complexity of reconstruction and isomorphism testing for designs and line graphs