Induced path and cycles in factor graphs of split graphs
Victor N. Schvöllner, Adrián Pastine · 2026
Read Induced path and cycles in factor graphs of split graphs by Victor N. Schvöllner, Adrián Pastine (2026) 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-2603-14061.txt.
Introduction
Schvöllner and Pastine study induced paths and cycles in factor graphs built from split graphs. The factor graph encodes how 2-switch moves reshape the split graph. Induced paths force chains of neighborhood inclusions among their vertices. Degrees along such a path then change in a monotone way. As a result, induced cycles can have length at most four. Only the first or last edge of an induced path can be simple, which bounds the graph's diameter.
Catalog record
| CREATOR | Victor N. Schvöllner, Adrián Pastine |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 20788 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.14061
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Induced path and cycles in factor graphs of split graphs Victor N. Schvöllner, Adrián Pastine Abstract Let S S be a split graph with bipartition ( K , I ) (K,I) and let Φ ( S ) \Phi(S) be the factor graph associated with S S , a multigraph on I I whose encodes the combinatorial information about 2-switch transformations in S S . We study induced paths and cycles in Φ ( S ) \Phi(S) and show that they impose strong structural restrictions on the neighborhoods in S S of the corresponding vertices. In particular, induced paths generate chains of neighborhood inclusions which force a monotone behavior of the degrees (in S S ) of their vertices along the path. As a consequence, we prove that induced cycles in Φ ( S ) \Phi(S) have length ≤ 4 \leq 4 . Finally, we show that in any induced path only the first or the last edge can be simple, which yields an upper bound for the diameter of Φ ( S ) \Phi(S) in terms of the 2-switch-degree of S S . 1 Introduction Let G be a graph. We use V(G) and E(G) to refer to the vertex set and the edge set of G , respectively. As usual, |G| denotes the order of G . The degree sequence of a graph G with V(G)=[n]=\{1,\dots,n\} is the n -tuple (d_{1},\dots,d_{n}) , where d_{v} is the degree of vertex v in G . Structural transformations on graphs play a fundamental role in the study of graph classes defined by degree constraints. Among these operations, the 2-switch is one of the most important tools for navigating the family of graphs that share a common degree sequence. Given vertices a,b,c,d such that ab,cd\in E(G) and ac,bd\notin E(G) , the 2-switch replaces the edges ab,cd with ac,bd . This operation preserves the degree sequence of the graph and has been widely used in several contexts. For closely related results, see [ 1 , 6 , 8 , 9 ] . A classical result highlighting the importance of these transformations is the canonical decomposition theorem of Tyshkevich (see [ 10 ] ), which describes how graphs can be decomposed into indecomposable factors with respect to certain composition operations. In particular, indecomposable graphs appear as fundamental building blocks from which large classes of graphs can be constructed. Understanding the structure of these components and the transformations acting on them is therefore a natural and important problem. In this direction, Barrus and West introduced in [ 2 ] the graph A_{4}(G) associated with a graph G . The vertices of A_{4}(G) are the vertices of G , and two vertices are adjacent whenever they participate in the same 2-switch of G . One of their main results shows that A_{4}(G) decomposes as the disjoint union of the corresponding A_{4} -graphs of the Tyshkevich factors of G . As a consequence, a graph G is indecomposable if and only if A_{4}(G) is connected. This connection between 2-switch transformations and structural decomposition provides a useful framework for studying graph realizations. Split graphs constitute a particularly well-behaved class within this context. A graph G is called a split graph if its vertex set can be partitioned as K\dot{\cup}I , where K is a clique and I is an independent set. When such a partition is fixed, we write (S,K,I) to emphasize that the split graph S is considered together with a specific bipartition. Split graphs appear naturally in several areas of graph theory and are widely studied in the literature (see [ 3 , 4 , 5 , 11 ] ). Motivated by the study of 2-switch dynamics in split graphs and inspired by Barrus and West’s A_{4} , in [ 7 ] the authors introduced the factor graph of a split graph (S,K,I) , denoted by \Phi(S) , or simply by \Phi , if S is clear form the context. This is a loopless multigraph with V(\Phi)=I , such that there is an edge joining u and v in \Phi for each 2-switch acting on u and v . Thus, E(\Phi) is a multiset and each edge of \Phi has a multiplicity. In this way, \Phi(S) encodes the combinatorial information associated with 2-switch transformations on S . In particular, the size of \Phi(S) (counting multiplicities) equals the 2-switch-degree of S , i.e., the number of 2-switches acting on S (see [ 6 ] ). Moreover, \Phi(S) avoids certain redundancies present in the construction of A_{4}(S) , providing a more compact description of the 2-switch structure in the special case of split graphs. Several structural properties of \Phi were established in [ 7 ] , including relationships between the multiplicities and the neighborhoods in S of the corresponding vertices. In particular, these results show that the factor graph captures delicate inclusion relations between neighborhoods in the split graph and can be used to obtain structural information about S , especially when \Phi(S) is simple or connected. The purpose of this article is to further investigate the structure of \Phi by focusing on its induced paths and cycles. Understanding these configurations reveals strong constraints on how neighborhoods in the split graph may be arranged. This article is divided into 4 sections. In Section 2 we study induced paths in \Phi . We note that the presence of an induced path P in \Phi determines certain inclusion chains in the neighborhoods in S of the vertices of P . Thanks to this, we also see how the degree in S of the vertices of P tends to increase along P , moving from one end to the other. These results are then applied in Section 3 to study the length of induced cycles in \Phi (since these contain induced paths), establishing that it is at most 4. Subsequently, in Section 4 , we return to induced paths, now analyzing the multiplicity of their edges. We find that only the first or the last edge can be simple (i.e., of multiplicity 1). This result allows us to conclude the section with an interesting upper bound for the diameter of \Phi(S) , in terms of the 2-switch-degree of S . Finally, in Section 5 , we summarize the main results of the paper and discuss possible directions for future research. 2 Induced paths in \Phi(S) From now on, we only concern about a split graph S and its associated factor graph \Phi(S) . So, the symbol N_{i} will always refer to the (open) neighborhood in S of the vertex i or v_{i} . Similarly, the symbol d_{i} will always refer to the degree in S of the vertex i or v_{i} . On the other hand, we denote by N_{\Phi}(i) the (open) neighborhood in \Phi(S) of the vertex i or v_{i} , and by \sigma_{uv} the multiplicity of the edge uv in \Phi(S) . In [ 7 ] the authors show that \sigma_{uv}=(d_{u}-\eta_{uv})(d_{v}-\eta_{uv}), where \eta_{uv}=|N_{u}\cap N_{v}| , and subsequently derive from it the following proposition. Proposition 2.1 ( [ 7 ] ) . Let S be a split graph. Then: 1. \sigma_{uv}=0 (i.e., uv\notin E(\Phi) ) and d_{v}\leq d_{u} if and only if N_{v}\subset N_{u} ; 2. \sigma_{uv}=0