Simple factor graphs associated with split graphs
Adrián Pastine, Victor N. Schvöllner · 2025
Read Simple factor graphs associated with split graphs by Adrián Pastine, Victor N. Schvöllner (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-24252.txt.
Introduction
Victor Nicolas Schvöllner and Adrian Pastine attach a new graph to split graphs. A split graph divides its vertices into a clique and an independent set. The new object is a loopless multigraph called the factor graph. Its vertices are exactly the independent set. Its edges record the 2-switches acting on the special subset S, counted with multiplicity.
An earlier structure by Barrus and West carried more information. The factor graph is more compact by design. It lives only on the independent set. It still determines the 2-switch degree of S. The main theorem is a characterization. An active split graph is indecomposable exactly when its factor graph is connected. That mirrors the Barrus-West result for general graphs. The paper ends with a complete description. It covers the active split graphs whose factor graph is simple and connected.
Catalog record
| CREATOR | Adrián Pastine, Victor N. Schvöllner |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 47 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-24252
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Simple factor graphs associated with split graphs Adrián Pastine, Victor N. Schvöllner Abstract We introduce and study a loopless multigraph associated with a split graph S S : the factor graph of S S , denoted by Φ ( S ) \Phi(S) , which encodes the combinatorial information about 2-switch transformations over S S . This construction provides a cleaner, compact and non-redundant alternative to the graph A 4 ( S ) A_{4}(S) by Barrus and West, for the particular case of split graphs. If Φ ( S ) \Phi(S) is simple and connected, we obtain a precise description of the underlying structure of S S , particularly when Φ ( S ) \Phi(S) is complete, highlighting the usefulness of the factor graph for understanding 2-switch dynamics in balanced and indecomposable split graphs, as well as its 2-switch-degree classification. 1 Introduction For specific graph theoretical concepts not defined here, we refer the reader to [ 2 ] . Let G be a graph. We use the notation V(G) and E(G) to refer to the vertex set and the edge set of G , respectively. The symbol |G| is used to represent |V(G)| , the number of vertices of G . The complement of G is denoted by \overline{G} . The expression H\subset G means that H is a subgraph of G . On the other hand, H\prec G means that H is an induced subgraph of G . If W=\{v_{1},\ldots,v_{n}\}\subset V(G) , we denote by \langle W\rangle_{G} or \langle v_{1},\ldots,v_{n}\rangle_{G} the subgraph of G induced by the vertices in W . The set N_{G}(v)=\{x\in V(G):vx\in E(G)\} , of all neighbors of a vertex v in a graph G , is called the neighborhood of v in G . We usually write N_{v} , instead of N_{G}(v) , if G is clear from the context. Clearly, v\notin N_{G}(v) . The number of edges incident to a vertex v in a graph G , denoted by \deg_{G}(v) , is called the degree of v in G . We usually write d_{v} , instead of \deg_{G}(v) , if G is clear from the context. Obviously, 0\leq d_{v}\leq|G|-1 . If d_{v}=0 , then v is said to be isolated ; if d_{v}=1 , then v is a leaf ; and if d_{v}=|G|-1 (i.e., N_{v}=V(G)-v ), then v is universal . The degree sequence of G is the |V(G)| -tuple whose i -coordinate is \deg_{G}(i) . A clique in G is a subset K of V(G) such that \langle K\rangle_{G} is complete. An independent set of G is a subset I of V(G) such that E(\langle I\rangle_{G})=\varnothing . The clique number of G , denoted by \omega(G) , is the size of a maximum clique in G . The independence number of G , denoted by \alpha(G) , is the size of a maximum independent set of G . Clearly, \omega(G)=\alpha(\overline{G}) , for every graph G . The notation G\approx H means that the graphs G and H are isomorphic. For n\in\mathbb{N} , [n] means \{1,\ldots,n\} . The study of structural transformations on graphs has proven to be a powerful framework for understanding both global and modular properties of graphs. Among these operations, the 2-switch plays a central role in the family of graphs with a given degree sequence. Let G be a graph containing four distinct vertices a,b,c,d such that ab,cd\in E(G) and ac,bd\notin E(G) . A 2-switch in G is a process that removes the edges ab and cd from G and adds the edges ac and bd (see [ 2 ] , page 23). Directly from the definition, it follows that 2-switch preserves the degree sequence. Moreover, it is easy to see that a 2-switch replaces edges between vertices a,b,c,d in G if and only if \langle a,b,c,d\rangle_{G}\approx P_{4},C_{4} or 2K_{2} . The realization graph is the graph whose vertex set is the family of all labeled graphs with the same degree sequence, where two vertices (graphs) G,H are adjacent if and only if H=\tau(G) for some 2-switch \tau (see [ 6 ] , pages 3 and 4). Given any two graphs G,H with the same degree sequence, a basic theorem states that G can be transformed into H by a sequence of 2-switches ( [ 2 ] , page 24). As a consequence, every realization graph is connected. Two fundamental results illustrate the importance of 2-switch transformations and motivate this article: the canonical decomposition theorem by R. Tyshkevich [ 8 ] , and the characterization by Barrus and West [ 1 ] of indecomposable graphs. In order to properly understand the content of both, we need to clarify these preliminary concepts: split graph, Tyshkevich composition, and indecomposable graph. A graph G\neq(\varnothing,\varnothing) is said to be split if V(G) is the disjoint union of two sets, V(G)=K\dot{\cup}I , where K is a clique and I is an independent set. In such a case, we say that the pair (K,I) is a bipartition for G . We call clique vertices the elements of K , and independent vertices the elements of I . The notation (S,K,I) means that we are considering the split graph S together with a bipartition (K,I) for it. Split graphs have been characterized in [ 4 ] as those that do not contain a C_{4},C_{5} or 2K_{2} as induced subgraphs. Further information about the structure of split graphs can be found in [ 3 ] . If (S,K,I) is a split graph and G is a graph disjoint from S , the Tyshkevich composition S\circ G of S and G is defined as the graph whose vertex set is V(S\circ G)=V(S)\cup V(G) and whose edge set is E(S\circ G)=E(S)\cup E(G)\cup\{xy:x\in K,y\in G\}. This operation was introduced by R. Tyshkevich in [ 8 ] . In general, S\circ G is a split graph if and only if G is. A graph G is decomposable if there exist graphs S,H\neq(\varnothing,\varnothing) such that S\circ H=G . Otherwise, G is said to be indecomposable . Next, we can finally cite Tyshkevich’s and Barrus-West’s theorems. Theorem 1.1 (Tyshkevich, [ 8 ] ) . Every graph G can be written as a (Tyshkevich) composition of indecomposable graphs: G=G_{n}\circ\ldots\circ G_{2}\circ G_{1}, where G_{2},\ldots,G_{n} are split. When |G_{r}|\geq 1 for all r , this decomposition is unique up to isomorphism, and neither the order of the factors nor the choice of bipartitions of the split factors can vary. Notice that Theorem 1.1 highlights the importance of indecomposable split graphs as fundamental building blocks for constructing a vast class of larger graphs. On the other hand, Barrus and West studied the graph A_{4}(G) associated with a graph G , with V(A_{4}(G))=V(G) and where two vertices are adjacent if and only if they participate in the same 2 -switch. They proved that A_{4}(G) decomposes as the disjoint union of the corresponding A_{4} -graphs of the Tyshkevich factors of G . As a consequence, G is indecomposable if and only if A_{4}(G) is connected. Theorem 1.2 (Barrus, West, [ 1 ] ) . Let G be a graph and let A_{4}(G) be the graph with V(A_{4}(G))=V(G) , where uv\in E(A_{4}(G)) if and only if we can perform a 2-switch in G involving both u and v