# Twin Subgraphs and Core-Semiperiphery-Periphery Structures

Authors: Ricardo Riaza
Journal: Complexity
 (2018)

---

## Abstract

A standard approach to reduce the complexity of very large networks is to group together sets of nodes into clusters according to some criterion which reflects certain structural properties of the network. Beyond the well-known modularity measures defining communities, there are criteria based on the existence of similar or identical connection patterns of a node or sets of nodes to the remainder of the network. A key notion in this context is that ofstructurally equivalent ortwin nodes, displaying exactly the same connection pattern to the remainder of the network. Our first goal is to extend this idea to subgraphs of arbitrary order of a given network, by means of the notions of T-twin and F-twin subgraphs. This research, which leads to graph-theoretic results of independent interest, is motivated by the need to provide a systematic approach to the analysis of core-semiperiphery-periphery (CSP) structures, a notion which is widely used in network theory but that somehow lacks a formal treatment in the literature. The goal is to provide an analytical framework accommodating and extending the idea that the unique (ideal) core-periphery (CP) structure is a 2-partitioned K2, a fact which is here understood to rely on the true and false twin notions for vertices already known in network theory. We provide a formal definition of such CSP structures in terms of core eccentricities and periphery degrees, with semiperiphery vertices acting as intermediaries between both. The T-twin and F-twin notions then make it possible to reduce the large number of resulting structures, paving the way for the decomposition and enumeration of CSP structures. We compute explicitly the resulting CSP structures up to order six. We illustrate the scope of our results by analyzing a subnetwork of the well-known network of metal manufactures trade arising from 1994 world trade statistics.


---

## Body

## 1. Introduction

The notion of a core-periphery (CP) structure can be traced back at least to some research on economic and commercial networks developed in the late 1970s and early 1980s [1–3], largely emanating from the influential work of Wallerstein on world systems analysis [4]. These ideas were revisited and addressed in a more formal framework by Borgatti and Everett in [5]. For these authors, the two key ideas in the definition of a core-periphery structure in a network context are those of a dense, cohesive core of heavily interconnected nodes and a sparse periphery of nodes, essentially lacking any connections among them; by contrast, the connection pattern between the core and the periphery admits several definitions and, actually, the core-periphery connection densities differ from some models to others. In idealized models, core nodes are fully connected among them, periphery nodes are isolated (within the periphery subnetwork), whereas the core and the periphery may either be fully connected or totally disconnected. Since then, a great deal of research has been directed to the detection of such core-periphery structures in real networks, measuring how well they approximate the ideal ones, and to the development of analytical and computational tools to classify nodes in such networks (cf. [6–12] and references therein). Other approaches to the definition of a core-periphery structure can be found in [13–15].Even though the idea of a core-semiperiphery-periphery (CSP) structure can be also found in the aforementioned sociological works (cf. [3, 4]) and despite the fact that this concept has been widely used since then (see e.g., [8, 11, 16, 17]), the network literature seems to lack a formal definition and a systematic classification of these CSP structures. In the aforementioned paper by Borgatti and Everett [5], these authors indicate that there are many reasonable options to define a CSP structure and, further, discrete partitions with more than three classes. The difficulty does not seem to rely on providing a formal definition but on classifying the resulting “reasonable options,” quoting these authors; more precisely, there is a need for a notion of similar or equivalent subgraphs making it possible to somehow reduce the number of different CSP structures. When dealing with core-periphery structures, there is a well-known subgraph similarity notion which makes this reduction feasible, namely, that ofstructural equivalence defining so-calledtwin nodes (broadly, two vertices are twins if they have the same neighbors; a distinction is made betweentrue twins andfalse twins depending on whether both vertices are adjacent or not; details are given in Section 2). Essentially, under structural equivalence, K2 will be the unique core-periphery structure: details are provided later, but the reader can think for the moment, for example, of the star Sn as a network with a unique core (the central node) to whom n-1 peripheric nodes are attached; all n-1 leaves have the same set of neighbors, namely, the central node, and are therefore structurally equivalent (more precisely, they will be false twins); then, after identifying all leaves in light of this twin notion for vertices, the quotient graph amounts to K2.But in the network literature there is no equivalence notion for “similar” higher order subgraphs, which would pave the way to a systematic reduction of (eventually defined) CSP structures. As explained in detail in Section2 (see, specifically, Section 2.3), the goal of this paper is to fill this gap by introducing a mathematical framework allowing for a systematic classification of CSP networks and other partitioned structures. The key idea is to introduce the concept oftwin subgraphs, a notion which extends to arbitrary order that of twin (structurally equivalent) vertices. This mathematical framework will be developed in Sections 3 and 4, which address graph-theoretic problems of independent interest (i.e., problems which go beyond the eventual application of these notions to the classification of CSP structures). These sections introduce and elaborate on the idea ofF-twin andT-twin subgraphs, which in a sense are dual to each other and generalize several known properties of false twin and true twin vertices; for example, distinct connected components of F-twin pairs will be proved to be disjoint and nonadjacent, whereas disjoint T-twin pairs will be fully connected to each other. With this background, the classification of CSP networks will then be tackled in Section 5. In Section 6 we present the lines along which these structures can be identified in real cases by analyzing a subnetwork of the network of manufactures of metal arising from 1994 world trade statistics. These data are available and analyzed in [16], in the spirit of the aforementioned seminal work [4], and nowadays define a widely used benchmark for the positional analyses of networks. Finally, Section 7 compiles some lines for future research.


## 2. Background on Graphs, Twins, and Core-Periphery Networks

### 2.1. Graph-Theoretic Notions

We refer the reader to [18–21] for excellent introductions to graph theory. Throughout the paper we will work with undirected graphs G=(V,E) without parallel edges or self-loops, so that edges can be thought of as pairs of distinct vertices (also termednodes). Given a graph G, its vertex and edge sets will be written as V(G) and E(G), respectively, or simply as V and E if there is no possible ambiguity. We will only work with finite graphs; that is, the order (number of vertices) will be finite in all cases. With notational abuse, we will often write v∈G to mean v∈V(G) and V0⊆G for V0⊆V(G). Analogously, we will say that two graphs are disjoint when their vertex sets are disjoint (note that the latter implies that the edge sets are disjoint as well).Apath of length k≥0 is a graph with k+1 distinct vertices v0, v1,…,vk and edges e1,…,ek with ei joining vi-1 and vi. Since we are not allowing parallel edges, a path is uniquely defined by its vertex set. We say that v0 and vk arelinked by such a path. When k≥1, sometimes the vertex set will be implicitly assumed to inherit the order defined by the indices and we will then speak of a pathfromv0tovk. Thedistance, d, between a pair of distinct vertices in the same connected component of a given graph is the length of a shortest path linking them. Theeccentricity of a vertex in a connected graph is the maximum distance to other vertices. The distance between two disjoint subgraphs H1 and H2 lying in the same connected component of a given graph is defined as min⁡du,v,u∈H1,v∈H2. We say that two disjoint subgraphs H1 and H2 are not adjacent if there is no adjacent pair (u,v) with u∈H1 and v∈H2; if both subgraphs lie in the same connected component of G, this is equivalent to saying that d(H1,H2)≥2.We will denote byN(u) the set of neighbors of a given vertex u (namely, the set of vertices adjacent to u), and write N[u]=N(u)∪{u}. Thedegree of a vertex u is the number of elements in N(u). We will call a vertex of degree one aleaf (note that this term is often reserved to cases in which the whole graph is acyclic, i.e., a disjoint union of trees) and will say that it isattached to its unique adjacent vertex.Thenull graph defined by V=∅ will be denoted by K0; Kn with n≥1 stands for the complete graph on n vertices. The complement of a graph G=(V,E) of order n (namely, (V,E(Kn)-E)) will be written as G¯, and En will stand for theempty graphKn¯ on n≥1 vertices. Cycles, paths, and stars on n vertices will be written as Cn, Pn, and Sn, respectively, with n≥3 for cycles. As usual, the union and intersection of Gi=(Vi,Ei) (i=1, 2) are the graphs (V1∪V2,E1∪E2) and (V1∩V2,E1∩E2), respectively. ThejoinG1+G2 of two graphs with disjoint vertex sets V(G1) and V(G2) is the graph obtained after enlarging G1∪G2 with all possible edges joining the vertices of G1 to those of G2 (sometimes we express the latter by saying that G1 and G2 are fully connected to one another).Apartitioned graph is simply a graph whose vertex set is split into (pairwise disjoint) classes. A k-partitioned graph is a partitioned graph with k nonempty partition classes. Obviously, a partitioned graph defines an equivalence relation in the set of vertices. Thequotient graph (often called asupergraph) of a partitioned graph is defined as a graph whose vertex set is the quotient set (i.e., vertices in the quotient graph correspond to the partition classes in the original graph), with two distinct vertices in the quotient being adjacent if and only if the original graph has at least one edge which joins vertices belonging to the corresponding pair of classes.Anisomorphism of two graphs G1 and G2 is a bijection φ:V1→V2 (with Vi=V(Gi)) which preserves adjacencies, that is, any given pair of vertices u and v in G1 are adjacent if and only if φ(u) and φ(v) are adjacent in G2. An isomorphism of partitioned graphs is a graph isomorphism which keeps the classes invariant.


### 2.2. Twins

Different analytical and computational issues arise in connection with the existence and the distribution of isomorphic copies of certain subgraphs of a given graph: see, for example, [21–25] and references therein. From a different perspective, some attention has been focused on vertices which share the same connection pattern within a graph. Such vertices receive (at least) two different names in the literature, namely,twins andstructurally equivalent vertices, as detailed in the sequel. Two (distinct) vertices u and v arefalse twins (resp.,true twins) if N(u)=N(v) (resp., N[u]=N[v]) [26–29]. The exclusion of self-loops yields u∉N(u) and this implies that false twins are not adjacent. In the dual case, true twins are necessarily adjacent to each other: for these reasons, true and false twins are also calledadjacent andnonadjacent twins (see, e.g., [26, 29, 30]). True twins correspond to 1-twins in the terminology of [31, 32]. By contrast, in the social network analysis literature twin vertices u and v are said to be(weakly) structurally equivalent: this means that the transposition tu,v of u and v yields an automorphism of the graph (cf. [33, 34]), a condition which is easily seen equivalent to u and v being (false or true) twins in the sense indicated above.The F-twin and T-twin notions that will be introduced in Sections3 and 4 for arbitrary subgraphs somehow combine the two ideas at the beginning of the paragraph above. Twin subgraphs will be isomorphic copies of each other and, additionally, they will share the connection pattern to the remainder of the graph; in other words, our approach will define a structural equivalence notion for (isomorphic) subgraphs which extends the one already defined for single vertices. Consistently, twin subgraphs will retain,mutatis mutandis, certain properties already known for twin vertices, such as the aforementioned adjacency properties (which will hold for disjoint twin subgraphs; cf. Corollaries 6 and 17), the duality between F-twins and T-twins in the sense that a pair of twins of one type defines a pair of the other on the complement graph (Theorem 18), or the fact that twins will have the same distance multisets to the vertex set of the graph (cf. Proposition 8). In particular, twin subgraphs will definehomometric sets (Corollary 9; cf. [35–37]). Both notions will induce a classification in the family of isomorphic copies of each induced subgraph, extending the way in which false and true twin concepts classify the vertices of a graph. These, together with other related results, will be extensively discussed in Sections 3 and 4.


### 2.3. Core-Periphery Networks

Consider one of the “idealized” core-periphery (CP) networks mentioned in Section1, namely, the one defined by a 2-partitioned graph with the following two classes of vertices:(i)
Core vertices, which are fully connected to each other and also to the vertices in the second class (defined below)(ii)
Periphery vertices, totally disconnected from each other (and fully connected to the core, in light of the first requirement above).As indicated in the Introduction, other core-periphery connection patterns are possible, although the one above is often used as a starting point in different analytical and computational approaches to this topic (see, e.g., [5, 16]). These core-periphery networks are simply 2-partitioned graphs of the form Kp+Er (find notations in Section 2.1; when using a 2-partitioned structure in Kp+Er, we assume throughout the document and without further mention that the two partition classes are the vertex sets of Kp and Er). Cases with a unique core vertex amount to the star Sn=K1,n-1=K1+En-1. In the simplest setting (n=2) we get a 2-partitioned S2=K2=K1+K1, with a single core and a single periphery vertex; note that E1=K1, and we prefer to use the latter notation for the singleton graph.Aiming at later developments lets us note that, in a certain sense,K2 is substantially different from all other joins Kp+Er. Actually, we may think of K2=K1+K1 as the quotient graph of any other join of the form Kp+Er. But, in order to extend these ideas to support the definition and classification of more complex structures, we emphasize that the reduction above comprises more than a quotient reduction. Indeed, all core vertices (namely, those of Kp) are true twins as defined in Section 2.2 above and, analogously, all periphery vertices (the ones in Er) are false twins. In this context, K2 arises not only as the reduction of other joins, but also as the uniquetwin-free network meeting the requirements (i) and (ii) above. From this point of view we may think of K2 as the unique core-peripherystructure (we use the latter term to make a distinction with the CP networks Kp+Er above, which are allowed to display twin vertices). To avoid any misunderstanding, let us clarify that K2 is twin-free only as a 2-partitioned graph; that is, we cannot consider both vertices as (true) twins because they belong to different partition classes; see the beginning of Section 5.However, when scaling these ideas to define formally core-semiperiphery-periphery (CSP) structures and eventually other structures with more partition classes, one finds the problem that there is no appropriate analog of the twin notions mentioned above for subgraphs with more than one vertex. Since the intuitive idea behind the concept of a core is that of a set of heavily connected vertices, the true twin notion for single vertices may well apply to reduce the number of admissible core subgraphs in these higher order structures; by contrast, in the literature one finds no way to reduce conveniently the semiperiphery-periphery subgraph.To put it in the simplest possible setting, compare the CP networkK1+E2 (Figure 1(a)), which amounts to a 2-partitioned path P3 with one class (the core, painted black in the figure) defined by the central node, with a 3-partitioned path P5 in which the three classes are defined by the central vertex (core), the two vertices with eccentricity three (semiperiphery vertices, grey) and the two leaves (periphery vertices, white) (Figure 1(b)). We may think of the latter as a (sometimes called)spider graph with a central vertex (the core) and two legs, each one a P2=K2 attached to the core by a single articulation (the semiperiphery vertices).Figure 1As indicated above, in the CP case (K1+E2) the false twin notion makes it possible to identify the two peripheries into a single one, reducing the network to a 2-partitioned K2=P2 (cf. Figure 2(a)). But, how can we reduce the CSP case (the spider) to a single P3, which captures the essential connection pattern? (Figure 2(b)). Note that both legs in Figure 1(b) have exactly the same structure and, accordingly, we should find a systematic way to perform such reduction. Note also that neither the semiperiphery vertices nor the periphery ones in Figure 1(b) are false twins, so that an eventual recourse to the notion of twin vertices would fail for our present purpose.Figure 2Obviously, it would be easy to identify equal-length legs in spider graphs; however, more complex structures are possible: think, for example, of cases with more cores and/or with other connection patterns within the semiperiphery (actually, different CSP structures will arise in Sections5 and 6). Additionally, the goal should be the development of a broader mathematical framework allowing for an identification of (say) structurally equivalent, higher order subgraphs in greater generality. The idea is to formalize the notion of isomorphic subgraphs or arbitrary order displaying, in a sense to be made precise, the same connection patterns to the remainder of the graph, generalizing the false twin and true twin concepts for single vertices. The F-twin notion for arbitrary subgraphs, together with the dual concept of T-twin subgraphs, is aimed at filling this gap. After introducing and discussing these ideas in Sections 3 and 4, we will be back to CSP structures in Sections 5 and 6.


