Vertex reconstruction in Cayley graphs

DOI10.1016/j.disc.2008.07.039zbMath1182.05085OpenAlexW2026548724MaRDI QIDQ1011492

Elena V. Konstantinova

Publication date: 8 April 2009

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2006/786/

zbMATH Keywords

Cayley graphssigned permutationspancake problemsorting by reversalsvertex reconstruction problemthe hyperoctahedral groupthe symmetric group

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)

Related Items (7)

Metric intersection problems in Cayley graphs and the Stirling recursion ⋮ The evolution of the random reversal graph ⋮ One conjecture of bubble-sort graphs ⋮ Unnamed Item ⋮ Some problems on Cayley graphs ⋮ Distance in cayley graphs on permutation groups generated by $k$ $m$-Cycles ⋮ Resistance distances in Cayley graphs on symmetric groups

Cites Work

• Unnamed Item
• Unnamed Item
• Small-diameter Cayley graphs for finite simple groups
• On the diameter of Cayley graphs of the symmetric group
• Processor interconnection networks from Cayley graphs
• Bounds for sorting by prefix reversal
• Reconstruction of objects from a minimum number of distorted patterns
• On the problem of sorting burnt pancakes
• Symmetry in interconnection networks based on Cayley graphs of permutation groups: A survey
• Reconstruction of permutations distorted by reversal errors
• On reconstruction of signed permutations distorted by reversal errors
• Combinatorics of Coxeter Groups
• A group-theoretic model for symmetric interconnection networks
• The minimum-length generator sequence problem is NP-hard
• On the Diameter of the Pancake Network
• Efficient reconstruction of sequences
• Genome Rearrangements and Sorting by Reversals
• On the diameter and bisector size of Cayley graphs
• Sorting with fixed-length reversals

This page was built for publication: Vertex reconstruction in Cayley graphs