Searching for square-complementary graphs: complexity of recognition and further nonexistence results

DOI10.1016/j.disc.2021.112369zbMath1462.05257arXiv1808.01313OpenAlexW3138598984MaRDI QIDQ2022157

Martin Milanič, Ratko Darda, Miguel A. Pizaña

Publication date: 28 April 2021

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1808.01313

zbMATH Keywords

complementgraph equationssquco graphs

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Uses Software

• plantri

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• r-partite self-complementary graphs-diameters
• Further results on graph equations for line graphs and \(n\)-th power graphs
• Characterisation of potentially bipartite self-complementary bipartitioned sequences
• Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs
• Graphs whose complement and square are isomorphic
• There are exactly seven graphs whose subdivision graphs are bipartite self-complementary
• Graph Classes: A Survey
• Graph isomorphism in quasipolynomial time [extended abstract]
• Enumeration of bipartite self-complementary graphs
• Enumeration of bipartite self-complementary graphs
• On self-antipodal graphs

This page was built for publication: Searching for square-complementary graphs: complexity of recognition and further nonexistence results