## 2.1. Graph-Theoretic Notions

We refer the reader to [18–21] for excellent introductions to graph theory. Throughout the paper we will work with undirected graphs G=(V,E) without parallel edges or self-loops, so that edges can be thought of as pairs of distinct vertices (also termednodes). Given a graph G, its vertex and edge sets will be written as V(G) and E(G), respectively, or simply as V and E if there is no possible ambiguity. We will only work with finite graphs; that is, the order (number of vertices) will be finite in all cases. With notational abuse, we will often write v∈G to mean v∈V(G) and V0⊆G for V0⊆V(G). Analogously, we will say that two graphs are disjoint when their vertex sets are disjoint (note that the latter implies that the edge sets are disjoint as well).Apath of length k≥0 is a graph with k+1 distinct vertices v0, v1,…,vk and edges e1,…,ek with ei joining vi-1 and vi. Since we are not allowing parallel edges, a path is uniquely defined by its vertex set. We say that v0 and vk arelinked by such a path. When k≥1, sometimes the vertex set will be implicitly assumed to inherit the order defined by the indices and we will then speak of a pathfromv0tovk. Thedistance, d, between a pair of distinct vertices in the same connected component of a given graph is the length of a shortest path linking them. Theeccentricity of a vertex in a connected graph is the maximum distance to other vertices. The distance between two disjoint subgraphs H1 and H2 lying in the same connected component of a given graph is defined as min⁡du,v,u∈H1,v∈H2. We say that two disjoint subgraphs H1 and H2 are not adjacent if there is no adjacent pair (u,v) with u∈H1 and v∈H2; if both subgraphs lie in the same connected component of G, this is equivalent to saying that d(H1,H2)≥2.We will denote byN(u) the set of neighbors of a given vertex u (namely, the set of vertices adjacent to u), and write N[u]=N(u)∪{u}. Thedegree of a vertex u is the number of elements in N(u). We will call a vertex of degree one aleaf (note that this term is often reserved to cases in which the whole graph is acyclic, i.e., a disjoint union of trees) and will say that it isattached to its unique adjacent vertex.Thenull graph defined by V=∅ will be denoted by K0; Kn with n≥1 stands for the complete graph on n vertices. The complement of a graph G=(V,E) of order n (namely, (V,E(Kn)-E)) will be written as G¯, and En will stand for theempty graphKn¯ on n≥1 vertices. Cycles, paths, and stars on n vertices will be written as Cn, Pn, and Sn, respectively, with n≥3 for cycles. As usual, the union and intersection of Gi=(Vi,Ei) (i=1, 2) are the graphs (V1∪V2,E1∪E2) and (V1∩V2,E1∩E2), respectively. ThejoinG1+G2 of two graphs with disjoint vertex sets V(G1) and V(G2) is the graph obtained after enlarging G1∪G2 with all possible edges joining the vertices of G1 to those of G2 (sometimes we express the latter by saying that G1 and G2 are fully connected to one another).Apartitioned graph is simply a graph whose vertex set is split into (pairwise disjoint) classes. A k-partitioned graph is a partitioned graph with k nonempty partition classes. Obviously, a partitioned graph defines an equivalence relation in the set of vertices. Thequotient graph (often called asupergraph) of a partitioned graph is defined as a graph whose vertex set is the quotient set (i.e., vertices in the quotient graph correspond to the partition classes in the original graph), with two distinct vertices in the quotient being adjacent if and only if the original graph has at least one edge which joins vertices belonging to the corresponding pair of classes.Anisomorphism of two graphs G1 and G2 is a bijection φ:V1→V2 (with Vi=V(Gi)) which preserves adjacencies, that is, any given pair of vertices u and v in G1 are adjacent if and only if φ(u) and φ(v) are adjacent in G2. An isomorphism of partitioned graphs is a graph isomorphism which keeps the classes invariant.


## 2.2. Twins

Different analytical and computational issues arise in connection with the existence and the distribution of isomorphic copies of certain subgraphs of a given graph: see, for example, [21–25] and references therein. From a different perspective, some attention has been focused on vertices which share the same connection pattern within a graph. Such vertices receive (at least) two different names in the literature, namely,twins andstructurally equivalent vertices, as detailed in the sequel. Two (distinct) vertices u and v arefalse twins (resp.,true twins) if N(u)=N(v) (resp., N[u]=N[v]) [26–29]. The exclusion of self-loops yields u∉N(u) and this implies that false twins are not adjacent. In the dual case, true twins are necessarily adjacent to each other: for these reasons, true and false twins are also calledadjacent andnonadjacent twins (see, e.g., [26, 29, 30]). True twins correspond to 1-twins in the terminology of [31, 32]. By contrast, in the social network analysis literature twin vertices u and v are said to be(weakly) structurally equivalent: this means that the transposition tu,v of u and v yields an automorphism of the graph (cf. [33, 34]), a condition which is easily seen equivalent to u and v being (false or true) twins in the sense indicated above.The F-twin and T-twin notions that will be introduced in Sections3 and 4 for arbitrary subgraphs somehow combine the two ideas at the beginning of the paragraph above. Twin subgraphs will be isomorphic copies of each other and, additionally, they will share the connection pattern to the remainder of the graph; in other words, our approach will define a structural equivalence notion for (isomorphic) subgraphs which extends the one already defined for single vertices. Consistently, twin subgraphs will retain,mutatis mutandis, certain properties already known for twin vertices, such as the aforementioned adjacency properties (which will hold for disjoint twin subgraphs; cf. Corollaries 6 and 17), the duality between F-twins and T-twins in the sense that a pair of twins of one type defines a pair of the other on the complement graph (Theorem 18), or the fact that twins will have the same distance multisets to the vertex set of the graph (cf. Proposition 8). In particular, twin subgraphs will definehomometric sets (Corollary 9; cf. [35–37]). Both notions will induce a classification in the family of isomorphic copies of each induced subgraph, extending the way in which false and true twin concepts classify the vertices of a graph. These, together with other related results, will be extensively discussed in Sections 3 and 4.


## 2.3. Core-Periphery Networks

Consider one of the “idealized” core-periphery (CP) networks mentioned in Section1, namely, the one defined by a 2-partitioned graph with the following two classes of vertices:(i)
Core vertices, which are fully connected to each other and also to the vertices in the second class (defined below)(ii)
Periphery vertices, totally disconnected from each other (and fully connected to the core, in light of the first requirement above).As indicated in the Introduction, other core-periphery connection patterns are possible, although the one above is often used as a starting point in different analytical and computational approaches to this topic (see, e.g., [5, 16]). These core-periphery networks are simply 2-partitioned graphs of the form Kp+Er (find notations in Section 2.1; when using a 2-partitioned structure in Kp+Er, we assume throughout the document and without further mention that the two partition classes are the vertex sets of Kp and Er). Cases with a unique core vertex amount to the star Sn=K1,n-1=K1+En-1. In the simplest setting (n=2) we get a 2-partitioned S2=K2=K1+K1, with a single core and a single periphery vertex; note that E1=K1, and we prefer to use the latter notation for the singleton graph.Aiming at later developments lets us note that, in a certain sense,K2 is substantially different from all other joins Kp+Er. Actually, we may think of K2=K1+K1 as the quotient graph of any other join of the form Kp+Er. But, in order to extend these ideas to support the definition and classification of more complex structures, we emphasize that the reduction above comprises more than a quotient reduction. Indeed, all core vertices (namely, those of Kp) are true twins as defined in Section 2.2 above and, analogously, all periphery vertices (the ones in Er) are false twins. In this context, K2 arises not only as the reduction of other joins, but also as the uniquetwin-free network meeting the requirements (i) and (ii) above. From this point of view we may think of K2 as the unique core-peripherystructure (we use the latter term to make a distinction with the CP networks Kp+Er above, which are allowed to display twin vertices). To avoid any misunderstanding, let us clarify that K2 is twin-free only as a 2-partitioned graph; that is, we cannot consider both vertices as (true) twins because they belong to different partition classes; see the beginning of Section 5.However, when scaling these ideas to define formally core-semiperiphery-periphery (CSP) structures and eventually other structures with more partition classes, one finds the problem that there is no appropriate analog of the twin notions mentioned above for subgraphs with more than one vertex. Since the intuitive idea behind the concept of a core is that of a set of heavily connected vertices, the true twin notion for single vertices may well apply to reduce the number of admissible core subgraphs in these higher order structures; by contrast, in the literature one finds no way to reduce conveniently the semiperiphery-periphery subgraph.To put it in the simplest possible setting, compare the CP networkK1+E2 (Figure 1(a)), which amounts to a 2-partitioned path P3 with one class (the core, painted black in the figure) defined by the central node, with a 3-partitioned path P5 in which the three classes are defined by the central vertex (core), the two vertices with eccentricity three (semiperiphery vertices, grey) and the two leaves (periphery vertices, white) (Figure 1(b)). We may think of the latter as a (sometimes called)spider graph with a central vertex (the core) and two legs, each one a P2=K2 attached to the core by a single articulation (the semiperiphery vertices).Figure 1As indicated above, in the CP case (K1+E2) the false twin notion makes it possible to identify the two peripheries into a single one, reducing the network to a 2-partitioned K2=P2 (cf. Figure 2(a)). But, how can we reduce the CSP case (the spider) to a single P3, which captures the essential connection pattern? (Figure 2(b)). Note that both legs in Figure 1(b) have exactly the same structure and, accordingly, we should find a systematic way to perform such reduction. Note also that neither the semiperiphery vertices nor the periphery ones in Figure 1(b) are false twins, so that an eventual recourse to the notion of twin vertices would fail for our present purpose.Figure 2Obviously, it would be easy to identify equal-length legs in spider graphs; however, more complex structures are possible: think, for example, of cases with more cores and/or with other connection patterns within the semiperiphery (actually, different CSP structures will arise in Sections5 and 6). Additionally, the goal should be the development of a broader mathematical framework allowing for an identification of (say) structurally equivalent, higher order subgraphs in greater generality. The idea is to formalize the notion of isomorphic subgraphs or arbitrary order displaying, in a sense to be made precise, the same connection patterns to the remainder of the graph, generalizing the false twin and true twin concepts for single vertices. The F-twin notion for arbitrary subgraphs, together with the dual concept of T-twin subgraphs, is aimed at filling this gap. After introducing and discussing these ideas in Sections 3 and 4, we will be back to CSP structures in Sections 5 and 6.


## 3. F-Twin Subgraphs

### 3.1. Definition and Elementary Properties

Definition 1.
LetH1 and H2 be two induced subgraphs of a graph G. Denote by Vi the vertex set of Hi. H1 and H2 are called F-twins if they are isomorphic via a map φ:V1→V2 for which identities(1)Nu-V1=Nφu-V2hold for all u∈V1.We may also say that the set of verticesV1 and V2 are F-twins, since the definition above requires H1 and H2 to be the subgraphs induced by V1 and V2 and there is no possible ambiguity. The reason for the requirement that F-twins are induced subgraphs should become apparent in light of a simple example, defined by the graph G=P3∪K3. Let H1 be the P3-component of G and H2 any one of the three subgraphs of K3 isomorphic to P3. Should F-twins not be required to be induced subgraphs, H1 and H2 would be F-twins, because identities (1) hold trivially since both sides are empty for all vertices. However there exists an extra edge in K3 which makes the endvertices of H2 adjacent in G without the endvertices of H1 being so. Since the idea of the F-twin notion is to capture identical adjacency patterns, we rule out this type of situations by requiring H1 and H2 to be induced subgraphs.Note that any induced subgraph is trivially an F-twin of itself; we will say that a given induced subgraph is aproper F-twin if it has at least an F-twin different from itself (and both of them will also be said to be proper F-twins of each other). Atrivial F-twin is an induced subgraph that has no F-twin but itself.In particular, the notion above for two single distinct verticesu and v amounts to requiring that they are false twins in the sense that N(u)=N(v), as defined in Section 2.2. Just note that u∉N(u) and v∉N(v), so that (1) holds in this case if and only if N(u)=N(v).Proposition 2.
Two induced subgraphsH1 and H2 are F-twins if and only if their connected components can be matched as pairs of F-twins.Proof.
Assume first thatH1 and H2 are F-twins, and let φ denote the isomorphism arising in Definition 1. Then φ induces k isomorphisms φ1,…,φk between the connected components of H1 and H2; denote these connected components by Hi,j, with i∈{1,2},j∈{1,…,k}, and let accordingly Vi,j be the vertex set of Hi,j, so that φj:V1,j→V2,j. Then obviously (2)Vi=⋃j=1kVi,jand, provided that a vertex u (resp., φ(u)) belongs to V1,j (resp., to V2,j), it is also clear that N(u)∩V1⊆V1,j, which implies that N(u)∩V1,k=∅ if k≠j (resp., N(φ(u))∩V2⊆V2,j and then N(φ(u))∩V2,k=∅ if k≠j). This yields(3)Nu-V1,j=Nu-V1=Nφu-V2=Nφju-V2,jso that H1,j and H2,j are indeed F-twins.
The converse result proceeds in exactly the same manner and details are left to the reader.The result above is nontrivial only whenH1 and H2 are not connected. In this setting, even if H1 and H2 are proper F-twins some of their components might be trivial F-twins.Proposition 3.
IfH1 and H2 are proper F-twins, the intersection V1∩V2, if nonempty, induces a set of connected components of both H1 and H2.Proof.
Assume thatw∈V1∩V2, and let K1 and K2 be the connected components of H1 and H2 which accommodate w. Assume that K1≠K2 and, w.l.o.g., suppose that there is a vertex in K2 not belonging to K1. The set V(K2) can be described as the disjoint union of V(K1)∩V(K2) and V(K2)-V(K1) and, since K2 is connected, there must exist two adjacent vertices u and v with u∈V(K1)∩V(K2) and v∈V(K2)-V(K1). The fact that v∉V(K1) implies that v∉V1=V(H1); indeed, should it belong to V1, since it is adjacent to u∈V(K1)⊆V1, it would necessarily belong to the same connected component of u, that is, to K1, but we know that v∉V(K1). This implies that v∈N(u)-V1 and, in light of (1), it must happen that (4)v∈Nφu-V2,whoever φ(u) is. But this is impossible because v∈V(K2)⊆V2 implies that v∉N(φ(u))-V2. Hence K1=K2 and since V(K1)⊆V1 and V(K2)⊆V2 we conclude that the whole connected components K1=K2 are in the intersection H1∩H2 as we aimed to show.In particular, Proposition3 implies that distinct connected F-twins are actually disjoint.Corollary 4.
IfH1 and H2 are connected proper F-twins then V1∩V2=∅.


