REVIEW 2 cited by
Aspects of the commuting graph
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
abstract
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.
Forward citations
Cited by 2 Pith papers
-
On the Complexity of Problems on Graphs Defined on Groups
Under ETH, isomorphism-invariant problems cannot be NP-complete on power graphs; Graph Motif is hard on power graphs of cyclic groups, and recognition is polynomial for abelian and some nilpotent power graphs.
-
Commuting Graph of Unitriangular Group UT(4; p)
For the commuting graph of UT(4,p), the paper proves connectivity, diameter 3, clique number p^4, maximal cliques of size p^3 or p^4, and bounds on chromatic and independence numbers.
Discussion (0). Continue with ORCID to comment.