DROPS

Document

DOI: 10.4230/LIPIcs.FSTTCS.2024.20

The Isomorphism Problem of Power Graphs and a Question of Cameron

Authors: Bireswar Das, Jinia Ghosh, and Anant Kumar

Published in: LIPIcs, Volume 323, 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024)

Abstract

We study the isomorphism problem of graphs that are defined in terms of groups, namely power graphs, directed power graphs, and enhanced power graphs. We design polynomial-time algorithms for the isomorphism problems for the power graphs, the directed power graphs and the enhanced power graphs arising from finite nilpotent groups. In contrast, no polynomial-time algorithm is known for the group isomorphism problem, even for nilpotent groups of class 2. Our algorithms do not require the underlying groups of the input graphs to be given. A crucial step in our algorithms is to reconstruct the directed power graph from the given power graph or the enhanced power graph. The problem of efficiently computing the directed power graph from a power graph or an enhanced power graph is due to Cameron [IJGT'22]. Bubboloni and Pinzauti [Arxiv'22] gave a polynomial-time algorithm to reconstruct the directed power graph from a power graph. We give an efficient algorithm to compute the directed power graph from an enhanced power graph. The tools and techniques that we design are general enough to give a different algorithm to compute the directed power graph from a power graph as well.

Cite as

Bireswar Das, Jinia Ghosh, and Anant Kumar. The Isomorphism Problem of Power Graphs and a Question of Cameron. In 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 323, pp. 20:1-20:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{das_et_al:LIPIcs.FSTTCS.2024.20,
  author =	{Das, Bireswar and Ghosh, Jinia and Kumar, Anant},
  title =	{{The Isomorphism Problem of Power Graphs and a Question of Cameron}},
  booktitle =	{44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024)},
  pages =	{20:1--20:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-355-3},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{323},
  editor =	{Barman, Siddharth and Lasota, S{\l}awomir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2024.20},
  URN =		{urn:nbn:de:0030-drops-222095},
  doi =		{10.4230/LIPIcs.FSTTCS.2024.20},
  annote =	{Keywords: Graph Isomorphism, Graphs defined on Groups, Power Graphs, Enhanced Power Graphs, Directed Power Graphs, Nilpotent Groups}
}

Search Results

Documents authored by Ghosh, Jinia

The Isomorphism Problem of Power Graphs and a Question of Cameron

Abstract

Cite as

Thanks for your feedback!

Could not send message