{'fraction_non_alphanumeric': 0.0589817138759412, 'fraction_numerical': 0.020437432771602725, 'mean_word_length': 3.5762920426579163, 'pattern_counts': {'":': 0, '<': 2, '<?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': 5, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Reconstruction of p-disconnected graphs

We prove that Kelly-Ulam conjecture is true for p-disconnected graphs.


Introduction
Let G be a simple graph. The collection D(G) = (G v ) v∈V (G) of vertex-deleted subgraphs of graph G is called the deck of G. The graph H with deck D(H) = (H u ) u∈V (H) is called the reconstruction of G if there exists a bijection f : v) . In this case we say that the decks D(G) and D(H) are equal. The graph G is reconstructible if it is isomorphic to any of its reconstructions.
The following conjecture, first posed in 1942, is one of the most famious open problems in graph theory. Conjecture 1.1. Kelly-Ulam reconstruction conjecture [11], [17]. Every graph with at least three vertices is reconstructible.
It is clear that a graph is reconstructible if and only if its complement is reconstructible. The class of graphs is called reconstructible if all graphs from this class with at least three vertices are reconstructible. The known examples of reconstructible classes are disconnected graphs, complements of disconnected graphs, regular graphs etc. (see, for example, [4], [5]). Analogously, a graph parameter is reconstructible, if it is the same for all graphs with equal decks. For example, it is easy to show that degree sequence of graph is reconstructible ( [4], [5]).
The class of graphs R is called recognizable if for any graph G ∈ R all its reconstructions also belong to R. The class R is weakly reconstructible if for any G ∈ R every reconstruction of G which belongs to R is isomorphic to G. Clearly R is reconstructible if and only if it is recognizable and weakly reconstructible.
We write u ∼ v (u ∼ v) if vertices u and v are adjacent (non-adjacent). For the subsets U, W ⊆ V (G) the notation U ∼ W means that u ∼ w for all vertices u ∈ U and w ∈ W , U ∼ W means that there are no adjacent vertices u ∈ U and w ∈ W . To shorten notation, we write A triad is a triple T = (G, A, B), where G is a graph and (A, B) is an ordered partition of V (G) into two disjoint subsets. Isomorphism of two triads T = (G, A, B) and S = (H, C, D) is an isomorphism of graphs G and H preserving corresponding partitions. In this case we say, that the triads T and S are isomorphic (T ∼ = S).
Let G be a graph, is naturally partitioned into three parts: (1.1) The partition (1.1) is associated with the module M . In this case we write For every graph G the sets V (G), singleton subsets of V (G) and ∅ are modules. The modules M with 1 < |M | < |V G| are called nontrivial modules or homogeneous sets.
A graph G is called 1-decomposable [16], if there exists a module M (called (1-module)) of G with associated partition (A, B, M ) such that A is a clique and B is a stable set. Otherwise G is called 1-indecomposable. The properties and applications of 1-decomposable graphs are described, for example, in [12], [15], [6]. One of the most important for us facts concerning 1decomposable graphs is the following result of V. Turin.
Theorem 1.1. [14] 1-decomposable graphs are reconstructible A graph G is called P 4 -connected (or p-connected), if for every partition of V (G) into two disjoint sets V 1 and V 2 there exists an induced P 4 (called crossing P 4 ) which contains vertices from both V 1 and V 2 . Otherwise G is called P 4 -disconnected (or p-disconnected). P 4 -disconnected graphs were introduced by B. Jamison and S. Olariu in [10]. The p-connected component of G is a maximal induced p-connected subgraph of G. It is clear that every disconnected graph is p-disconnected, but inverse inclusion is not true.
A graph is called split [9], if there exists a partition of its set of vertices V (G) = A ∪ B into a clique and a stable set. This partition is called a bipartition and denoted as (A, B).
In this paper we prove that P 4 -disconnected graphs are reconstructible. In particular, it generalizes the results about reconstructibility of disconnected graphs, complements of disconnected graphs and 1-decomposable graphs.
We show that the reconstructibility of P 4 -disconnected graphs implies the reconstructibility of P 4 -tidy graphs. Therefore, in particular, all listed above classes are also reconstructible. Note, that the reconstructibility of P 4 -reducible graphs was proved by B. Thatte in [13].

Reconstruction of p-disconnected graphs.
A p-connected graph S is called separable [10], if there exists a disjoint partition of its vertex set V (S) = A ∪ B such that every crossing P 4 has its midpoints in A and its endpoints in B. In this case a triad (S, A, B) is called a separable p-connected triad.  Note, that, in particular, separable p-connected triad contains at least four vertices. A split graph G with bipartition (A, B) is called spider, if there exists a bijection f : B → A such that one of the following conditions holds: Proof. Since thick spiders are complements of thin spiders, it is sufficient to prove that thin spiders are reconstructible.
Let G be a graph with Taking into account Theorem 2.1, it is evident that G is a thin spider if and only if (2.2) and the following conditions hold: Since degree sequence of graph is reconstructible, thin spiders are reconstructible.
If every vertex of G is a p-articulation vertex, then G is called minimally p-connected.

Theorem 2.3. [2]
A p-connected graph which is not minimally p-connected contains at least two vertices which are not p-articulation vertices.
The following structure theorem was proved in [10]. In our terms it could be written in the following way: Theorem 2.4. [10]. For an arbitrary graph G exactly one of the following statements is true: For example, all connected and anticonnected 1-decomposable graphs satisfy 3). Let R be the class of graphs G such that a) G is p-disconnected; b) G is both connected and anticonnected; To prove, that p-disconnected graphs are reconstructible, by Theorem 2.4 it is sufficient to prove that class R is reconstructible. there is no crossing P 4 . Indeed, let vertices x, y, z, t induces crossing P 4 for the partition (2.3) with midpoints y, z and endpoints x, t such that y ∼ x, z ∼ t. The only possibility is x ∈ C, y ∈ A, z, t ∈ B. Then the vertices z and t belongs to the same connected component U of S [B]. But since U is a homogeneous set and y ∼ z we have y ∼ t. The contradiction is obtained.
As a corollary we obtain that 1-decomposable graphs are p-disconnected.

