Representing Groups on Graphs

DOI10.1007/978-3-642-03816-7_26MaRDI QIDQ3182934zbMATH OpenOpenAlexFDO

Authors Sagarmoy Dutta, Piyush P. Kurur

Publication date 16 October 2009

Published in Mathematical Foundations of Computer Science 2009 (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0904.3941

zbMATH Keywords

abelian group representabilitygeneratorsgraph isomorphismno polynomial time algoirthmpermutation groupsrepresentability problemsolvable group representabilityTuring reducibility

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Representation theory of groups (20C99)

Abstract: In this paper we formulate and study the problem of representing groups on graphs. We show that with respect to polynomial time turing reducibility, both abelian and solvable group representability are all equivalent to graph isomorphism, even when the group is presented as a permutation group via generators. On the other hand, the representability problem for general groups on trees is equivalent to checking, given a group $G$ and $n$, whether a nontrivial homomorphism from $G$ to $S_n$ exists. There does not seem to be a polynomial time algorithm for this problem, in spite of the fact that tree isomorphism has polynomial time algorithm.

Recommendations

• Permutation Groups and the Graph Isomorphism Problem
• scientific article; zbMATH DE number 3896964
• On Cayley representations of finite graphs over abelian p-groups
• Representing graphs by the non-commuting relation
• scientific article; zbMATH DE number 96386

Cites work

• A note on the graph isomorphism counting problem
• Graph Isomorphism is in SPP
• Graph isomorphism is low for PP
• scientific article; zbMATH DE number 4007728 (Why is no real title available?)
• scientific article; zbMATH DE number 3722702 (Why is no real title available?)
• scientific article; zbMATH DE number 3223737 (Why is no real title available?)

Cited in

(5)

• Representability of trees and some of their applications
• Groups as Graphs
• Representing graphs by the non-commuting relation
• Subgroups of minimal index in polynomial time
• On Cayley representations of finite graphs over abelian p-groups

This page was built for publication: Representing Groups on Graphs

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