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

DOI10.1016/J.DISC.2021.112369MaRDI QIDQ2022157zbMATH OpenOpenAlexFDO

Authors Ratko Darda, Martin Milanič, M. 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)

Abstract: A graph is square-complementary (squco, for short) if its square and complement are isomorphic. We prove that there are no squco graphs with girth 6, that every bipartite graph is an induced subgraph of a squco bipartite graph, that the problem of recognizing squco graphs is graph isomorphism complete, and that no nontrivial squco graph is both bipartite and planar. These results resolve three of the open problems posed in Discrete Math. 327 (2014) 62-75.

Recommendations

• Graphs whose complement and square are isomorphic
• Complexity of finding graph roots with girth conditions
• scientific article; zbMATH DE number 6027233
• A good characterization of squares of strongly chordal split graphs
• A unified approach to recognize squares of split graphs

Cites work

• Characterisation of potentially bipartite self-complementary bipartitioned sequences
• Enumeration of bipartite self-complementary graphs
• Enumeration of bipartite self-complementary graphs
• Further results on graph equations for line graphs and n-th power graphs
• Graph Classes: A Survey
• Graph isomorphism completeness for chordal bipartite graphs and strongly chordal graphs
• Graph isomorphism in quasipolynomial time (extended abstract)
• Graph theory
• Graphs whose complement and square are isomorphic
• scientific article; zbMATH DE number 3654176 (Why is no real title available?)
• scientific article; zbMATH DE number 3756527 (Why is no real title available?)
• scientific article; zbMATH DE number 3807661 (Why is no real title available?)
• scientific article; zbMATH DE number 742770 (Why is no real title available?)
• scientific article; zbMATH DE number 840694 (Why is no real title available?)
• scientific article; zbMATH DE number 851097 (Why is no real title available?)
• scientific article; zbMATH DE number 861442 (Why is no real title available?)
• scientific article; zbMATH DE number 4187826 (Why is no real title available?)
• On self-antipodal graphs
• r-partite self-complementary graphs-diameters
• There are exactly seven graphs whose subdivision graphs are bipartite self-complementary

Cited in

(3)

• Graphs whose complement and square are isomorphic
• scientific article; zbMATH DE number 4063129 (Why is no real title available?)
• On 4-regular square-complementary graphs of large girth

Describes a project that uses

Uses Software

• plantri

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

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