### 3.2. Distance-Related Properties

We know from Proposition3 that nonempty intersections of F-twins necessarily span connected components of both. On the other hand, when two F-twin subgraphs are disjoint one can easily show that they cannot be adjacent (just derive from (1) the identities N(u)∩V2=∅ for all u∈V1). A stronger statement actually holds.Proposition 5.
IfH1 and H2 are disjoint F-twins in a given graph G, then their connected components can be arranged as F-twin pairs (H1,j,H2,j) in a way such that, for every j,(i)
eitherH1,j and H2,j are connected components of G or(ii)
bothH1,j and H2,j belong to the same connected component of G and d(H1,j,H2,j)=2.Proof.
Take a connected componentH1,j of H1 and assume that there exists a vertex v∉V1=V(H1) adjacent to some u∈V1,j=V(H1,j). In light of (1), it follows that v∈N(φ(u))-V2, with V2=V(H2); this implies that v∉V2 (a property that will be used later) and also that (u,v,φ(u)) is a path. Let H2,j be the connected component of H2 accommodating φ(u): then H1,j and H2,j are isomorphic via φ; moreover, they are in the same connected component of G and, additionally, d(H1,j,H2,j)≤2. The aforementioned property that any vertex v∉V1 adjacent to u∈H1,j cannot belong to V2=V(H2) shows that, actually, d(H1,j,H2,j)=2.
The same reasoning applies to all connected components ofH1. Those for which there is no adjacent vertex away from V(H1) are by definition connected components of G. Exactly the same reasoning applies to the connected components of H2 and this completes the proof.Note also that for componentsH1,j, H2,k of H1 and H2 which do not define an F-twin pair and which are contained in the same connected component of G it holds as well that d(H1,j,H2,k)≥2 since they cannot be adjacent to each other.Corollary6 follows directly from Proposition 5. Implicit in its first claim is the fact that connected, proper F-twins which are not connected component themselves must lie in the same connected component of G. The second claim emphasizes that our notion extends the nonadjacency property of false twin vertices mentioned in Section 2.2.Corollary 6.
IfH1 and H2 are connected proper F-twins in a given graph G, then either they are connected components of G or d(H1,H2)=2. In either case, connected proper F-twins are not adjacent to each other.Another distance-related property of proper F-twins is that they arehomometric; this means that the distance multisets of both are the same [35–37]. The distance multiset of an order-k subgraph H of a connected graph G is the multiset of k2 distances (in G) between vertices of H.Lemma 7.
Assume thatH1 and H2 are disjoint F-twin subgraphs of a graph G. Let (u0,…,uk) be a vertex sequence defining a path (of length k) in G. Then (v0,…,vk), with (5)vi=φuiifui∈VH1φ-1uiifui∈VH2uiifui∉VH1∪VH2,also defines a length-k path.Proof.
The fact that all verticesvi are distinct is a direct consequence of the construction: indeed, note that φ maps V1=V(H1) onto V2=V(H2) and, conversely, φ-1 maps V2 onto V1. Since V1, V2, and V-(V1∪V2) (with V=V(G)) are pairwise disjoint sets, then the claim follows easily from the facts that φ, φ-1, and the identity are bijections and that the vertices ui are all distinct.
The other fact that needs to be proved is that the pairs{vi-1,vi} are adjacent. Since we know that disjoint F-twins are not adjacent (cf. Proposition 5 and Corollary 6) and the isomorphisms φ and φ-1 preserve adjacencies, we only need to check that vi-1 and vi are adjacent when one of them (say vi-1) belongs to one of the twins (e.g., to H2, for later notational simplicity) and vi is not in H1∪H2. This means that vi-1=φ(ui-1) with ui-1∈V1 and that vi=ui∉V1∪V2. Now use the fact that ui∈N(ui-1) because the vertices ui define a path. Additionally, since ui∉V1, from (1) we conclude that ui∈N(φ(ui-1))-V2. The identities vi=ui, vi-1=φ(ui-1), show that vi∈N(vi-1), as we aimed to prove.Proposition 8.
Assume thatH1 and H2 are disjoint F-twin subgraphs of a connected graph G, and let u∈V(H1). Then, for any other vertex u~ in G the following assertions hold:(a)
Ifu~∈V(H1), then d(u,u~)=d(φ(u),φ(u~)).(b)
Ifu~∈V(H2), then d(u,u~)=d(φ(u),φ-1(u~)).(c)
Ifu~∉V(H1)∪V(H2), then d(u,u~)=d(φ(u),u~).Proof.
The results follow in a straightforward manner from Lemma7 since the set of paths from u to u~ are in a one-to-one, length-preserving correspondence to the ones that link φ(u) to φ(u~), φ-1(u~), or u~, depending on the case. The distance identities follow as an immediate consequence simply because the distance between two vertices is the minimum length of the paths linking those vertices.Another way to state item (a) of Proposition8 is the following.Corollary 9.
Disjoint F-twin subgraphs of a connected graphG are homometric.Note also that (c) extends a known property of false twin vertices (cf. [28, Proposition 1.1]).


### 3.3. On the Classification of F-Twin Subgraphs

The F-twin notion classifies the set of isomorphic copies of any induced subgraph of a given graph, as shown below.Theorem 10.
LetH be an induced subgraph of G and denote by H the set of induced subgraphs of G which are isomorphic to H. Then the F-twin relation stated in Definition 1 is an equivalence relation in H.Proof.
The F-twin relation is obviously reflexive since we may setφ as the identity when H1=H2 in Definition 1. The fact that it is also symmetric is also easily checked, just using the inverse φ-1 of the isomorphism φ. Transitivity is also rather straightforward. Let us assume that (H1, H2) and (H2, H3) are pairs of F-twins and denote by φ and ψ the isomorphisms between H1 and H2 and between H2 and H3, respectively. One can check that the isomorphism ζ=ψ∘φ yields(6)Nu-V1=Nζu-V3for all u∈V1: indeed, this is an immediate consequence of (1) and the corresponding identity for the isomorphism ψ; that is, N(v)-V2=N(ψ(v))-V3 for all v∈V2. The identities (6) are obtained just by setting v=φ(u).Since all these classifications of induced subgraphs eventually act on the same underlying object (the graph itself), it is natural to wonder about possible interrelations between such classifications of different subgraph families. In the forthcoming subsections we provide some initial results in this direction; we explore, in particular, whether F-twin vertices may belong to larger connected F-twin structures and also provide some remarks about the F-twin classification of the family (to be denoted asH2) of subgraphs isomorphic to K2. With terminological abuse we will refer to this problem as the classification of F-twin edges (namely, we deliberately identify an edge e with the K2-graph induced by its endvertices u,v, the latter being in fact the graph {u,v},{e}): with this cautionary remark in mind the reader can think of H2 simply as the set of edges.


#### 3.3.1. F-Twin Vertices within Larger F-Twin Structures

Assume that a given graph has a class of three or more F-twin vertices. We know that they are pairwise nonadjacent and, by definition, that they share a common set of neighbors. It then follows that any two proper subsets of this class with the same number of elements (which induce two empty graphs with the same number of vertices) are themselves F-twins, since any isomorphism matching the vertices of these two empty graphs preserves the relations involved in (1). The other way round, we may think of this as an example in which two proper F-twin subgraphs contain two proper F-twin vertices (more precisely, in a way such that each vertex lies on one of the larger twins), consistently with Proposition 2. As shown below, this cannot happen, however, if such an F-twin vertex is adjacent to at least another vertex in the larger twin; this essentially means that the inclusion of pairs of F-twin vertices into pairs of larger F-twin structures is specific to singletons of these larger subgraphs.Proposition 11.
Assume thatu and φ(u) are proper F-twin vertices. If u is properly contained in a connected proper F-twin H, then the F-twin vertex φ(u) also belongs to H.Proof.
Letv be a vertex in H adjacent to u; such a vertex is guaranteed to exist because u is assumed to be properly contained in the connected subgraph H. The F-twin vertices u and φ(u) are known to verify the relation N(u)=N(φ(u)), and v∈N(u) then yields v∈N(φ(u)); for later use we recast this relation as φ(u)∈N(v).
Let us suppose thatφ(u)∉V(H) and denote by ψ the isomorphism mapping H to its F-twin ψ(H). For this F-twin relation, the identities (1) yield in particular for v∈H(7)Nv-VH=Nψv-ψVH.Now, if φ(u)∉V(H) and given the fact that φ(u)∈N(v) as shown above, we obtain φ(u)∈N(ψ(v)); as before, we recast this as ψ(v)∈N(φ(u)). But using again N(u)=N(φ(u)) we would get ψ(v)∈N(u) and this is in contradiction with Corollary 6 because u∈H and ψ(v)∈ψ(H), meaning that the connected F-twin structures H and ψ(H) would be adjacent to each other. This implies that necessarily φ(u)∈V(H) and the claim is proved.Corollary12 follows from the case in which the proper F-twin H in Proposition 11 is isomorphic to K2. In this case there is no way in which H may accommodate two distinct F-twin vertices, since they would obviously be adjacent to each other and this would contradict Corollary 6.Corollary 12.
Vertices and edges admitting proper F-twins define mutually disjoint vertex sets.We finish this section with a pretty obvious but useful remark following Corollary12.Corollary 13.
Graphs of order≤5 cannot display simultaneously proper F-twin vertices and proper F-twin edges.


#### 3.3.2. Nontrivial Vertex Set Intersections between Classes of F-Twin Edges

Obviously, in any graph the classification of F-twin vertices yields pairwise disjoint vertex classes. Things may get more involved when studying the interrelation between different F-twin classes of subgraphs not isomorphic to a single vertex. For instance, a 6-cycle (cf. the proof of Proposition14) accommodates three pairs of F-twin edges with nonempty vertex intersections among classes. In a way, such a 6-cycle is the essential structure to signal this phenomenon. We recall that H2 denotes the set of subgraphs of G isomorphic to K2.Proposition 14.
Assume that two elements ofH2 within a graph G belong to different proper F-twin classes and have a common vertex. Then G contains the cycle C6 as an induced subgraph.Proof.
LetH1 and J1 be two subgraphs in H2 (namely, isomorphic to K2) which belong to different nontrivial F-twin classes, and denote by H2 and J2 two proper F-twins of H1 and J1, respectively (with the corresponding isomorphisms to be denoted by φ and ψ). Assume that v belongs to both H1 and J1, and let u and w be the other vertex of H1 and J1, respectively. We claim that φ(u)=ψ(w) and that the subgraph induced by {u,v,w,φ(v),φ(u),ψ(v)} is a 6-cycle.
To show this, write the F-twin identity forv∈H1 as(8)Nv-VH1=Nφv-VH2.Since w∈N(v) and w∉V(H1), we derive(9)w∈Nφv.For later use, notice that this implies that φ(v)∉V(J2) (i.e., ψ(v)≠φ(v)≠ψ(w)), since otherwise there would be two adjacent vertices in J1 and J2 (namely, w and φ(v)), against Corollary 6.
Note thatv also belongs to J1 and therefore, analogously, N(v)-V(J1)=N(ψ(v))-V(J2) and, proceeding as above (use u∈N(v)-V(J1)), we get(10)u∈Nψv,and also ψ(v)∉V(H2), that is, ψ(v)≠φ(u) (we already knew that ψ(v)≠φ(v)).
Now, restate (9) as φ(v)∈N(w) and, from the fact that φ(v)∉V(J1) (to check this just note that v≠φ(v)≠w, the latter being clear in the light of (9)) and the F-twin identity for w∈V(J1),(11)Nw-VJ1=Nψw-VJ2,deriving φ(v)∈N(ψ(w)) or, equivalently,(12)ψw∈Nφv.
We show in the sequel that, indeed, it isψ(w)=φ(u). Suppose that ψ(w)≠φ(u); as shown above we have ψ(w)≠φ(v) and both conditions together would mean ψ(w)∉V(H2). Equations (8) and (12) would then yield ψ(w)∈N(v). But then v∈V(J1) and ψ(w)∈V(J2) would be adjacent to each other. We conclude that necessarily ψ(w)=φ(u), as claimed.
The fact thatu,v,w,φ(v),φ(u)=ψ(w),ψ(v) yield a 6-cycle follows from the adjacency relations defined by H1, J1, (9), H2, J2, and (10), respectively. It only remains to show that this cycle is actually induced by these vertices, namely, that there are no additional adjacencies among them. Apart from the six edges defining the aforementioned cycle, there are other nine possible links between the six vertices listed above; seven of these are ruled out by Corollary 6 (namely, those connecting u,v with φ(u),φ(v), since both pairs define the F-twins H1, H2, resp., and v,w with ψ(v), ψ(w), which define J1 and J2; note that φ(u)=ψ(w) and therefore the pairs {v,φ(u)} and {v,ψ(w)} are the same). The two remaining pairs are {u,w} and {φ(v),ψ(v)}; consider the first one and note that u∉V(J1), so that the assumption u∈N(w) would imply that u∈N(ψ(w)) in light of (11), but this is impossible because u∈V(H1) and ψ(w)=φ(u)∈V(H2) cannot be adjacent to each other. The fact that φ(v) cannot be adjacent to ψ(v) can be checked in the same terms, and the proof is complete.We close this section by saying that the classification of F-twin structures (beyond F-twin vertices) possibly defines other mathematical problems of interest. This is a topic for future study.


