Recognizing the Commuting Graph of a Finite Group

Authors Vikraman Arvind, Peter J. Cameron

Publication date 2 June 2022

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Arithmetic and combinatorial problems involving abstract finite groups (20D60)

Abstract: In this paper we study the realizability question for commuting graphs of finite groups: Given an undirected graph

X

is it the commuting graph of a group

G

? And if so, to determine such a group. We seek efficient algorithms for this problem. We make some general observations on this problem, and obtain a polynomial-time algorithm for the case of extraspecial groups.

This page was built for publication: Recognizing the Commuting Graph of a Finite Group

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