Lemma 2.5. Graph is p-disconnected if and only if it is not a spider and at most one of its cards is p-connected.
Proof. Assume, that G is p-disconnected graph. By Theorem 2.2 G is not a spider. Let's show that at most one card of G is p-connected.
If G (G) is disconnected, then clearly at most one card of G is connected (anticonnected), therefore our statement is true. Let Inversely, let G is not a spider and at most one of its card is p-connected. Suppose that G is p-connected. Then by Theorem 2.3 there exist at least two p-connected cards of G. This is contradiction.
Since spiders are reconstructible, the following corollary is true.

Corollary 2.1. p-disconnected graphs are recognizable
Since disconnected graphs, antidisconnected graphs and 1-decomposable graphs are reconstructible, we have

Corollary 2.2. Class R is recognizable
In the further considerations we will use the following technical lemma. Proof. Let G 1 = T 1 • H 1 , G 2 = T 2 • H 2 be two graphs from R with equal decks D(G 1 ) and D(G 2 ), T 1 = (S 1 , A 1 , B 1 ), T 2 = (S 2 , A 2 , B 2 ) are separable p-connected triads from the definition of the class R. By Theorem 2.4 G 1 ∼ = G 2 if and only if T 1 ∼ = T 2 and H 1 ∼ = H 2 . Let It is evident, that all vertex-deleted triads T 1 v , T 2 u are generalized split triads. Therefore by Lemma 2.4 there exists a unique p-connected card of G 1 , and this card is isomorphic to S 1 . If and hence by Lemma 2.4 all cards of G 2 are p-disconnected.
Therefore |H 2 | = 1 and there exists a unique p-connected card of G 2 , isomorphic to S 2 . Thus we have S 1 ∼ = S 2 . By Lemma 2.1 T 1 ∼ = T 2 and consequently G 1 ∼ = G 1 . Let Then where By Lemma 2.4 all cards from D(G i ), i = 1, 2, are p-disconnected. Clearly all cards from D T i , i = 1, 2 are both connected and anticonnected p-disconnected graphs (since so is G i ).
But then, for example, B 2 ∼ C 2 ∩ ϕ(A 1 ), that is impossible. Therefore by Lemma 2.6 it is true, that ϕ( Now let's show that there exist v ∈ V (G 1 ) and u ∈ V (G 2 ) such that Suppose the contrary. Then there exist By Proposition 2.1 and The contradiction is obtained. So, consider v ∈ V (G 1 ), u ∈ V (G 2 ) such that (2.7) holds. We have

By Theorem 2.4 it is true that
Indeed, if there exist the cards from D T 1 and D H 2 such that (2.8) holds, then the inequality (2.10) is true. This contradicts (2.12).
It remains to prove that H 1 ∼ = H 2 .
Since G is 1 indecomposable, we have that S 1 is not a split graph. Thus there exists a connected component X of Therefore it is easy to see, that for any v ∈ X T 1 v is separable p-connected triad and the card G 1 v is both connected and anticonnected p-disconnected graph. Let • H 2 and let ψ be isomorphism of graphs G 1 v and G 2 u . By the same reasoning, as in the proof of Proposition 2.1 we have ψ(( So, Corollary 2.2 and Lemma 2.7 imply Theorem 2.5. p-disconnected graphs are reconstructible. A quasi-starfish (resp. quasi-urchin) [8] is a graph obtained from a thick spider (resp. thin spider) by replacing at most one vertex by a K 2 or a O 2 .
Theorem 2.6. [8] A graph G is P 4 -tidy if and only if every p-component of G is isomorphic to either a P 5 or a P 5 or a C 5 or a quasi-starfish or a quasi-urchin. Corollary 2.3. P 4 -tidy graphs are reconstructible.
Proof. Let G be P 4 -tidy graph. If G is p-disconnected, then by Theorem 2.5 G is reconstructible. Suppose that G is p-connected. Then G is isomorphic to either a P 5 or a P 5 or a C 5 or a quasistarfish or a quasi-urchin. Clearly P 5 , P 5 , C 5 are reconstructible. Moreover, quasi-starfishes are complements of quasi-urchins and by Lemma 2.3 spiders are reconstructible. Thus it is sufficient to consider the case, then G is obtained from a thin spider H with bipartition (A, B) and with at least 6 vertices by replacing a vertex v ∈ V (H) by K 2 or O 2 . Consider the following cases: 1) v ∈ A is replaced by K 2 . In [15] the complete description of the structure of 1-indecomposable split unigraphs is presented. From that description one can see that G is a split unigraph and thus G is reconstructible.
2) v ∈ B is replaced by O 2 . By the same description from [15] G is a split unigraph and therefore G is reconstructible.
3) v ∈ B is replaced by K 2 . It is easy to see that a graph F is isomorphic to G if and only if |V (F )| = |V (G)|, there exist exactly two vertices x, y ∈ V (F ) with deg(x) = deg(y) = 2 and F x ∼ = F y is a thin spider. Therefore it is evident, that G is reconstructible. 4) v ∈ A is replaced by O 2 . Then it is also easy to see that a graph F is isomorphic to G if and only if |V (F )| = |V (G)| = 2k + 1, k ≥ 3 and there exist two vertices x, y ∈ V (F ) such that deg(x) = deg(y) = k and cards F x , F y are thin spiders. Thus in this case G is also reconstructible.