## 3.1. Definition and Elementary Properties

Definition 1.
LetH1 and H2 be two induced subgraphs of a graph G. Denote by Vi the vertex set of Hi. H1 and H2 are called F-twins if they are isomorphic via a map φ:V1→V2 for which identities(1)Nu-V1=Nφu-V2hold for all u∈V1.We may also say that the set of verticesV1 and V2 are F-twins, since the definition above requires H1 and H2 to be the subgraphs induced by V1 and V2 and there is no possible ambiguity. The reason for the requirement that F-twins are induced subgraphs should become apparent in light of a simple example, defined by the graph G=P3∪K3. Let H1 be the P3-component of G and H2 any one of the three subgraphs of K3 isomorphic to P3. Should F-twins not be required to be induced subgraphs, H1 and H2 would be F-twins, because identities (1) hold trivially since both sides are empty for all vertices. However there exists an extra edge in K3 which makes the endvertices of H2 adjacent in G without the endvertices of H1 being so. Since the idea of the F-twin notion is to capture identical adjacency patterns, we rule out this type of situations by requiring H1 and H2 to be induced subgraphs.Note that any induced subgraph is trivially an F-twin of itself; we will say that a given induced subgraph is aproper F-twin if it has at least an F-twin different from itself (and both of them will also be said to be proper F-twins of each other). Atrivial F-twin is an induced subgraph that has no F-twin but itself.In particular, the notion above for two single distinct verticesu and v amounts to requiring that they are false twins in the sense that N(u)=N(v), as defined in Section 2.2. Just note that u∉N(u) and v∉N(v), so that (1) holds in this case if and only if N(u)=N(v).Proposition 2.
Two induced subgraphsH1 and H2 are F-twins if and only if their connected components can be matched as pairs of F-twins.Proof.
Assume first thatH1 and H2 are F-twins, and let φ denote the isomorphism arising in Definition 1. Then φ induces k isomorphisms φ1,…,φk between the connected components of H1 and H2; denote these connected components by Hi,j, with i∈{1,2},j∈{1,…,k}, and let accordingly Vi,j be the vertex set of Hi,j, so that φj:V1,j→V2,j. Then obviously (2)Vi=⋃j=1kVi,jand, provided that a vertex u (resp., φ(u)) belongs to V1,j (resp., to V2,j), it is also clear that N(u)∩V1⊆V1,j, which implies that N(u)∩V1,k=∅ if k≠j (resp., N(φ(u))∩V2⊆V2,j and then N(φ(u))∩V2,k=∅ if k≠j). This yields(3)Nu-V1,j=Nu-V1=Nφu-V2=Nφju-V2,jso that H1,j and H2,j are indeed F-twins.
The converse result proceeds in exactly the same manner and details are left to the reader.The result above is nontrivial only whenH1 and H2 are not connected. In this setting, even if H1 and H2 are proper F-twins some of their components might be trivial F-twins.Proposition 3.
IfH1 and H2 are proper F-twins, the intersection V1∩V2, if nonempty, induces a set of connected components of both H1 and H2.Proof.
Assume thatw∈V1∩V2, and let K1 and K2 be the connected components of H1 and H2 which accommodate w. Assume that K1≠K2 and, w.l.o.g., suppose that there is a vertex in K2 not belonging to K1. The set V(K2) can be described as the disjoint union of V(K1)∩V(K2) and V(K2)-V(K1) and, since K2 is connected, there must exist two adjacent vertices u and v with u∈V(K1)∩V(K2) and v∈V(K2)-V(K1). The fact that v∉V(K1) implies that v∉V1=V(H1); indeed, should it belong to V1, since it is adjacent to u∈V(K1)⊆V1, it would necessarily belong to the same connected component of u, that is, to K1, but we know that v∉V(K1). This implies that v∈N(u)-V1 and, in light of (1), it must happen that (4)v∈Nφu-V2,whoever φ(u) is. But this is impossible because v∈V(K2)⊆V2 implies that v∉N(φ(u))-V2. Hence K1=K2 and since V(K1)⊆V1 and V(K2)⊆V2 we conclude that the whole connected components K1=K2 are in the intersection H1∩H2 as we aimed to show.In particular, Proposition3 implies that distinct connected F-twins are actually disjoint.Corollary 4.
IfH1 and H2 are connected proper F-twins then V1∩V2=∅.


## 3.2. Distance-Related Properties

We know from Proposition3 that nonempty intersections of F-twins necessarily span connected components of both. On the other hand, when two F-twin subgraphs are disjoint one can easily show that they cannot be adjacent (just derive from (1) the identities N(u)∩V2=∅ for all u∈V1). A stronger statement actually holds.Proposition 5.
IfH1 and H2 are disjoint F-twins in a given graph G, then their connected components can be arranged as F-twin pairs (H1,j,H2,j) in a way such that, for every j,(i)
eitherH1,j and H2,j are connected components of G or(ii)
bothH1,j and H2,j belong to the same connected component of G and d(H1,j,H2,j)=2.Proof.
Take a connected componentH1,j of H1 and assume that there exists a vertex v∉V1=V(H1) adjacent to some u∈V1,j=V(H1,j). In light of (1), it follows that v∈N(φ(u))-V2, with V2=V(H2); this implies that v∉V2 (a property that will be used later) and also that (u,v,φ(u)) is a path. Let H2,j be the connected component of H2 accommodating φ(u): then H1,j and H2,j are isomorphic via φ; moreover, they are in the same connected component of G and, additionally, d(H1,j,H2,j)≤2. The aforementioned property that any vertex v∉V1 adjacent to u∈H1,j cannot belong to V2=V(H2) shows that, actually, d(H1,j,H2,j)=2.
The same reasoning applies to all connected components ofH1. Those for which there is no adjacent vertex away from V(H1) are by definition connected components of G. Exactly the same reasoning applies to the connected components of H2 and this completes the proof.Note also that for componentsH1,j, H2,k of H1 and H2 which do not define an F-twin pair and which are contained in the same connected component of G it holds as well that d(H1,j,H2,k)≥2 since they cannot be adjacent to each other.Corollary6 follows directly from Proposition 5. Implicit in its first claim is the fact that connected, proper F-twins which are not connected component themselves must lie in the same connected component of G. The second claim emphasizes that our notion extends the nonadjacency property of false twin vertices mentioned in Section 2.2.Corollary 6.
IfH1 and H2 are connected proper F-twins in a given graph G, then either they are connected components of G or d(H1,H2)=2. In either case, connected proper F-twins are not adjacent to each other.Another distance-related property of proper F-twins is that they arehomometric; this means that the distance multisets of both are the same [35–37]. The distance multiset of an order-k subgraph H of a connected graph G is the multiset of k2 distances (in G) between vertices of H.Lemma 7.
Assume thatH1 and H2 are disjoint F-twin subgraphs of a graph G. Let (u0,…,uk) be a vertex sequence defining a path (of length k) in G. Then (v0,…,vk), with (5)vi=φuiifui∈VH1φ-1uiifui∈VH2uiifui∉VH1∪VH2,also defines a length-k path.Proof.
The fact that all verticesvi are distinct is a direct consequence of the construction: indeed, note that φ maps V1=V(H1) onto V2=V(H2) and, conversely, φ-1 maps V2 onto V1. Since V1, V2, and V-(V1∪V2) (with V=V(G)) are pairwise disjoint sets, then the claim follows easily from the facts that φ, φ-1, and the identity are bijections and that the vertices ui are all distinct.
The other fact that needs to be proved is that the pairs{vi-1,vi} are adjacent. Since we know that disjoint F-twins are not adjacent (cf. Proposition 5 and Corollary 6) and the isomorphisms φ and φ-1 preserve adjacencies, we only need to check that vi-1 and vi are adjacent when one of them (say vi-1) belongs to one of the twins (e.g., to H2, for later notational simplicity) and vi is not in H1∪H2. This means that vi-1=φ(ui-1) with ui-1∈V1 and that vi=ui∉V1∪V2. Now use the fact that ui∈N(ui-1) because the vertices ui define a path. Additionally, since ui∉V1, from (1) we conclude that ui∈N(φ(ui-1))-V2. The identities vi=ui, vi-1=φ(ui-1), show that vi∈N(vi-1), as we aimed to prove.Proposition 8.
Assume thatH1 and H2 are disjoint F-twin subgraphs of a connected graph G, and let u∈V(H1). Then, for any other vertex u~ in G the following assertions hold:(a)
Ifu~∈V(H1), then d(u,u~)=d(φ(u),φ(u~)).(b)
Ifu~∈V(H2), then d(u,u~)=d(φ(u),φ-1(u~)).(c)
Ifu~∉V(H1)∪V(H2), then d(u,u~)=d(φ(u),u~).Proof.
The results follow in a straightforward manner from Lemma7 since the set of paths from u to u~ are in a one-to-one, length-preserving correspondence to the ones that link φ(u) to φ(u~), φ-1(u~), or u~, depending on the case. The distance identities follow as an immediate consequence simply because the distance between two vertices is the minimum length of the paths linking those vertices.Another way to state item (a) of Proposition8 is the following.Corollary 9.
Disjoint F-twin subgraphs of a connected graphG are homometric.Note also that (c) extends a known property of false twin vertices (cf. [28, Proposition 1.1]).


## 3.3. On the Classification of F-Twin Subgraphs

The F-twin notion classifies the set of isomorphic copies of any induced subgraph of a given graph, as shown below.Theorem 10.
LetH be an induced subgraph of G and denote by H the set of induced subgraphs of G which are isomorphic to H. Then the F-twin relation stated in Definition 1 is an equivalence relation in H.Proof.
The F-twin relation is obviously reflexive since we may setφ as the identity when H1=H2 in Definition 1. The fact that it is also symmetric is also easily checked, just using the inverse φ-1 of the isomorphism φ. Transitivity is also rather straightforward. Let us assume that (H1, H2) and (H2, H3) are pairs of F-twins and denote by φ and ψ the isomorphisms between H1 and H2 and between H2 and H3, respectively. One can check that the isomorphism ζ=ψ∘φ yields(6)Nu-V1=Nζu-V3for all u∈V1: indeed, this is an immediate consequence of (1) and the corresponding identity for the isomorphism ψ; that is, N(v)-V2=N(ψ(v))-V3 for all v∈V2. The identities (6) are obtained just by setting v=φ(u).Since all these classifications of induced subgraphs eventually act on the same underlying object (the graph itself), it is natural to wonder about possible interrelations between such classifications of different subgraph families. In the forthcoming subsections we provide some initial results in this direction; we explore, in particular, whether F-twin vertices may belong to larger connected F-twin structures and also provide some remarks about the F-twin classification of the family (to be denoted asH2) of subgraphs isomorphic to K2. With terminological abuse we will refer to this problem as the classification of F-twin edges (namely, we deliberately identify an edge e with the K2-graph induced by its endvertices u,v, the latter being in fact the graph {u,v},{e}): with this cautionary remark in mind the reader can think of H2 simply as the set of edges.


### 3.3.1. F-Twin Vertices within Larger F-Twin Structures

Assume that a given graph has a class of three or more F-twin vertices. We know that they are pairwise nonadjacent and, by definition, that they share a common set of neighbors. It then follows that any two proper subsets of this class with the same number of elements (which induce two empty graphs with the same number of vertices) are themselves F-twins, since any isomorphism matching the vertices of these two empty graphs preserves the relations involved in (1). The other way round, we may think of this as an example in which two proper F-twin subgraphs contain two proper F-twin vertices (more precisely, in a way such that each vertex lies on one of the larger twins), consistently with Proposition 2. As shown below, this cannot happen, however, if such an F-twin vertex is adjacent to at least another vertex in the larger twin; this essentially means that the inclusion of pairs of F-twin vertices into pairs of larger F-twin structures is specific to singletons of these larger subgraphs.Proposition 11.
Assume thatu and φ(u) are proper F-twin vertices. If u is properly contained in a connected proper F-twin H, then the F-twin vertex φ(u) also belongs to H.Proof.
Letv be a vertex in H adjacent to u; such a vertex is guaranteed to exist because u is assumed to be properly contained in the connected subgraph H. The F-twin vertices u and φ(u) are known to verify the relation N(u)=N(φ(u)), and v∈N(u) then yields v∈N(φ(u)); for later use we recast this relation as φ(u)∈N(v).
Let us suppose thatφ(u)∉V(H) and denote by ψ the isomorphism mapping H to its F-twin ψ(H). For this F-twin relation, the identities (1) yield in particular for v∈H(7)Nv-VH=Nψv-ψVH.Now, if φ(u)∉V(H) and given the fact that φ(u)∈N(v) as shown above, we obtain φ(u)∈N(ψ(v)); as before, we recast this as ψ(v)∈N(φ(u)). But using again N(u)=N(φ(u)) we would get ψ(v)∈N(u) and this is in contradiction with Corollary 6 because u∈H and ψ(v)∈ψ(H), meaning that the connected F-twin structures H and ψ(H) would be adjacent to each other. This implies that necessarily φ(u)∈V(H) and the claim is proved.Corollary12 follows from the case in which the proper F-twin H in Proposition 11 is isomorphic to K2. In this case there is no way in which H may accommodate two distinct F-twin vertices, since they would obviously be adjacent to each other and this would contradict Corollary 6.Corollary 12.
Vertices and edges admitting proper F-twins define mutually disjoint vertex sets.We finish this section with a pretty obvious but useful remark following Corollary12.Corollary 13.
Graphs of order≤5 cannot display simultaneously proper F-twin vertices and proper F-twin edges.


