Aspects of the commuting graph
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916865206386688 |
|---|---|
| author | Arvind, V. Ma, Xuanlong Cameron, Peter J. Maslova, Natalia V. |
| author_facet | Arvind, V. Ma, Xuanlong Cameron, Peter J. Maslova, Natalia V. |
| contents | The commuting graph of a group $G$ is the graph whose vertices are the elements of $G$, two distinct vertices joined if they commute.
Our purpose in this paper is twofold: 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 extra\-special 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2305_07301 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Aspects of the commuting graph Arvind, V. Ma, Xuanlong Cameron, Peter J. Maslova, Natalia V. Group Theory Combinatorics 05C25, 05C85, 20D60 The commuting graph of a group $G$ is the graph whose vertices are the elements of $G$, two distinct vertices joined if they commute. Our purpose in this paper is twofold: 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 extra\-special 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. |
| title | Aspects of the commuting graph |
| topic | Group Theory Combinatorics 05C25, 05C85, 20D60 |
| url | https://arxiv.org/abs/2305.07301 |