Mathematics – Combinatorics
Scientific paper
2011-10-23
Mathematics
Combinatorics
Journal of Combinatorial Theory A 2009
Scientific paper
10.1016/j.jcta.2008.11.005
Packing and covering problems for metric spaces, and graphs in particular, are of essential interest in combinatorics and coding theory. They are formulated in terms of metric balls of vertices. We consider a new problem in graph theory which is also based on the consideration of metric balls of vertices, but which is distinct from the traditional packing and covering problems. This problem is motivated by applications in information transmission when redundancy of messages is not sufficient for their exact reconstruction, and applications in computational biology when one wishes to restore an evolutionary process. It can be defined as the reconstruction, or identification, of an unknown vertex in a given graph from a minimal number of vertices (erroneous or distorted patterns) in a metric ball of a given radius r around the unknown vertex. For this problem it is required to find minimum restrictions for such a reconstruction to be possible and also to find efficient reconstruction algorithms under such minimal restrictions. In this paper we define error graphs and investigate their basic properties. A particular class of error graphs occurs when the vertices of the graph are the elements of a group, and when the path metric is determined by a suitable set of group elements. These are the undirected Cayley graphs. Of particular interest is the transposition Cayley graph on the symmetric group which occurs in connection with the analysis of transpositional mutations in molecular biology. We obtain a complete solution of the above problems for the transposition Cayley graph on the symmetric group.
Levenshtein Vladimir
Siemons Johannes
No associations
LandOfFree
Error Graphs and the Reconstruction of Elements in Groups does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Error Graphs and the Reconstruction of Elements in Groups, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Error Graphs and the Reconstruction of Elements in Groups will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-526862