### 3.3.2. Nontrivial Vertex Set Intersections between Classes of F-Twin Edges

Obviously, in any graph the classification of F-twin vertices yields pairwise disjoint vertex classes. Things may get more involved when studying the interrelation between different F-twin classes of subgraphs not isomorphic to a single vertex. For instance, a 6-cycle (cf. the proof of Proposition14) accommodates three pairs of F-twin edges with nonempty vertex intersections among classes. In a way, such a 6-cycle is the essential structure to signal this phenomenon. We recall that H2 denotes the set of subgraphs of G isomorphic to K2.Proposition 14.
Assume that two elements ofH2 within a graph G belong to different proper F-twin classes and have a common vertex. Then G contains the cycle C6 as an induced subgraph.Proof.
LetH1 and J1 be two subgraphs in H2 (namely, isomorphic to K2) which belong to different nontrivial F-twin classes, and denote by H2 and J2 two proper F-twins of H1 and J1, respectively (with the corresponding isomorphisms to be denoted by φ and ψ). Assume that v belongs to both H1 and J1, and let u and w be the other vertex of H1 and J1, respectively. We claim that φ(u)=ψ(w) and that the subgraph induced by {u,v,w,φ(v),φ(u),ψ(v)} is a 6-cycle.
To show this, write the F-twin identity forv∈H1 as(8)Nv-VH1=Nφv-VH2.Since w∈N(v) and w∉V(H1), we derive(9)w∈Nφv.For later use, notice that this implies that φ(v)∉V(J2) (i.e., ψ(v)≠φ(v)≠ψ(w)), since otherwise there would be two adjacent vertices in J1 and J2 (namely, w and φ(v)), against Corollary 6.
Note thatv also belongs to J1 and therefore, analogously, N(v)-V(J1)=N(ψ(v))-V(J2) and, proceeding as above (use u∈N(v)-V(J1)), we get(10)u∈Nψv,and also ψ(v)∉V(H2), that is, ψ(v)≠φ(u) (we already knew that ψ(v)≠φ(v)).
Now, restate (9) as φ(v)∈N(w) and, from the fact that φ(v)∉V(J1) (to check this just note that v≠φ(v)≠w, the latter being clear in the light of (9)) and the F-twin identity for w∈V(J1),(11)Nw-VJ1=Nψw-VJ2,deriving φ(v)∈N(ψ(w)) or, equivalently,(12)ψw∈Nφv.
We show in the sequel that, indeed, it isψ(w)=φ(u). Suppose that ψ(w)≠φ(u); as shown above we have ψ(w)≠φ(v) and both conditions together would mean ψ(w)∉V(H2). Equations (8) and (12) would then yield ψ(w)∈N(v). But then v∈V(J1) and ψ(w)∈V(J2) would be adjacent to each other. We conclude that necessarily ψ(w)=φ(u), as claimed.
The fact thatu,v,w,φ(v),φ(u)=ψ(w),ψ(v) yield a 6-cycle follows from the adjacency relations defined by H1, J1, (9), H2, J2, and (10), respectively. It only remains to show that this cycle is actually induced by these vertices, namely, that there are no additional adjacencies among them. Apart from the six edges defining the aforementioned cycle, there are other nine possible links between the six vertices listed above; seven of these are ruled out by Corollary 6 (namely, those connecting u,v with φ(u),φ(v), since both pairs define the F-twins H1, H2, resp., and v,w with ψ(v), ψ(w), which define J1 and J2; note that φ(u)=ψ(w) and therefore the pairs {v,φ(u)} and {v,ψ(w)} are the same). The two remaining pairs are {u,w} and {φ(v),ψ(v)}; consider the first one and note that u∉V(J1), so that the assumption u∈N(w) would imply that u∈N(ψ(w)) in light of (11), but this is impossible because u∈V(H1) and ψ(w)=φ(u)∈V(H2) cannot be adjacent to each other. The fact that φ(v) cannot be adjacent to ψ(v) can be checked in the same terms, and the proof is complete.We close this section by saying that the classification of F-twin structures (beyond F-twin vertices) possibly defines other mathematical problems of interest. This is a topic for future study.


## 3.3.1. F-Twin Vertices within Larger F-Twin Structures

Assume that a given graph has a class of three or more F-twin vertices. We know that they are pairwise nonadjacent and, by definition, that they share a common set of neighbors. It then follows that any two proper subsets of this class with the same number of elements (which induce two empty graphs with the same number of vertices) are themselves F-twins, since any isomorphism matching the vertices of these two empty graphs preserves the relations involved in (1). The other way round, we may think of this as an example in which two proper F-twin subgraphs contain two proper F-twin vertices (more precisely, in a way such that each vertex lies on one of the larger twins), consistently with Proposition 2. As shown below, this cannot happen, however, if such an F-twin vertex is adjacent to at least another vertex in the larger twin; this essentially means that the inclusion of pairs of F-twin vertices into pairs of larger F-twin structures is specific to singletons of these larger subgraphs.Proposition 11.
Assume thatu and φ(u) are proper F-twin vertices. If u is properly contained in a connected proper F-twin H, then the F-twin vertex φ(u) also belongs to H.Proof.
Letv be a vertex in H adjacent to u; such a vertex is guaranteed to exist because u is assumed to be properly contained in the connected subgraph H. The F-twin vertices u and φ(u) are known to verify the relation N(u)=N(φ(u)), and v∈N(u) then yields v∈N(φ(u)); for later use we recast this relation as φ(u)∈N(v).
Let us suppose thatφ(u)∉V(H) and denote by ψ the isomorphism mapping H to its F-twin ψ(H). For this F-twin relation, the identities (1) yield in particular for v∈H(7)Nv-VH=Nψv-ψVH.Now, if φ(u)∉V(H) and given the fact that φ(u)∈N(v) as shown above, we obtain φ(u)∈N(ψ(v)); as before, we recast this as ψ(v)∈N(φ(u)). But using again N(u)=N(φ(u)) we would get ψ(v)∈N(u) and this is in contradiction with Corollary 6 because u∈H and ψ(v)∈ψ(H), meaning that the connected F-twin structures H and ψ(H) would be adjacent to each other. This implies that necessarily φ(u)∈V(H) and the claim is proved.Corollary12 follows from the case in which the proper F-twin H in Proposition 11 is isomorphic to K2. In this case there is no way in which H may accommodate two distinct F-twin vertices, since they would obviously be adjacent to each other and this would contradict Corollary 6.Corollary 12.
Vertices and edges admitting proper F-twins define mutually disjoint vertex sets.We finish this section with a pretty obvious but useful remark following Corollary12.Corollary 13.
Graphs of order≤5 cannot display simultaneously proper F-twin vertices and proper F-twin edges.


## 3.3.2. Nontrivial Vertex Set Intersections between Classes of F-Twin Edges

Obviously, in any graph the classification of F-twin vertices yields pairwise disjoint vertex classes. Things may get more involved when studying the interrelation between different F-twin classes of subgraphs not isomorphic to a single vertex. For instance, a 6-cycle (cf. the proof of Proposition14) accommodates three pairs of F-twin edges with nonempty vertex intersections among classes. In a way, such a 6-cycle is the essential structure to signal this phenomenon. We recall that H2 denotes the set of subgraphs of G isomorphic to K2.Proposition 14.
Assume that two elements ofH2 within a graph G belong to different proper F-twin classes and have a common vertex. Then G contains the cycle C6 as an induced subgraph.Proof.
LetH1 and J1 be two subgraphs in H2 (namely, isomorphic to K2) which belong to different nontrivial F-twin classes, and denote by H2 and J2 two proper F-twins of H1 and J1, respectively (with the corresponding isomorphisms to be denoted by φ and ψ). Assume that v belongs to both H1 and J1, and let u and w be the other vertex of H1 and J1, respectively. We claim that φ(u)=ψ(w) and that the subgraph induced by {u,v,w,φ(v),φ(u),ψ(v)} is a 6-cycle.
To show this, write the F-twin identity forv∈H1 as(8)Nv-VH1=Nφv-VH2.Since w∈N(v) and w∉V(H1), we derive(9)w∈Nφv.For later use, notice that this implies that φ(v)∉V(J2) (i.e., ψ(v)≠φ(v)≠ψ(w)), since otherwise there would be two adjacent vertices in J1 and J2 (namely, w and φ(v)), against Corollary 6.
Note thatv also belongs to J1 and therefore, analogously, N(v)-V(J1)=N(ψ(v))-V(J2) and, proceeding as above (use u∈N(v)-V(J1)), we get(10)u∈Nψv,and also ψ(v)∉V(H2), that is, ψ(v)≠φ(u) (we already knew that ψ(v)≠φ(v)).
Now, restate (9) as φ(v)∈N(w) and, from the fact that φ(v)∉V(J1) (to check this just note that v≠φ(v)≠w, the latter being clear in the light of (9)) and the F-twin identity for w∈V(J1),(11)Nw-VJ1=Nψw-VJ2,deriving φ(v)∈N(ψ(w)) or, equivalently,(12)ψw∈Nφv.
We show in the sequel that, indeed, it isψ(w)=φ(u). Suppose that ψ(w)≠φ(u); as shown above we have ψ(w)≠φ(v) and both conditions together would mean ψ(w)∉V(H2). Equations (8) and (12) would then yield ψ(w)∈N(v). But then v∈V(J1) and ψ(w)∈V(J2) would be adjacent to each other. We conclude that necessarily ψ(w)=φ(u), as claimed.
The fact thatu,v,w,φ(v),φ(u)=ψ(w),ψ(v) yield a 6-cycle follows from the adjacency relations defined by H1, J1, (9), H2, J2, and (10), respectively. It only remains to show that this cycle is actually induced by these vertices, namely, that there are no additional adjacencies among them. Apart from the six edges defining the aforementioned cycle, there are other nine possible links between the six vertices listed above; seven of these are ruled out by Corollary 6 (namely, those connecting u,v with φ(u),φ(v), since both pairs define the F-twins H1, H2, resp., and v,w with ψ(v), ψ(w), which define J1 and J2; note that φ(u)=ψ(w) and therefore the pairs {v,φ(u)} and {v,ψ(w)} are the same). The two remaining pairs are {u,w} and {φ(v),ψ(v)}; consider the first one and note that u∉V(J1), so that the assumption u∈N(w) would imply that u∈N(ψ(w)) in light of (11), but this is impossible because u∈V(H1) and ψ(w)=φ(u)∈V(H2) cannot be adjacent to each other. The fact that φ(v) cannot be adjacent to ψ(v) can be checked in the same terms, and the proof is complete.We close this section by saying that the classification of F-twin structures (beyond F-twin vertices) possibly defines other mathematical problems of interest. This is a topic for future study.


## 4. T-Twins

We present in this section the dual concept of T-twin subgraphs, which extends the notion of true twin vertices discussed in Section2.2. This section will be briefer than the previous one; we just aim at providing a complete framework extending to arbitrary subgraphs the idea behind false and true twin vertices. We will also show (Theorem 18) that in a precise sense the notions supporting F-twins and T-twins are dual to each other, again extending a known property of false and true twin vertices [28, 34].Definition 15.
LetH1 and H2 be two induced subgraphs of a graph G and denote by Vi the vertex set of Hi. H1 and H2 are called T-twins if they are isomorphic via a map φ:V1→V2 for which the identities(13)Nu∪V1=Nφu∪V2hold for all u∈V1.Again this extends the notion of true twin vertices introduced in Section2.2, which are defined by the identities N[u]=N[v]; that is, N(u)∪{u}=N(v)∪{v}, consistently with (13).As in the F-twin case, we use the termproper T-twins for distinct T-twins.Proposition 16.
LetH1 and H2 be T-twins. Then V1∩V2, V1-V2, and V2-V1 are fully connected to each other.Proof.
From (13) it is clear that all vertices in V2-V1 belong to N(u) for all u∈V1, and this means that V2-V1 is fully connected to V1 (in particular, to V1-V2). Analogously, V1-V2 is fully connected to V2. Using both properties together we conclude that the intersection V1∩V2 is fully connected to both V1-V2 and V2-V1 and the claim is proved.Corollary 17.
IfH1 and H2 are disjoint T-twins, then V1 is fully connected to V2.The following result gives a precise meaning to the claim that the F-twin and T-twin notions are dual to each other.Theorem 18.
Two induced subgraphsH1 and H2 of a given graph G are T-twins (resp., F-twins) if and only if H1¯ and H2¯ are F-twins (resp., T-twins) in G¯.Proof.
The reader can check in advance that ifH is an induced subgraph of G, then H¯ is an induced subgraph of G¯. Assume now that H1 and H2 are T-twins, and let φ be the isomorphism arising in Definition 15; one can see that φ is also an isomorphism between the complements H1¯ and H2¯. Denoting by N¯(u) the neighborhood of u in G¯, we need to show that the identities(14)N¯u-V1=N¯φu-V2hold in G¯ for all u in V1=V(H1¯)=V(H1). We use the fact that (15)N¯u=VG-Nu∪u,N¯φu=VG-Nφu∪φuby definition of the complement. These relations yield(16)N¯u-V1=VG-Nu∪u∪V1=VG-Nu∪V1(where we have used u∈V1) and, analogously,(17)N¯φu-V2=VG-Nφu∪φu∪V2=VG-Nφu∪V2.The relations depicted in (14) then follow from (16) and (17) because H1 and H2 are T-twins, which means that N(u)∪V1=N(φ(u))∪V2.
Both the case in whichH1 and H2 are F-twins and the converse results proceed in the same manner and details are left to the reader.At first sight, a reader might be slightly surprised with Theorem18 since T-twins may have nonempty intersections in the vertex sets and (connected proper) F-twins seemingly not, as stated in Corollary 4. But note that the latter holds as a consequence of Proposition 3 forconnected F-twins: now assume that V1∩V2≠∅ for (even possibly connected) T-twins H1 and H2. From Proposition 16 it follows that V1∩V2 is fully connected to both V1-V2 and V2-V1, so that, in the complementary (F-twin) subgraphs H1¯ and H2¯, V1∩V2 is isolated from both V1-V2 and V2-V1. This means that V1∩V2 induces a set of connected components of both H1¯ and H2¯ and there is no contradiction with Proposition 3.Finally, we mention that the T-twin relation also induces a classification in the familiesH of isomorphic copies of induced subgraphs H. Details are entirely analogous to those in Theorem 10 and are left to the reader.


