Simple factor graphs associated with split graphs

Abstract

We introduce and study a loopless multigraph associated with a split graph $(S,K,I)$: its factor graph $\Phi (S,K,I)$, whose vertex set is $I$ and whose edges, counted with multiplicity, record the 2-switches acting on $S$. In contrast with the $A_4$-structure ${\mathcal{A}}_4(S)$ introduced by Barrus and West, the factor graph is supported on the independent set alone; it is therefore more compact and, although it retains less information, it still determines the 2-switch-degree of $S$. We show that an active split graph is indecomposable if and only if its factor graph is connected, an analogue for split graphs of the Barrus--West characterization of indecomposable graphs. Finally, we describe completely the active split graphs whose factor graph is simple and connected.

arXiv commentRevised and resubmitted to Discrete Mathematics following referee report