Aspects of the commuting graph

V. Arvind; Peter J. Cameron; Xuanlong Ma; Natalia Maslova

doi:10.1016/j.jalgebra.2025.07.020

Aspects of the commuting graph

V. Arvind, Peter J. Cameron, Xuanlong Ma, Natalia Maslova

Research output: Contribution to journal › Article › peer-review

Abstract

We discuss the computational problem of deciding whether a given graph
is the commuting graph of a finite group; we give a quasipolynomial algorithm,
and a polynomial algorithm for the case when the group is an extraspecial
p-group for p< an odd prime.

We give new results on the question of whether the commuting graph of
a given group is a cograph or a chordal graph, two classes of graphs defined
by forbidden subgraphs.

The problems are not unrelated, since there are a number of cases where hard
computational problems on graphs are easier when restricted to special
classes of graphs; we conjecture that the recognition problem is polynomial
for cographs and chordal graphs.

Original language	English
Journal	Journal of Algebra
Early online date	5 Aug 2025
DOIs	https://doi.org/10.1016/j.jalgebra.2025.07.020
Publication status	E-pub ahead of print - 5 Aug 2025

Keywords

Commuting graph
Finite group
Quasi-polynomial algorithm

Access to Document

10.1016/j.jalgebra.2025.07.020Licence: CC BY

https://arxiv.org/abs/2305.07301Licence: CC BY

Cite this

@article{601434b930eb4211a7276ac7c40e0465,

title = "Aspects of the commuting graph",

abstract = "We discuss the computational problem of deciding whether a given graph is the commuting graph of a finite group; we give a quasipolynomial algorithm, and a polynomial algorithm for the case when the group is an extraspecial p-group for p< an odd prime. We give new results on the question of whether the commuting graph of a given group is a cograph or a chordal graph, two classes of graphs defined by forbidden subgraphs. The problems are not unrelated, since there are a number of cases where hard computational problems on graphs are easier when restricted to special classes of graphs; we conjecture that the recognition problem is polynomial for cographs and chordal graphs.",

keywords = "Commuting graph, Finite group, Quasi-polynomial algorithm",

author = "V. Arvind and Cameron, \{Peter J.\} and Xuanlong Ma and Natalia Maslova",

note = "Funding: Engineering and Physical Sciences Research Council EP/R014604/1.",

year = "2025",

month = aug,

day = "5",

doi = "10.1016/j.jalgebra.2025.07.020",

language = "English",

journal = "Journal of Algebra",

issn = "0021-8693",

publisher = "Academic Press/Elsevier ",

}

TY - JOUR

T1 - Aspects of the commuting graph

AU - Arvind, V.

AU - Cameron, Peter J.

AU - Ma, Xuanlong

AU - Maslova, Natalia

N1 - Funding: Engineering and Physical Sciences Research Council EP/R014604/1.

PY - 2025/8/5

Y1 - 2025/8/5

N2 - We discuss the computational problem of deciding whether a given graph is the commuting graph of a finite group; we give a quasipolynomial algorithm, and a polynomial algorithm for the case when the group is an extraspecial p-group for p< an odd prime. We give new results on the question of whether the commuting graph of a given group is a cograph or a chordal graph, two classes of graphs defined by forbidden subgraphs. The problems are not unrelated, since there are a number of cases where hard computational problems on graphs are easier when restricted to special classes of graphs; we conjecture that the recognition problem is polynomial for cographs and chordal graphs.

AB - We discuss the computational problem of deciding whether a given graph is the commuting graph of a finite group; we give a quasipolynomial algorithm, and a polynomial algorithm for the case when the group is an extraspecial p-group for p< an odd prime. We give new results on the question of whether the commuting graph of a given group is a cograph or a chordal graph, two classes of graphs defined by forbidden subgraphs. The problems are not unrelated, since there are a number of cases where hard computational problems on graphs are easier when restricted to special classes of graphs; we conjecture that the recognition problem is polynomial for cographs and chordal graphs.

KW - Commuting graph

KW - Finite group

KW - Quasi-polynomial algorithm

UR - https://www.scopus.com/pages/publications/105012740482

U2 - 10.1016/j.jalgebra.2025.07.020

DO - 10.1016/j.jalgebra.2025.07.020

M3 - Article

SN - 0021-8693

JO - Journal of Algebra

JF - Journal of Algebra

ER -

Aspects of the commuting graph

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this