## 5. Core-Semiperiphery-Periphery Structures

We take now a look back at Section2.3; specifically, we provide here a definition of core-semiperiphery-periphery (CSP) structures extending the ideas presented there and reducing the number of structures via the exclusion of twin substructures, according to the notions introduced in Sections 3 and 4. We will work in this section with 3-partitioned graphs (cf. Section 2.1) and we make the remark that the F-twin and T-twin notions introduced in Definitions 1 and 15 apply also in this context just by assuming that the isomorphism φ is now an isomorphism of partitioned graphs, namely, that it leaves the classes invariant (it maps core vertices into core vertices, etc.).


### 5.1. A Parameterized Definition of Core-Semiperiphery-Periphery Structures

We first note that the condition depicted in item (i) in Section2.3, defining core vertices, may be recast as the requirement that all of them have eccentricity one. This approach is intimately related to thecloseness centrality notion, widely used in network theory [34, 38]. This idea has been previously used in the definition of core vertices within core-periphery structures [10, 11] and paves the way for the definition presented below.Definition 19.
A core-semiperiphery-periphery structure is a 3-partitioned connected graph with the following (nonempty) vertex classes:(i)
Core vertices, with eccentricity not greater than two(ii)
Semiperiphery vertices, adjacent (at least) to a pair of nonadjacent vertices from the other two classes(iii)
Periphery vertices, with degree one.
Moreover, the graph is required not to have proper T-twin core vertices or proper F-twin semiperiphery-periphery subgraphs.Here, semiperiphery vertices are simply required to act as intermediaries between (at least) a core and a periphery, whereas for the latter we impose a minimal connection to the rest of the network, in a way which implies in particular that periphery vertices are isolated from each other (cf. item (ii) in Section2.3). Note that the requirements depicted for each class may be satisfied by vertices from other classes: for example, a core may have degree one or connect a pair of (nonadjacent) semiperiphery and periphery vertices, whereas a semiperiphery or a periphery vertex might well have eccentricity not greater than two. It is pretty clear, however, that the requirements in items (ii) and (iii) are mutually exclusive.It is worth emphasizing that this approach admits further extensions; on the one hand we may consider the maximum core eccentricity (mce) and maximum periphery degree (mpd) as parameters which in our present framework are fixed to the values two and one in (i) and (iii), respectively. Allowing these parameters to take on higher values may well lead to other structures of interest. Additionally, in a setting with mce≥3 we might also define structures with more than three (ranked) classes, by distinguishing several semiperiphery layers defined by vertices which are adjacent to vertex pairs coming from a higher-rank and a lower-rank class (examples of networks with four classes can be found in [16, 17]). These ideas define tentative lines for future research.The twin-free conditions stated at the end of Definition19, supported on the ideas discussed in Sections 3 and 4, are the key element to reduce the seemingly large number of CSP structures. As already indicated in the Introduction and in Section 2.3, the core should be thought as a set of heavily interconnected vertices, amounting to a fully connected set in idealized cases; for this reason the true twin notion for vertices is enough to reduce the eventual number of core subgraphs within core-semiperiphery-periphery structures. On the other hand, the F-twin concept for the semiperiphery-periphery subgraph arises as a natural extension of the false twin notion for periphery vertices discussed in Section 2.3, allowing one to reduce the number of semiperiphery-periphery subgraphs as well. Note also that the nonadjacency property stated in Corollary 6 captures the fact that twin semiperiphery-periphery substructures to be reduced should be somehow independent, being related only through the core vertices; in other words, if two (or more) semiperiphery vertices are adjacent then it is natural to consider them as part of the same substructure.


### 5.2. Decomposition of CSP Structures

Definition19 allows for an explicit description of core-semiperiphery-periphery structures, as detailed below.Theorem 20.
Core-semiperiphery-periphery structures meeting Definition19 admit the decomposition described in the sequel.(1)
The core subgraphC is a join C0+C1, where (i) C0 is a complete graph Kn0 and (ii) C1 is any graph of order n1 without T-twin vertices.(2)
The core-semiperiphery subgraph is a joinC+S, where C has the form described above and S is any graph or order ns without F-twin subgraphs.(3)
The periphery subgraphP is an empty graph of order np=n0+ns. Periphery vertices are leaves attached in a one-to-one basis either to a vertex from C0 or from S.
The ordersnc=n0+n1, ns, and np do not vanish, but either n0 or n1 may do.Proof.
Note in advance that the splitting of core vertices in two groupsC0 and C1 is defined from the fact that those in C0 are connected to a periphery vertex, whereas those in C1 are not, as stated in item 3. In this regard, it is obvious that periphery vertices are only connected either to a core (in C0) or to a semiperiphery vertex because of the degree one condition stated in item (iii) of Definition 19; notice that a single K2 consisting of two peripheries is ruled out by the requirement that the graph has at least one core and one semiperiphery vertex. Conversely, semiperiphery vertices are necessarily connected to a single periphery (in addition to cores and, possibly, other semiperipheries), since two or more peripheries eventually connected to the same semiperiphery vertex would be false twins. For the same reason, a core vertex in C0 is attached to one periphery (again, in addition to connections to other cores and to semiperipheries). These properties fully describe the structure of the periphery subgraph P and will be used throughout the rest of the proof.
Regarding the structure of the core subgraph,C0 is a complete graph (maybe the null one K0) and, moreover, it defines a join with (i.e., it is fully connected to) C1, if nonempty, because of the eccentricity requirement for core vertices. Indeed, suppose that there is a pair of nonadjacent core vertices, at least one of which is adjacent to a periphery (i.e., at least one of which is in C0): the distance of this periphery vertex to the other core in that pair would be at least three, against the assumption that the maximum eccentricity of core vertices is two as stated in item (i) of Definition 19.
The core and the semiperiphery are fully connected as well. Again, assuming the contrary, the distance between such a core and the periphery vertex adjacent to that semiperiphery would be greater than two, against the aforementioned eccentricity requirement.
It remains to show that the exclusion of twin structures in Definition19 is equivalent to the absence of the corresponding twin structures in the core or semiperiphery subgraph, respectively, in the terms stated in this Theorem. Regarding core vertices, note first that C0 may never include T-twins (meant in the full graph) since the peripheries attached to these cores are adjacent only to one core and, therefore, these peripheries necessarily make a difference in the neighborhoods of the corresponding cores; for the same reason, cores in C0 and in C1 may never be T-twins in the full graph. Additionally, the absence of T-twins in C1 can be equivalently checked in the full graph or in the core subgraph because of the fact that cores in C1 are not adjacent to any peripheries and, on the contrary, fully connected to both C0 and S; this means that the neighborhoods of two C1-cores in the full graph differ if and only if these core vertices have different neighbors within C1.
Concerning the equivalence between F-twin structures, let us first assume that two subgraphsH1 and H2 within the semiperiphery-periphery subgraph are F-twins in the full graph, and let φ denote the corresponding isomorphism, so that (1) holds for all u∈V1=V(H1). Let φs stand for the restriction of this isomorphism to H1∩S, and denote V1s=V1∩V(S) and V2s=V2∩V(S). From (1) we get (18)Nu-V1∩VS=Nφu-V2∩VS,an identity that can be recast as(19)Nsu-V1s=Nsφu-V2sby making use of the property (A-B)∩C=A∩C-B∩C for arbitrary sets A, B, and C (here Ns(u) denotes N(u)∩V(S)). By noting that (19) holds for all u∈V1s and that φ(u)=φs(u) for vertices in V1s, it follows that H1∩S and H2∩S are F-twins as subgraphs of S via the restricted isomorphism φs, as we aimed to show.
Conversely, letH1s and H2s be F-twin structures as subgraphs of S, and denote by φs the corresponding isomorphism. Denote by V1s and V2s the vertex sets of H1s and H2s, respectively. Let H1 (resp., H2) be the subgraph induced in the full graph by the vertices of V1s (resp., V2s) and their adjacent peripheries, and write as V1 (resp., V2) the vertex set of H1 (resp., H2). Now, for every u∈V(S) write as p(u) the unique periphery vertex attached to u in the full graph and, conversely, for every u∈P let s(u) be the unique semiperiphery vertex adjacent to u. With this notation we extend the isomorphism φs to the whole of H1 by setting (20)φu=φsuifu∈H1∩Spφssuifu∈H1∩P.We claim that φ makes H1 and H2 F-twin subgraphs in the full graph. First, note that by construction (19) is met for all u∈H1∩S, and then(21)VC∪Nsu-V1s=VC∪Nsφu-V2sholds because V(C)∩V1s=V(C)∩V2s=∅; additionally, since V1-V1s and V2-V2s are in the periphery, we may rewrite (21) as(22)VC∪Nsu-V1=VC∪Nsφu-V2.Moreover, using the fact that p(u)∈V1,p(φ(u))∈V2, (22) yields(23)VC∪Nsu∪pu-V1=VC∪Nsφu∪pφu-V2.In light of the join structure proved above for C+S we have N(u)=V(C)∪Ns(u)∪{p(u)} and N(φ(u))=V(C)∪Ns(φ(u))∪{p(φ(u))} for every u∈H1∩S, so that (23) is equivalent to (1).
It remains to show that (1) also holds for u∈H1∩P, but this is a much simpler check. Indeed, we have N(u)={s(u)} and, by construction, s(u)∈V1, so that the left-hand side of (1) is N(u)-V1=∅. Analogously, φ(u)=p(φs(s(u))) and therefore N(φ(u))={φs(s(u))}; again, φs(s(u))∈V2 and the right-hand side of (1) also verifies N(φ(u))-V2=∅. This means that (1) holds trivially if u∈H1∩P and this, together with the remarks in the previous paragraph, shows that H1 and H2 as constructed above are F-twins in the full graph.
Note finally that, apart from the twin-free requirements above, bothC1 and S admit any topology since no additional restrictions emanate from Definition 19. This completes the proof of Theorem 20.


### 5.3. Enumeration of CSP Structures

Theorem20 above essentially reduces the enumeration problem for CSP structures to a combination of a subgraph C1 within the core displaying no true twin vertices and a semiperiphery subgraph S without any kind of F-twins, with the eventual addition (join) of a complete graph C0 with its corresponding peripheries attached. In this problem one is faced with two different subproblems of independent mathematical interest: enumerating graphs without true twin vertices on the one hand and graphs without F-twin subgraphs on the other. We let tn and sn be the numbers of graphs on n vertices without true twin vertices and without F-twin subgraphs, respectively. It is worth mentioning that, in light of Theorem 18, these two numbers coincide with those of graphs without false twin vertices and graphs without T-twin subgraphs, although we will not make use of this except for the obvious remark that sn≤tn. Related enumeration problems are finding the numbers of graphs without any type of twin vertices (i.e., without either true or false twin vertices) and without either T-twin or F-twin subgraphs.The number of core-semiperiphery-periphery structures can be computed in arbitrary order (≥3) in terms of the quantitiestn and sn defined above. We will do so by splitting the computation in two parts. First we compute the number xn of core-semiperiphery-periphery structures of order n in which all periphery vertices are adjacent to the semiperiphery: this corresponds to the case n0=0 (or C0=K0) in the notation of Theorem 20. Later on we will add a number yn of structures with n0>0 to get the total number zn=xn+yn of CSP structures on n vertices.In order to computexn, by means of Theorem 20 the number of joins C1+S is easily seen to be given by all combinations of tnc core subgraphs on nc vertices without true twins and sns semiperiphery subgraphs on ns vertices without F-twin subgraphs. Using the fact that in this setting ns=np and then n=nc+2ns, some easy computations yield(24)xn=∑k=1n-1/2t2k-1sn+1/2-kifnis  odd∑k=1n-2/2t2ksn/2-kifnis  even,for n≥3.On the other hand, we can computeyn in a recursive manner, just using the remark that all structures with n0>0 can be obtained from a lower order structure just joining (the core vertex of) a core-periphery pair to the cores and semiperipheries of this lower order structure. This leads to(25)yn=zn-2ifnis  oddzn-2+sn/2-1ifnis  even,again for n≥3. The additional term sn/2-1 for even n captures the structures with only one core which belongs to C0. Note that we make recursive use of the total number zn=xn+yn of core-semiperiphery-periphery structures, setting z1=z2=0 for consistency.Equations (24) and (25) together define recursively the total number of core-semiperiphery-periphery structures on n vertices, which (omitting details for the sake of brevity) read, in terms of the numbers n (total number of vertices) and nc (number of core vertices), as(26)zn,nc=∑k=0min⁡Enc-1/2,n-nc-3/2tnc-2k-1sn-nc-1/2-kifn-ncis  odd∑k=0min⁡Enc/2,n-nc/2-1tnc-2ksn-nc/2-kifn-ncis  even.Finally, zn is the sum of the above values of zn,nc for nc=1⋯n-2.In the sequel we use the above derived formulas to compute the number of core-semiperiphery-periphery structures in low order (up ton=8), in terms of the previously defined quantities tn and sn. To the knowledge of the author, the number tn of graphs without true twin vertices (or without false twins vertices) is not known in general; however, computationally this is a very simple task in low order and for later use we depict the numbers tn up to n=6 in Table 1.Table 1
Number of graphs without (true) twin vertices.
Order (n) #Graphs without (true) twin vertices (tn) 1 1 2 1 3 2 4 5 5 16 6 78The computation ofsn (i.e., the number of graphs on n vertices without any kind of F-twin subgraphs) is more involved even from a computational point of view. Nevertheless, it is very easy to check that the lowest order structure involving F-twin subgraphs with order greater than one is K2∪K2; this obviously implies that sn=tn for n≤3. Additionally, one can easily see that only the subindices i=1,2,3 for si are involved in the computation of the number of CSP structures up to order eight. Using these remarks, the numbers zn up to n=8 are given in Table 2.Table 2
Number of core-semiperiphery-periphery structures.
Order (n) Number of CSP structures (zn) 3 1 4 2 5 4 6 9 7 24 8 96


### 5.4. CSP Structures in Low Order

The core-semiperiphery-periphery structures in order up to 6 are displayed in Figures3 and 4. Core, semiperiphery, and periphery vertices are painted black, grey, and white, respectively. Worth commenting are the facts that with n=3 one gets the expected “elementary” CSP structure and that one of the two cases with n=4 arises from the addition of a periphery vertex connected to a (say) C0 core vertex; a structure with two cores is already displayed in order four. Note also that up to three and four cores are displayed with n=5 and n=6.Figure 3
CSP structures up to order five.Figure 4
CSP structures in order six.


