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; this approach supports so-called positional analyses and the definition of certain structures in social, commercial and economic networks. A key notion in this context is that of structurally equivalent or twin nodes, displaying exactly the same connection pattern to the remainder of the network. Abstract The first goal of this paper 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 K 2 , a fact which is here understood to rely on the truetwin 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 Ttwin and F-twin notions then make it possible to reduce the large number of resulting structures by identifying isomorphic substructures which share the connection pattern to the remainder of the graph, paving the way for the decomposition and enumeration of CSP structures. We compute explicitly the resulting CSP structures up to order six. Abstract 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. As this example suggests, our approach can be naturally applied in complex network theory and seem to have many potential extensions, since the analytical properties of twin subgraphs and the structure of CSP and other partitioned graphs admit further study. Introduction 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 of twin 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 (that is, problems which go beyond the eventual application of these notions to the classification of CSP structures). These sections introduce and elaborate on the idea of F-twin and T-twin subgraphs, which in a sense are dual to each other and generalize several known properties of false twin and true twin vertices; e.g. distinct connected components of F-twin pairs will be proved to be disjoint and non-adjacent, 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 [19] , in the spirit of the the aforementioned seminal work [37] , and nowadays define a widely used benchmark for the positional analyses of networks. Finally, Section 7 compiles some lines for future research. Introduction 2 Background on graphs, twins, and core-periphery networks Graph-theoretic notions We refer the reader to [5, 6, 20, 23] for excellent introductions to graph theory. Throughout the paper we will work with undirected graphs G = (V, E) without parallel edges or selfloops, so that edges can be thought of as pairs of distinct vertices (also termed nodes). 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 V 0 ⊆ G for V 0 ⊆ 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). Graph-theoretic notions A path of length k ≥ 0 is a graph with k + 1 distinct vertices v 0 , v 1 , . . . , v k and edges e 1 , . . . , e k with e i joining v i−1 and v i . Since we are not allowing parallel edges, a path is uniquely defined by its vertex set. We say that v 0 and v k are linked 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 path from v 0 to v k . The distance, 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. The eccentricity of a vertex in a connected graph is the maximum distance to other vertices. The distance between two disjoint subgraphs H 1 and H 2 lying in the same connected component of a given graph is defined as min{d(u, v), u ∈ H 1 , v ∈ H 2 }. We say that two disjoint subgraphs H 1 and H 2 are not adjacent if there is no adjacent pair (u, v) with u ∈ H 1 , v ∈ H 2 ; if both subgraphs lie in the same connected component of G, this is equivalent to saying that d(H 1 , H 2 ) ≥ 2. Graph-theoretic notions We will denote by N (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}. The degree of a vertex u is the number of elements in N (u). We will call a vertex of degree one a leaf (note that this term is often reserved to cases in which the whole graph is acyclic, that is, a disjoint union of trees), and will say that it is attached to its unique adjacent vertex. Graph-theoretic notions The null graph defined by V = ∅ will be denoted by K 0 ; K n 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(K n ) − E)) will be written as G, and E n will stand for the empty graph K n on n ≥ 1 vertices. Cycles, paths and stars on n vertices will be written as C n , P n and S n , respectively, with n ≥ 3 for cycles. As usual, the union and intersection of G i = (V i , E i ) (i = 1, 2) are the graphs (V 1 ∪ V 2 , E 1 ∪ E 2 ) and (V 1 ∩ V 2 , E 1 ∩ E 2 ), respectively. The join G 1 + G 2 of two graphs with disjoint vertex sets V (G 1 ), V (G 2 ) is the graph obtained after enlarging G 1 ∪ G 2 with all possible edges joining the vertices of G 1 to those of G 2 (sometimes we express the latter by saying that G 1 and G 2 are fully connected to one another). Graph-theoretic notions A partitioned graph is simply a graph whose vertex set is split into (pairwise disjoint) classes. A k-partitioned graph is a partitioned graph with k non-empty partition classes. Obviously, a partitioned graph defines an equivalence relation in the set of vertices. The quotient graph (often called a supergraph) of a partitioned graph is defined as a graph whose vertex set is the quotient set (that is, vertices in the quotient graph correspond to the partition classes in the original graph), 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. Graph-theoretic notions An isomorphism of two graphs G 1 and G 2 is a bijection ϕ : V 1 → V 2 (with V i = V (G i )) which preserves adjacencies, that is, such that any given pair of vertices u, v in G 1 are adjacent if and only if ϕ(u) and ϕ(v) are adjacent in G 2 . An isomorphism of partitioned graphs is a graph isomorphism which keeps the classes invariant. Twins Different analytical and computational issues arise in connection to the existence and the distribution of isomorphic copies of certain subgraphs of a given graph: see e.g. [2, 15, 21, 23, 31] 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 and structurally equivalent vertices, as detailed in the sequel. Two (distinct) vertices u and v are false twins (resp. true [4, 11, 25, 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 called adjacent and non-adjacent twins (see e.g. [4, 24, 29] ). True twins correspond to 1-twins in the terminology of [12, 28] . 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 t u,v of u and v yields an automorphism of the graph (cf. [7, 10] ), a condition which is easily seen equivalent to u and v being (false or true) twins in the sense indicated above. Twins The F-twin and T-twin notions that will be introduced in Sections 3 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 2 and 6), 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 2), or the fact that twins will have the same distance multisets to the vertex set of the graph (cf. Proposition 4). In particular, twin subgraphs will define homometric sets (Corollary 3; cf. [1, 3, 35] ). 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. Core-periphery networks Consider one of the "idealized" core-periphery (CP) networks mentioned in Section 1, 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); Core-periphery networks (ii) periphery vertices, totally disconnected from each other (and fully connected to the core, in light of the first requirement above). Core-periphery networks 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. [8, 19] ). These core-periphery networks are simply 2-partitioned graphs of the form K p + E r (find notations in subsection 2.1; when using a 2-partitioned structure in K p + E r , we assume throughout the document and without further mention that the two partition classes are the vertex sets of K p and E r ). Cases with a unique core vertex amount to the star S n = K 1,n−1 = K 1 + E n−1 . In the simplest setting (n = 2) we get a 2-partitioned S 2 = K 2 = K 1 + K 1 , with a single core and a single periphery vertex; note that E 1 = K 1 , and we prefer to use the latter notation for the singleton graph. Core-periphery networks Aiming at later developments let us note that, in a certain sense, K 2 is substantially different from all other joins K p + E r . Actually, we may think of K 2 = K 1 + K 1 as the quotient graph of any other join of the form K p + E r . 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 K p ) are true twins as defined in subsection 2.2 above and, analogously, all periphery vertices (the ones in E r ) are false twins. In this context, K 2 arises not only as the reduction of other joins, but also as the unique twin-free network meeting the requirements (i) and (ii) above. From this point of view we may think of K 2 as the unique core-periphery structure (we use the latter term to make a distinction with the CP networks K p + E r above, which are allowed to display twin vertices). To avoid any misunderstanding, let us clarify that K 2 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; cf. the beginning of Section 5. Core-periphery networks 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. Core-periphery networks To put it in the simplest possible setting, compare the CP network K 1 + E 2 ( Fig. 1(a) ), which amounts to a 2-partitioned path P 3 with one class (the core, painted black in the figure) defined by the central node, with a 3-partitioned path P 5 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) ( Fig. 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 P 2 = K 2 attached to the core by a single articulation (the semiperiphery vertices). As indicated above, in the CP case (K 1 +E 2 ) the false twin notion makes it possible to identify the two peripheries into a single one, reducing the network to a 2-partitioned K 2 = P 2 (cf. Fig. 2(a) ). But, how can we reduce the CSP case (the spider) to a single P 3 , which captures the essential connection pattern? (Fig. 2(b) ). Note that both legs in Fig. 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 Fig. 1(b) are false twins, so that an eventual recourse to the notion of twin vertices would fail for our present purpose. Obviously, it would be easy to identify equal-length legs in spider graphs; however, more complex structures are possible: think e.g. of cases with more cores and/or with other connection patterns within the semiperiphery (actually, different CSP structures will arise in Sections 5 and 6; see . 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, are 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. Core-periphery networks 3 F-twin subgraphs Core-periphery networks hold for all u ∈ V 1 . Core-periphery networks We may also say that the set of vertices V 1 and V 2 are F-twins, since the definition above requires H 1 and H 2 to be the subgraphs induced by V 1 and V 2 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 = P 3 ∪ K 3 . Let H 1 be the P 3 -component of G and H 2 any one of the three subgraphs of K 3 isomorphic to P 3 . Should F-twins not be required to be induced subgraphs, H 1 and H 2 would be F-twins, because the identities (1) hold trivially since both sides are empty for all vertices. However there exists an extra edge in K 3 which make the endvertices of H 2 adjacent in G without the endvertices of H 1 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 H 1 and H 2 to be induced subgraphs. Core-periphery networks Note that any induced subgraph is trivially an F-twin of itself; we will say that a given induced subgraph is a proper 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). A trivial F-twin is an induced subgraph that has no F-twin but itself. Core-periphery networks In particular, the notion above for two single distinct vertices u, v amounts to requiring that they are false twins in the sense that N (u) = N (v), as defined in subsection 2.2. Just note that u ∈ N (u) and v ∈ N (v), so that (1) Proof. Assume first that H 1 and H 2 are F-twins, and let ϕ denote the isomorphism arising in Definition 1. Then ϕ induces k isomorphisms ϕ 1 , . . . , ϕ k between the connected components of H 1 and H 2 ; denote these connected components by H i,j , with i ∈ {1, 2}, j ∈ {1, . . . , k}, and let accordingly V i,j be the vertex set of H i,j , so that ϕ j : V 1,j → V 2,j . Then obviously Core-periphery networks and, provided that a vertex u (resp. ϕ(u)) belongs to V 1,j (resp. to V 2,j ), it is also clear that Core-periphery networks so that H 1,j and H 2,j are indeed F-twins. Core-periphery networks The converse result proceeds in exactly the same manner and details are left to the reader. ✷ Proof. Assume that w ∈ V 1 ∩ V 2 , and let K 1 and K 2 be the connected components of H 1 and H 2 which accommodate w. Assume that K 1 = K 2 and, w.l.o.g., suppose that there is a vertex in K 2 not belonging to K 1 . The set V (K 2 ) can be described as the disjoint union of Core-periphery networks ; indeed, should it belong to V 1 , since it is adjacent to u ∈ V (K 1 ) ⊆ V 1 it would necessarily belong to the same connected component of u, that is, Core-periphery networks we conclude that the whole connected components K 1 = K 2 are in the intersection H 1 ∩ H 2 as we aimed to show. ✷ Core-periphery networks In particular, Proposition 2 implies that distinct connected F-twins are actually disjoint. Distance-related properties We know from Proposition 2 that non-empty 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)∩V 2 = ∅ for all u ∈ V 1 ). A stronger statement actually holds. Distance-related properties Proposition 3. If H 1 and H 2 are disjoint F-twins in a given graph G, then their connected components can be arranged as F-twin pairs (H 1,j , H 2,j ) in a way such that, for every j, Distance-related properties • either H 1,j and H 2,j are connected components of G; or Distance-related properties • both H 1,j and H 2,j belong to the same connected component of G and Distance-related properties Proof. Take a connected component H 1,j of H 1 and assume that there exists a vertex Distance-related properties ∈ V 2 (a property that will be used later) and also that (u, v, ϕ(u)) is a path. Let H 2,j be the connected component of H 2 accommodating ϕ(u): then H 1,j and H 2,j are isomorphic via ϕ; moreover, they are in the same connected component of G and, additionally, Distance-related properties The same reasoning applies to all connected components of H 1 . Those for which there is no adjacent vertex away from V (H 1 ) are by definition connected components of G. Exactly the same reasoning applies to the connected components of H 2 and this completes the proof. ✷ Note also that for components H 1,j , H 2,k of H 1 and H 2 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(H 1,j , H 2,k ) ≥ 2 since they cannot be adjacent to each other. Corollary 2 follows directly from Proposition 3. 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 non-adjacency property of false twin vertices mentioned in subsection 2.2. Distance-related properties Corollary 2. If H 1 and H 2 are connected proper F-twins in a given graph G, then either they are connected components of G or d(H 1 , H 2 ) = 2. In either case, connected proper F-twins are not adjacent to each other. Distance-related properties Another distance-related property of proper F-twins is that they are homometric; this means that the distance multisets of both are the same [1, 3, 35] . The distance multiset of an order-k subgraph H of a connected graph G is the multiset of Distance-related properties also defines a length-k path. Distance-related properties Proof. The fact that all vertices v i are distinct is a direct consequence of the construction: indeed, note that ϕ maps Distance-related properties ) are pairwise disjoint sets, then the claim follows easily from the facts that ϕ, ϕ −1 and the identity are bijections and that the vertices u i are all distinct. Distance-related properties The other fact that needs to be proved is that the pairs {v i−1 , v i } are adjacent. Since we know that disjoint F-twins are not adjacent (cf. Proposition 3 and Corollary 2) and the isomorphisms ϕ and ϕ −1 preserve adjacencies, we only need to check that v i−1 and v i are adjacent when one of them (say v i−1 ) belongs to one of the twins (e.g. to H 2 , for later notational simplicity) and v i is not in H 1 ∪H 2 . This means that Distance-related properties , as we aimed to prove. ✷ Proposition 4. Assume that H 1 and H 2 are disjoint F-twin subgraphs of a connected graph G, and let u ∈ V (H 1 ). Then, for any other vertexũ in G the following assertions hold. Distance-related properties Proof. The results follow in a straightforward manner from Lemma 1 since the set of paths from u toũ are in a one-to-one, length-preserving correspondence to the ones that link ϕ(u) to ϕ(ũ), ϕ −1 (ũ) orũ, 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. 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 1. Let H 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. On the classification of F-twin subgraphs Proof. The F-twin relation is obviously reflexive since we may set ϕ as the identity when H 1 = H 2 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 (H 1 , H 2 ) and (H 2 , H 3 ) are pairs of F-twins, and denote by ϕ and ψ the isomorphisms between H 1 and H 2 and between H 2 and H 3 , respectively. One can check that the isomorphism ζ = ψ • ϕ yields On the classification of F-twin subgraphs for all u ∈ V 1 : indeed, this is an immediate consequence of (1) and the corresponding identity for the isomorphism ψ, that is, On the classification of F-twin subgraphs The identities (3) 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 as H 2 ) of subgraphs isomorphic to K 2 . 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 K 2 -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 H 2 simply as the set of edges. 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 non-adjacent 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 1. 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. F-twin vertices within larger F-twin structures Proposition 5. Assume that u 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. F-twin vertices within larger F-twin structures Proof. Let v 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). F-twin vertices within larger F-twin structures 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 F-twin vertices within larger F-twin structures ∈ 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 2 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. ✷ Corollary 4 follows from the case in which the proper F-twin H in Proposition 5 is isomorphic to K 2 . 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 2. F-twin vertices within larger F-twin structures Corollary 4. Vertices and edges admitting proper F-twins define mutually disjoint vertex sets. F-twin vertices within larger F-twin structures We finish this section with a pretty obvious but useful remark following Corollary 4. F-twin vertices within larger F-twin structures Corollary 5. Graphs of order ≤ 5 cannot display simultaneously proper F-twin vertices and proper F-twin edges. Non-trivial 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 Proposition 6 below) accommodates three pairs of F-twin edges with non-empty vertex intersections among classes. In a way, such a 6-cycle is the essential structure to signal this phenomenon. We recall that H 2 denotes the set of subgraphs of G isomorphic to K 2 . Proposition 6. Assume that two elements of H 2 within a graph G belong to different proper F-twin classes and have a common vertex. Then G contains the cycle C 6 as an induced subgraph. Non-trivial vertex set intersections between classes of F-twin edges Proof. Let H 1 and J 1 be two subgraphs in H 2 (namely, isomorphic to K 2 ) which belong to different nontrivial F-twin classes, and denote by H 2 and J 2 two proper F-twins of H 1 and J 1 , respectively (with the corresponding isomorphisms to be denoted by ϕ and ψ). Assume that v belongs to both H 1 and J 1 , and let u and w be the other vertex of H 1 and J 1 , respectively. We claim that ϕ(u) = ψ(w) and that the subgraph induced by {u, v, w, ϕ(v), ϕ(u), ψ(v)} is a 6-cycle. Non-trivial vertex set intersections between classes of F-twin edges To show this, write the F-twin identity for v ∈ H 1 as Non-trivial vertex set intersections between classes of F-twin edges Since w ∈ N (v) and w / ∈ V (H 1 ), we derive Non-trivial vertex set intersections between classes of F-twin edges For later use, notice that this implies ϕ(v) / ∈ V (J 2 ) (that is, ψ(v) = ϕ(v) = ψ(w)), since otherwise there would be two adjacent vertices in J 1 and J 2 (namely, w and ϕ(v)), against Corollary 2. Non-trivial vertex set intersections between classes of F-twin edges Note that v also belongs to J 1 and therefore, analogously, Non-trivial vertex set intersections between classes of F-twin edges and also ψ(v) / ∈ V (H 2 ), that is ψ(v) = ϕ(u) (we already knew that ψ(v) = ϕ(v)). Non-trivial vertex set intersections between classes of F-twin edges Now, restate (5) as ϕ(v) ∈ N (w) and, from the fact that ϕ(v) / ∈ V (J 1 ) (to check this just note that v = ϕ(v) = w, the latter being clear in the light of (5)) and the F-twin identity for w ∈ V (J 1 ), Non-trivial vertex set intersections between classes of F-twin edges derive ϕ(v) ∈ N (ψ(w)) or, equivalently, Non-trivial vertex set intersections between classes of F-twin edges We show in the sequel that, indeed, it is ψ(w) = ϕ(u). Suppose ψ(w) = ϕ(u); as shown above we have ψ(w) = ϕ(v) and both conditions together would mean ψ(w) / ∈ V (H 2 ). Equations (4) and (8) would then yield ψ(w) ∈ N (v). But then v ∈ V (J 1 ) and ψ(w) ∈ V (J 2 ) would be adjacent to each other. We conclude that necessarily ψ(w) = ϕ(u), as claimed. Non-trivial vertex set intersections between classes of F-twin edges The fact that u, v, w, ϕ(v), ϕ(u) = ψ(w), ψ(v) yield a 6-cycle follows from the adjacency relations defined by H 1 , J 1 , (5), H 2 , J 2 , and (6), 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 2 (namely, those connecting u, v with ϕ(u), ϕ(v), since both pairs define the F-twins H 1 , H 2 , respectively, and v, w with ψ(v), ψ(w), which define J 1 and J 2 ; 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 (J 1 ), so that the assumption u ∈ N (w) would imply u ∈ N (ψ(w)) in light of (7), but this is impossible because u ∈ V (H 1 ) and ψ(w) = ϕ(u) ∈ V (H 2 ) 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. T-twins We present in this section the dual concept of T-twin subgraphs, which extends the notion of true twin vertices discussed in subsection 2.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 2) 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 [10, 25] T-twins hold for all u ∈ V 1 . T-twins Again this extends the notion of true twin vertices introduced in subsection 2.2, which are defined by the identities T-twins As in the F-twin case, we use the term proper T-twins for distinct T-twins. T-twins Proof. From (9) it is clear that all vertices in V 2 − V 1 belong to N (u) for all u ∈ V 1 , and this means that V 2 − V 1 is fully connected to V 1 (in particular, to V 1 − V 2 ). Analogously, V 1 − V 2 is fully connected to V 2 . Using both properties together we conclude that the intersection V 1 ∩ V 2 is fully connected to both V 1 − V 2 and V 2 − V 1 and the claim is proved. ✷ Corollary 6. If H 1 and H 2 are disjoint T-twins, then V 1 is fully connected to V 2 . T-twins The following result gives a precise meaning to the claim that the F-twin and T-twin notions are dual to each other. T-twins Theorem 2. Two induced subgraphs H 1 and H 2 of a given graph G are T-twins (resp. F-twins) if and only if H 1 and H 2 are F-twins (resp. T-twins) in G. T-twins Proof. The reader can check in advance that if H is an induced subgraph of G, then H is an induced subgraph of G. Assume now that H 1 and H 2 are T-twins, and let ϕ be the isomorphism arising in Definition 2; one can see that ϕ is also an isomorphism between the complements H 1 and H 2 . Denoting by N (u) the neighborhood of u in G, we need to show that the identities T-twins . We use the fact that T-twins by definition of the complement. These relations yield T-twins (where we have used u ∈ V 1 ) and, analogously, T-twins The relations depicted in (10) then follow from (11) and (12) because H 1 and H 2 are T-twins, which means T-twins Both the case in which H 1 and H 2 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 Theorem 2 since T-twins may have non-empty intersections in the vertex sets and (connected proper) F-twins seemingly not, as stated in Corollary 1. But note that the latter holds as a consequence of Proposition 2 for connected F-twins: now assume V 1 ∩ V 2 = ∅ for (even possibly connected) T-twins H 1 , H 2 . From Proposition 7 it follows that V 1 ∩ V 2 is fully connected to both V 1 − V 2 and to V 2 − V 1 , so that, in the complementary (F-twin) subgraphs H 1 and H 2 , V 1 ∩ V 2 is isolated from both V 1 − V 2 and V 2 − V 1 . This means that V 1 ∩ V 2 induces a set of connected components of both H 1 and H 2 and there is no contradiction with Proposition 2. ✷ Finally, we mention that the T-twin relation also induces a classification in the families H of isomorphic copies of induced subgraphs H. Details are entirely analogous to those in Theorem 1 and are left to the reader. Core-semiperiphery-periphery structures We take now a look back at subsection 2.3; specifically, we provide here a definition of coresemiperiphery-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. subsection 2.1) and we make the remark that the F-twin and T-twin notions introduced in Definitions 1 and 2 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.). A parameterized definition of core-semiperiphery-periphery structures We first note that the condition depicted in item (i) on page 5, defining core vertices, may be recast as the requirement that all of them have eccentricity one. This approach is intimately related to the closeness centrality notion, widely used in network theory [10, 33] . This idea has been previously used in the definition of core vertices within core-periphery structures [27, 34] , and paves the way for the definition presented below. Definition 3. A core-semiperiphery-periphery structure is a 3-partitioned connected graph with the following (non-empty) vertex classes: Definition 3. (i) core vertices, with eccentricity not greater than two; Definition 3. (ii) semiperiphery vertices, adjacent (at least) to a pair of non-adjacent vertices from the other two classes; and (iii) periphery vertices, with degree one. Definition 3. Moreover, the graph is required not to have proper T-twin core vertices or proper F-twin semiperiphery-periphery subgraphs. Definition 3. 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) on page 5). Note that the requirements depicted for each class may be satisfied by vertices from other classes: e.g. a core may have degree one and/or connect a pair of (non-adjacent) 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. Definition 3. 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 [19, 30] ). These ideas define tentative lines for future research. Definition 3. The twin-free conditions stated at the end of Definition 3, 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 subsection 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 subsection 2.3, allowing one to reduce the number of semiperiphery-periphery subgraphs as well. Note also that the the non-adjacency property stated in Corollary 2 captures the fact that twin semiperipheryperiphery 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. Decomposition of CSP structures Definition 3 allows for an explicit description of core-semiperiphery-periphery structures, as detailed below. Decomposition of CSP structures Theorem 3. Core-semiperiphery-periphery structures meeting Definition 3 admit the decomposition described in the sequel. Decomposition of CSP structures 1. The core subgraph C is a join C 0 + C 1 , where Decomposition of CSP structures • C 0 is a complete graph K n 0 ; and • C 1 is any graph of order n 1 without T-twin vertices. Decomposition of CSP structures 2. The core-semiperiphery subgraph is a join C + S, where C has the form described above and S is any graph or order n s without F-twin subgraphs. Decomposition of CSP structures 3. The periphery subgraph P is an empty graph of order n p = n 0 + n s . Periphery vertices are leaves attached in a one-to-one basis either to a vertex from C 0 or from S. Decomposition of CSP structures The orders n c = n 0 + n 1 , n s and n p do not vanish, but either n 0 or n 1 may do. Decomposition of CSP structures Proof. Note in advance that the splitting of core vertices in two groups C 0 and C 1 is defined from the fact that those in C 0 are connected to a periphery vertex whereas those in C 1 are not, as stated in item 3. In this regard, it is obvious that periphery vertices are only connected either to a core (in C 0 ) or to a semiperiphery vertex because of the degree one condition stated in item (iii) of Definition 3; notice that a single K 2 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 C 0 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. Decomposition of CSP structures Regarding the structure of the core subgraph, C 0 is a complete graph (maybe the null one K 0 ) and, moreover, it defines a join with (i.e. it is fully connected to) C 1 , if non-empty, because of the eccentricity requirement for core vertices. Indeed, suppose there is a pair of non-adjacent core vertices, at least one of which is adjacent to a periphery (i.e. at least one of which is in C 0 ): 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 3. Decomposition of CSP structures 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. Decomposition of CSP structures It remains to show that the exclusion of twin structures in Definition 3 is equivalent to the absence of the corresponding twin structures in the core or semiperiphery subgraph, respectively, in the terms stated in this Proposition. Regarding core vertices, note first that C 0 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 C 0 and in C 1 may never be T-twins in the full graph. Additionally, the absence of T-twins in C 1 can be equivalently checked in the full graph or in the core subgraph because of the fact that cores in C 1 are not adjacent to any peripheries and, on the contrary, fully connected to both C 0 and S; this means that the neighborhoods of two C 1 -cores in the full graph differ if and only if these core vertices have different neighbors within C 1 . Decomposition of CSP structures Concerning the equivalence between F-twin structures, let us first assume that two subgraphs H 1 and H 2 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 ∈ V 1 = V (H 1 ). Let ϕ
{'paper_id': '51605768', 'title': 'Twin subgraphs and core-semiperiphery-periphery structures', 's2_url': 'https://api.semanticscholar.org/CorpusID:51605768', 'source': 'S2ORC'}