{'fraction_non_alphanumeric': 0.06133333333333333, 'fraction_numerical': 0.005866666666666667, 'mean_word_length': 3.3126436781609194, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Graph Reconstruction by Permutations

Let G and H be graphs with a common vertex set V , such that G−i ∼= H−i, for all i ∈ V . Let pi be the permutation of V − i that maps G− i to H − i, and let qi denote the permutation obtained from pi by mapping i to i. It is shown that certain algebraic relations involving the edges of G and the permutations qiq −1 j and qiq −1 k , where i, j, k ∈ V are distinct vertices, often force G and H to be isomorphic. 1. Permutations and Partial Permutations Let G and H be graphs with a common vertex set V , such that G − i ∼= H − i, for all i ∈ V . Ulam’s conjecture, also known as the graph reconstruction conjecture (see Bondy [1]), states that this condition implies that G ∼= H, if |V | ≥ 3. All graphs that we will work with are simple graphs, with the same vertex set V . We will view a graph G as a set of edges, where each edge is an unordered pair of distinct vertices. We write ( V 2 ) for the set of all unordered pairs of vertices. Thus, G ⊆ ( V 2 ) . The complement of G is G = ( V 2 ) −G. An unordered pair of vertices is denoted by [x, y]. (The square brackets are convenient when it is necessary to construct sets of unordered pairs.) It will often be convenient to write [x, y]G = 1 to mean that [x, y] ∈ G, and [x, y]G = 0 to mean that [x, y] 6∈ G. Given a permutation q of V , and a vertex x ∈ V , the image of x under q is denoted x. Then [x, y] = [x, y]. We also write G for the graph obtained from G by permuting each edge of G by q. Let pi be an isomorphism of G − i with H − i, so that (G − i)i = H − i. Then pi is a partial permutation of the set V . It does not map the point i. * This work was partially supported by an operating grant from the Natural Sciences and Engineering Research Council of Canada. It was partially done while W. Kocay was visiting the University Aix-Marseille II as an invited professor.