## 5.1. A Parameterized Definition of Core-Semiperiphery-Periphery Structures

We first note that the condition depicted in item (i) in Section2.3, defining core vertices, may be recast as the requirement that all of them have eccentricity one. This approach is intimately related to thecloseness centrality notion, widely used in network theory [34, 38]. This idea has been previously used in the definition of core vertices within core-periphery structures [10, 11] and paves the way for the definition presented below.Definition 19.
A core-semiperiphery-periphery structure is a 3-partitioned connected graph with the following (nonempty) vertex classes:(i)
Core vertices, with eccentricity not greater than two(ii)
Semiperiphery vertices, adjacent (at least) to a pair of nonadjacent vertices from the other two classes(iii)
Periphery vertices, with degree one.
Moreover, the graph is required not to have proper T-twin core vertices or proper F-twin semiperiphery-periphery subgraphs.Here, semiperiphery vertices are simply required to act as intermediaries between (at least) a core and a periphery, whereas for the latter we impose a minimal connection to the rest of the network, in a way which implies in particular that periphery vertices are isolated from each other (cf. item (ii) in Section2.3). Note that the requirements depicted for each class may be satisfied by vertices from other classes: for example, a core may have degree one or connect a pair of (nonadjacent) semiperiphery and periphery vertices, whereas a semiperiphery or a periphery vertex might well have eccentricity not greater than two. It is pretty clear, however, that the requirements in items (ii) and (iii) are mutually exclusive.It is worth emphasizing that this approach admits further extensions; on the one hand we may consider the maximum core eccentricity (mce) and maximum periphery degree (mpd) as parameters which in our present framework are fixed to the values two and one in (i) and (iii), respectively. Allowing these parameters to take on higher values may well lead to other structures of interest. Additionally, in a setting with mce≥3 we might also define structures with more than three (ranked) classes, by distinguishing several semiperiphery layers defined by vertices which are adjacent to vertex pairs coming from a higher-rank and a lower-rank class (examples of networks with four classes can be found in [16, 17]). These ideas define tentative lines for future research.The twin-free conditions stated at the end of Definition19, supported on the ideas discussed in Sections 3 and 4, are the key element to reduce the seemingly large number of CSP structures. As already indicated in the Introduction and in Section 2.3, the core should be thought as a set of heavily interconnected vertices, amounting to a fully connected set in idealized cases; for this reason the true twin notion for vertices is enough to reduce the eventual number of core subgraphs within core-semiperiphery-periphery structures. On the other hand, the F-twin concept for the semiperiphery-periphery subgraph arises as a natural extension of the false twin notion for periphery vertices discussed in Section 2.3, allowing one to reduce the number of semiperiphery-periphery subgraphs as well. Note also that the nonadjacency property stated in Corollary 6 captures the fact that twin semiperiphery-periphery substructures to be reduced should be somehow independent, being related only through the core vertices; in other words, if two (or more) semiperiphery vertices are adjacent then it is natural to consider them as part of the same substructure.


## 5.2. Decomposition of CSP Structures

Definition19 allows for an explicit description of core-semiperiphery-periphery structures, as detailed below.Theorem 20.
Core-semiperiphery-periphery structures meeting Definition19 admit the decomposition described in the sequel.(1)
The core subgraphC is a join C0+C1, where (i) C0 is a complete graph Kn0 and (ii) C1 is any graph of order n1 without T-twin vertices.(2)
The core-semiperiphery subgraph is a joinC+S, where C has the form described above and S is any graph or order ns without F-twin subgraphs.(3)
The periphery subgraphP is an empty graph of order np=n0+ns. Periphery vertices are leaves attached in a one-to-one basis either to a vertex from C0 or from S.
The ordersnc=n0+n1, ns, and np do not vanish, but either n0 or n1 may do.Proof.
Note in advance that the splitting of core vertices in two groupsC0 and C1 is defined from the fact that those in C0 are connected to a periphery vertex, whereas those in C1 are not, as stated in item 3. In this regard, it is obvious that periphery vertices are only connected either to a core (in C0) or to a semiperiphery vertex because of the degree one condition stated in item (iii) of Definition 19; notice that a single K2 consisting of two peripheries is ruled out by the requirement that the graph has at least one core and one semiperiphery vertex. Conversely, semiperiphery vertices are necessarily connected to a single periphery (in addition to cores and, possibly, other semiperipheries), since two or more peripheries eventually connected to the same semiperiphery vertex would be false twins. For the same reason, a core vertex in C0 is attached to one periphery (again, in addition to connections to other cores and to semiperipheries). These properties fully describe the structure of the periphery subgraph P and will be used throughout the rest of the proof.
Regarding the structure of the core subgraph,C0 is a complete graph (maybe the null one K0) and, moreover, it defines a join with (i.e., it is fully connected to) C1, if nonempty, because of the eccentricity requirement for core vertices. Indeed, suppose that there is a pair of nonadjacent core vertices, at least one of which is adjacent to a periphery (i.e., at least one of which is in C0): the distance of this periphery vertex to the other core in that pair would be at least three, against the assumption that the maximum eccentricity of core vertices is two as stated in item (i) of Definition 19.
The core and the semiperiphery are fully connected as well. Again, assuming the contrary, the distance between such a core and the periphery vertex adjacent to that semiperiphery would be greater than two, against the aforementioned eccentricity requirement.
It remains to show that the exclusion of twin structures in Definition19 is equivalent to the absence of the corresponding twin structures in the core or semiperiphery subgraph, respectively, in the terms stated in this Theorem. Regarding core vertices, note first that C0 may never include T-twins (meant in the full graph) since the peripheries attached to these cores are adjacent only to one core and, therefore, these peripheries necessarily make a difference in the neighborhoods of the corresponding cores; for the same reason, cores in C0 and in C1 may never be T-twins in the full graph. Additionally, the absence of T-twins in C1 can be equivalently checked in the full graph or in the core subgraph because of the fact that cores in C1 are not adjacent to any peripheries and, on the contrary, fully connected to both C0 and S; this means that the neighborhoods of two C1-cores in the full graph differ if and only if these core vertices have different neighbors within C1.
Concerning the equivalence between F-twin structures, let us first assume that two subgraphsH1 and H2 within the semiperiphery-periphery subgraph are F-twins in the full graph, and let φ denote the corresponding isomorphism, so that (1) holds for all u∈V1=V(H1). Let φs stand for the restriction of this isomorphism to H1∩S, and denote V1s=V1∩V(S) and V2s=V2∩V(S). From (1) we get (18)Nu-V1∩VS=Nφu-V2∩VS,an identity that can be recast as(19)Nsu-V1s=Nsφu-V2sby making use of the property (A-B)∩C=A∩C-B∩C for arbitrary sets A, B, and C (here Ns(u) denotes N(u)∩V(S)). By noting that (19) holds for all u∈V1s and that φ(u)=φs(u) for vertices in V1s, it follows that H1∩S and H2∩S are F-twins as subgraphs of S via the restricted isomorphism φs, as we aimed to show.
Conversely, letH1s and H2s be F-twin structures as subgraphs of S, and denote by φs the corresponding isomorphism. Denote by V1s and V2s the vertex sets of H1s and H2s, respectively. Let H1 (resp., H2) be the subgraph induced in the full graph by the vertices of V1s (resp., V2s) and their adjacent peripheries, and write as V1 (resp., V2) the vertex set of H1 (resp., H2). Now, for every u∈V(S) write as p(u) the unique periphery vertex attached to u in the full graph and, conversely, for every u∈P let s(u) be the unique semiperiphery vertex adjacent to u. With this notation we extend the isomorphism φs to the whole of H1 by setting (20)φu=φsuifu∈H1∩Spφssuifu∈H1∩P.We claim that φ makes H1 and H2 F-twin subgraphs in the full graph. First, note that by construction (19) is met for all u∈H1∩S, and then(21)VC∪Nsu-V1s=VC∪Nsφu-V2sholds because V(C)∩V1s=V(C)∩V2s=∅; additionally, since V1-V1s and V2-V2s are in the periphery, we may rewrite (21) as(22)VC∪Nsu-V1=VC∪Nsφu-V2.Moreover, using the fact that p(u)∈V1,p(φ(u))∈V2, (22) yields(23)VC∪Nsu∪pu-V1=VC∪Nsφu∪pφu-V2.In light of the join structure proved above for C+S we have N(u)=V(C)∪Ns(u)∪{p(u)} and N(φ(u))=V(C)∪Ns(φ(u))∪{p(φ(u))} for every u∈H1∩S, so that (23) is equivalent to (1).
It remains to show that (1) also holds for u∈H1∩P, but this is a much simpler check. Indeed, we have N(u)={s(u)} and, by construction, s(u)∈V1, so that the left-hand side of (1) is N(u)-V1=∅. Analogously, φ(u)=p(φs(s(u))) and therefore N(φ(u))={φs(s(u))}; again, φs(s(u))∈V2 and the right-hand side of (1) also verifies N(φ(u))-V2=∅. This means that (1) holds trivially if u∈H1∩P and this, together with the remarks in the previous paragraph, shows that H1 and H2 as constructed above are F-twins in the full graph.
Note finally that, apart from the twin-free requirements above, bothC1 and S admit any topology since no additional restrictions emanate from Definition 19. This completes the proof of Theorem 20.


## 5.3. Enumeration of CSP Structures

Theorem20 above essentially reduces the enumeration problem for CSP structures to a combination of a subgraph C1 within the core displaying no true twin vertices and a semiperiphery subgraph S without any kind of F-twins, with the eventual addition (join) of a complete graph C0 with its corresponding peripheries attached. In this problem one is faced with two different subproblems of independent mathematical interest: enumerating graphs without true twin vertices on the one hand and graphs without F-twin subgraphs on the other. We let tn and sn be the numbers of graphs on n vertices without true twin vertices and without F-twin subgraphs, respectively. It is worth mentioning that, in light of Theorem 18, these two numbers coincide with those of graphs without false twin vertices and graphs without T-twin subgraphs, although we will not make use of this except for the obvious remark that sn≤tn. Related enumeration problems are finding the numbers of graphs without any type of twin vertices (i.e., without either true or false twin vertices) and without either T-twin or F-twin subgraphs.The number of core-semiperiphery-periphery structures can be computed in arbitrary order (≥3) in terms of the quantitiestn and sn defined above. We will do so by splitting the computation in two parts. First we compute the number xn of core-semiperiphery-periphery structures of order n in which all periphery vertices are adjacent to the semiperiphery: this corresponds to the case n0=0 (or C0=K0) in the notation of Theorem 20. Later on we will add a number yn of structures with n0>0 to get the total number zn=xn+yn of CSP structures on n vertices.In order to computexn, by means of Theorem 20 the number of joins C1+S is easily seen to be given by all combinations of tnc core subgraphs on nc vertices without true twins and sns semiperiphery subgraphs on ns vertices without F-twin subgraphs. Using the fact that in this setting ns=np and then n=nc+2ns, some easy computations yield(24)xn=∑k=1n-1/2t2k-1sn+1/2-kifnis  odd∑k=1n-2/2t2ksn/2-kifnis  even,for n≥3.On the other hand, we can computeyn in a recursive manner, just using the remark that all structures with n0>0 can be obtained from a lower order structure just joining (the core vertex of) a core-periphery pair to the cores and semiperipheries of this lower order structure. This leads to(25)yn=zn-2ifnis  oddzn-2+sn/2-1ifnis  even,again for n≥3. The additional term sn/2-1 for even n captures the structures with only one core which belongs to C0. Note that we make recursive use of the total number zn=xn+yn of core-semiperiphery-periphery structures, setting z1=z2=0 for consistency.Equations (24) and (25) together define recursively the total number of core-semiperiphery-periphery structures on n vertices, which (omitting details for the sake of brevity) read, in terms of the numbers n (total number of vertices) and nc (number of core vertices), as(26)zn,nc=∑k=0min⁡Enc-1/2,n-nc-3/2tnc-2k-1sn-nc-1/2-kifn-ncis  odd∑k=0min⁡Enc/2,n-nc/2-1tnc-2ksn-nc/2-kifn-ncis  even.Finally, zn is the sum of the above values of zn,nc for nc=1⋯n-2.In the sequel we use the above derived formulas to compute the number of core-semiperiphery-periphery structures in low order (up ton=8), in terms of the previously defined quantities tn and sn. To the knowledge of the author, the number tn of graphs without true twin vertices (or without false twins vertices) is not known in general; however, computationally this is a very simple task in low order and for later use we depict the numbers tn up to n=6 in Table 1.Table 1
Number of graphs without (true) twin vertices.
Order (n) #Graphs without (true) twin vertices (tn) 1 1 2 1 3 2 4 5 5 16 6 78The computation ofsn (i.e., the number of graphs on n vertices without any kind of F-twin subgraphs) is more involved even from a computational point of view. Nevertheless, it is very easy to check that the lowest order structure involving F-twin subgraphs with order greater than one is K2∪K2; this obviously implies that sn=tn for n≤3. Additionally, one can easily see that only the subindices i=1,2,3 for si are involved in the computation of the number of CSP structures up to order eight. Using these remarks, the numbers zn up to n=8 are given in Table 2.Table 2
Number of core-semiperiphery-periphery structures.
Order (n) Number of CSP structures (zn) 3 1 4 2 5 4 6 9 7 24 8 96


## 5.4. CSP Structures in Low Order

The core-semiperiphery-periphery structures in order up to 6 are displayed in Figures3 and 4. Core, semiperiphery, and periphery vertices are painted black, grey, and white, respectively. Worth commenting are the facts that with n=3 one gets the expected “elementary” CSP structure and that one of the two cases with n=4 arises from the addition of a periphery vertex connected to a (say) C0 core vertex; a structure with two cores is already displayed in order four. Note also that up to three and four cores are displayed with n=5 and n=6.Figure 3
CSP structures up to order five.Figure 4
CSP structures in order six.


## 6. CSP Structure within the Asia-Africa-Oceania Subnetwork of 1994 Metal Manufactures Trade

The approach developed in previous sections provides a formal definition and a criterion for the systematic classification of core-semiperiphery-periphery structures in networks. In order to identify such structures in real problems, we need to develop additional results based on positional analyses allowing one to assign systematically vertices to clusters and to evaluate the extent to which the quotient network fits a CSP structure. This task, in its broad generality, exceeds the scope of the present paper and will be the object of future research. However, we discuss below a roadmap for this research by examining a given subnetwork of the network of miscellaneous imports of metal manufactures between 80 countries in 1994. These data, coming from world trade statistics, have been previously addressed in [16] along the lines discussed in the original work of Wallerstein [4]. This data set is freely available on the web (cf. [16]).Since the results in this section have illustrative purposes and in order to simplify the discussion we restrict the attention to a subnetwork of the abovementioned network, namely, the one defined by the countries from Asia, Africa, and Oceania for which data are available in the original dataset. Note that the large amount of exports of high-technology products from East Asian countries makes this analysis relevant, looking in particular for their relation patterns with developing and least-developed countries from Africa, Oceania, and other regions of Asia. In our model, every edge in the network is weighted with the total amount of trade between the two countries (i.e., we add imports and exports). To reduce dimensionality we remove edges in which this amount does not reach 10 M (10 million) USD or links involving countries whose total amount of trade does not reach 25 M USD; note that these quantities barely represent a few parts per thousand of the total amount of trade in this network which is over 8 billion USD. Exceptions are made when such a removal renders the network disconnected: for the involved countries we then retain the edge displaying the highest amount of trade with any of their commercial neighbors. This yields a connected network with 29 nodes and 69 edges (data are displayed on Table3).Table 3
Asia-Africa-Oceania metal manufactures trade in 1994 (from [16]).
Country #1 Country #2 Trade (thousands of USD) China Hong Kong 1482824 Japan Thailand 894820 Japan Korea 880295 China Japan 630342 Malaysia Singapore 484350 Japan Malaysia 453463 Japan Singapore 380454 Hong Kong Japan 351919 Indonesia Japan 200451 China Korea 181392 Australia New Zealand 168680 Japan Philippines 138348 China Singapore 135616 Japan Australia 115283 Hong Kong Singapore 110574 Singapore Thailand 107720 China Australia 90620 Australia Indonesia 72387 Korea Hong Kong 65315 Australia Singapore 62392 Korea Thailand 56160 Korea Singapore 50098 Korea Australia 45517 China Thailand 44387 Australia Malaysia 43068 Korea Indonesia 41827 Indonesia Malaysia 40291 China Malaysia 39617 Singapore Indonesia 39206 Malaysia Thailand 37963 China Indonesia 32817 India Singapore 32130 Korea Malaysia 31255 Japan India 27655 Japan South Africa 24555 Hong Kong Malaysia 24159 Hong Kong Thailand 23642 Hong Kong Philippines 23396 China South Africa 23166 Singapore Philippines 21744 Hong Kong South Africa 21277 Australia India 20366 China Philippines 19865 Israel South Africa 19183 Korea South Africa 17826 Korea Philippines 17031 India Malaysia 15817 Japan New Zealand 15470 Korea Pakistan 15469 Thailand Australia 14377 China Egypt 14342 China Pakistan 13953 Hong Kong Australia 13644 China New Zealand 12810 Hong Kong Indonesia 12604 Singapore Sri Lanka 12253 China Algeria 11709 Australia Fiji 10589 Japan Pakistan 10388 China Kuwait 9232 China Jordan 8014 China Morocco 7077 South Africa Mauritius 6805 Algeria Tunisia 6283 China Bangladesh 5217 India Oman 4151 Thailand Seychelles 3179 South Africa Reunion 2566 Japan Madagascar 2042In order to examine the presence of CSP structures in this network, as well as the eventual reduction of twin substructures, we use two different criteria to cluster vertices. The first one is very elementary and just uses a threshold in the volume of trade between pairs of countries: we use this basic approach to provide simple examples of CSP structures and twin subgraphs. The second criterion is more elaborate: in order to identify clusters we combine the amount of trade between countries, as above, with a dissimilarity measure capturing similar relation patterns. This will result in a refinement of the CSP structures which arise under the first clustering criterion. Details are given below.As indicated above, let us first cluster the different countries using the connected components of the graph which results from removing edges below a given trade threshold. Let us for instance consider pairs of countries exchanging at least 75 M USD. This yields a main cluster defined by 11 countries, namely, China, Hong Kong, Japan, Thailand, and Korea (to be referred to in the sequel as East Asian countries), together with Malaysia, Singapore, Indonesia, the Philippines (Southeast Asia), and Australia and New Zealand (both countries being jointly referred to as Australasia). This cluster comprises more than 7.7 billion USD trade, that is, more than 95% of the total amount of trade in the network. None of the remaining countries reaches the above threshold with any neighbor, so that each one of the other clusters is identified with a single country.With this clustering, the quotient graph displays 3 countries (Algeria, South Africa, and India) which are adjacent to the main cluster and to 5 countries with degree one (Tunisia (Algeria), Israel, Mauritius, Reunion (South Africa), and Oman (India), resp.). There are 10 countries with degree one which are adjacent to the main cluster (Pakistan, Bangladesh, Egypt, Jordan, Kuwait, Morocco, Madagascar, Seychelles, Sri Lanka, and Fiji). This quotient network is displayed in Figure5(a); we explicitly label the vertices corresponding to Algeria, South Africa, and India for better clarity.Figure 5
Clustering with threshold 75 M USD: (a) CSP network; (b) reduction of false twin vertices; (c) CSP structure.This quotient graph admits a classification of all the clusters either as a core, semiperiphery, or periphery, according to the criteria given in Definition19. The core is composed of the East and Southeast Asian countries together with Australia and New Zealand, whereas the semiperiphery is composed of three countries (Algeria, South Africa, and India), and the fifteen countries with degree one define the periphery. Among the latter, the three ones adjacent to South Africa are false twins (we use Israel as their representative) and, analogously, the ten countries with degree one attached to the core are false twins as well (with Pakistan as the representative of this class). After identifying false twin vertices, the resulting graph is displayed in Figure 5(b). In turn, this figure clearly displays three subgraphs which are F-twins, namely, the semiperiphery-periphery pairs defined by Algeria and Tunisia, South Africa and Israel, and India and Oman, respectively. After identifying these three subgraphs (with the pair South Africa-Israel being chosen as the representative of this relation pattern), the resulting CSP structure is depicted in Figure 5(c) (it has four vertices and can be also found in Figure 3). We emphasize that the F-twin notion makes it possible to capture the elementary pattern displayed by the three semiperiphery-periphery pairs mentioned above.Another pattern arises if we raise the threshold to cluster countries say to 125 M USD. Since now neither Australia nor New Zealand trades such an amount with any Asian country, but they do with each other, they turn to define a cluster by themselves (Australasia in the sequel), independently of the East and Southeast Asian countries which are still joined together into a big cluster, trading more than 7 billion USD. The latter still meets the requirement defining a core in Definition19, but the Australasian cluster does not, since it does not satisfy the eccentricity-two criterion (e.g., its distance to Israel is three). Australasia may by contrast be classified as a semiperiphery: note that Fiji is now attached to the Australasian cluster. The new quotient graph is displayed in Figure 6(a). As before, we depict in Figures 6(b) and 6(c), respectively, the network without false twin vertices and the CSP structure which finally results from removing F-twin structures (now only the Algeria-Tunisia and South Africa-Israel pairs).Figure 6
Clustering with threshold 125 M USD: (a) CSP network; (b) reduction of false twin vertices; (c) CSP structure.As indicated earlier, the clustering criterion above already paves the way to illustrate some relation patterns; in a deeper analysis, however, it displays a severe limitation. Clustering countries according to their amount of trade works well for (eventually defined) core clusters and also for some semiperipheries. But it does not accommodate the identification of semiperiphery countries which, not trading a significant amount between themselves, display however a similar (or even identical) connection pattern to the rest of the network. To incorporate this, the criterion above should be combined with a similarity (or dissimilarity) measure identifying countries with similar relation patterns.To illustrate this idea we first raise the trade threshold above to 500 M USD. This yields a smaller cluster defined by the five East Asian countries (trading more than 4.6 billion USD among themselves). Second, since we are dealing with a weighted network we define a dissimilarity criterion as follows: for each country we label each one of its incident edges with the percentage of trade that it carries, computed over the country’s total amount of trade. This percentage is zero for absent edges, that is, for pairs of countries not adjacent to each other. Denoting this percentage bywij for the edge connecting vertices i and j, the dissimilarity measure for countries i, j is then defined as (27)δij=∑i≠k≠jwik-wjk.This means that two countries which have exactly the same connection pattern to the rest of the network have a dissimilarity measure close to zero (not exactly zero, in most cases, because even if the connections are the same the percentages will typically be different); on the contrary, if i and j are not adjacent and do not have any neighbor in common then the dissimilarity measure reaches the maximum value δij=2.Ignoring peripheries, we may now define new clusters (i.e., besides the main one above) in terms of this dissimilarity measure: for instance, we may join together a set of countries into a single cluster if the dissimilarities of all pairs within this set do not reach a threshold of 1.0. Two nontrivial clusters arise this way: the four Southeast Asian countries are joined into a single cluster (the six dissimilarities range from 0.33 (Malaysia-Singapore) to 0.95 (Singapore-Philippines); the total internal trade in this cluster reaches 585 M USD) and so do Australia and New Zealand (with a dissimilarity of 0.59; the trade among themselves is 168 M USD). The remaining countries remain isolated. Note that none of these countries reach, in any connection, the threshold of peer-to-peer trade of 500 M USD defined above.The quotient graph which results from this new clustering is displayed in Figure7(a); now Sri Lanka is not adjacent to the core but to the Southeast Asian cluster, via Singapore. As already depicted in this figure, the five East Asian countries qualify again as a core, whereas the other clusters do not because of the eccentricity criterion. The reductions of false twin vertices and of F-twin pairs yielding a CSP structure can be found in Figures 7(b)-7(c).Figure 7
Adding a dissimilarity measure: (a) CSP network; (b) reduction of false twin vertices; (c) CSP structure.Finally, in order to further illustrate the eventual presence of other F-twin substructures, let us ignore in Figure7(c) the edge connecting India and Australasia: among the three semiperipheries at the bottom of this figure, this is clearly the one carrying less trade (20,2 M USD, whereas Southeast Asia trades 47,9 M with India and over 177 M with Australasia). The resulting network is depicted in Figure 8(a). Note that now the Australasia-Fiji and India-Oman pairs become F-twins; they are isomorphic, disjoint, and nonadjacent, and the connection pattern to the remainder of the network is the same (both Australasia and India are connected to the core and to Southeast Asia). We can therefore reduce this new relation pattern and the resulting structure is displayed in Figure 8(b). Worth clarifying is that the Australasia-Fiji pair now stands as the representative of this pattern, which is also met by the India-Oman pair.Figure 8
(a) The removal of the Australasia-India edge yields a new pair of F-twin subgraphs; (b) resulting CSP structure.As indicated earlier in this section, the network here analyzed is intended to illustrate the lines along which the results presented in this paper can be applied to real problems. Future study should provide a systematic analysis of clustering criteria in this context; these criteria should combine density and similarity measures. In a second step, quality measures defining the extent to which the nodes in the quotient (clustered) graph may be classified either as cores, semiperipheries, or peripheries would indicate to what degree the network fits a CSP structure. When a CSP structure is actually met, the twin notions here introduced make it possible to reduce identical substructures, capturing the relation patterns depicted in the network.The example here considered suggests that the roadmap above is a promising one. Note that the threshold parameters within the aforementioned clustering criteria (involving, e.g., the amount of trade or the degree of dissimilarity between countries) have allowed for a progressive refinement of the clusters, providing gradually more detailed information about the network structure. Indeed, the (say) giant core in Figure5(b) yields two clusters in Figure 6(b), namely, East/Southeast Asia and Australasia; in turn, the East-Southeast Asian core is split into two in Figure 7(b). Accordingly, the corresponding CSP structures in Figures 5(c), 6(c), and 7(c) (with four, eight, and ten nodes, respectively) gradually display more detailed information about the network structure. The network example here considered also shows how different twin structures may be identified and reduced. These include not only twin vertices but different semiperiphery-periphery patterns: compare, for example, in Figure 8(a) the Algeria-Tunisia and South Africa-Israel pairs, on the one hand, and India-Oman and Australasia-Fiji, on the other. Naturally, more complicated semiperiphery-periphery patterns would arise in larger networks.


## 7. Concluding Remarks

Many problems related to twin subgraphs and to core-semiperiphery-periphery structures remain open for future study. We compile here some of them. First, the T-twin and F-twin notions for subgraphs introduced in Sections3 and 4 have for sure a connection to automorphic and orbital equivalences, much as twin vertices arise in situations in which a transposition yields a graph automorphism. Note in this regard that, for vertices, the true and false twin notions accommodate all possible cases of structurally equivalent vertices, but for higher order subgraphs other twin notions besides T-twins and F-twins might be considered (for this reason we avoid using the “true” and “false” labels for our T-twin and F-twin notions, since the former labels seem to cover exhaustively all possible cases). The classification of twin structures partially addressed in Section 3.3 also seems to have several potential extensions, in particular, connected to the interrelations between the classification of different families of twin subgraphs.Concerning the results considered in Section5, it would be interesting to examine systematically to what extent the set of actors (countries, companies, etc.) in real social or economic networks can be clustered in a way that matches some of the structures displayed in Section 5.4 after a suitable reduction of twin patterns: the example discussed in Section 6 suggests a plan for future research in this direction. Motivated by the enumeration of CSP structures (cf. Section 5.3), several enumeration problems arise in connection with the absence of twin substructures in graphs: specifically, it would be of interest to get a general enumeration formula for graphs without true twin vertices (or equivalently, in light of Theorem 18, for graphs without false twin vertices) and also for graphs without any kind of T-twin (or, analogously, F-twin) subgraphs. Closely related are the problems of enumerating graphs without any kind of twin vertices, or without any kind of twin subgraphs. It also seems to be worth studying other (say, layered) structures emanating from greater parameter values in Definition 19, that is, accommodating core eccentricities greater than two and/or periphery degrees greater than one. All these topics are in the scope of future research.



---

*Source: 2547270-2018-04-18.xml*