Absolute retracts of split graphs

Let \(G= G(V,E)\) be a finite, undirected, connected and simple graph. \(G\) is called split if there is a partition \(V= K+ S\) of its vertex set into a complete set \(K\) and a stable set \(S\). This means that split graphs are ``half-way between bipartite graphs and their complements. Especially, \(G\) is a complete split graph if every vertex in \(S\) is adjacent to every vertex in \(K\). A subgraph \(H\subseteq G\) is a retract of \(G\) if there is an edge-preserving map \(r: V(G)\to V(H)\) with \(r(x)= x\) for all \(x\in V(H)\). A member \(G\) of a class \(\mathfrak C\) of graphs is called an absolute retract of the graphs in \(\mathfrak C\) if \(G\) is a retract of any \(M\in {\mathfrak C}\) containing \(G\) as an isometric and isochromatic subgraph. The author establishes structural properties depending on the maximum cardinalities \(\omega\) and \(\alpha\) of the subsets \(K\) and \(S\) of \(V(G)\), respectively, which characterize split graphs (Theorem 2.1). The main result of the paper is the statement that a split graph is an absolute retract of split graphs iff a partition of its vertex set into a stable set and a complete set is unique or it is a complete split graph (Theorem 3.2). Moreover the author proves equivalent conditions for split graphs with given \(\omega\) to be an absolute retract of the class \(\mathfrak C\) of all graphs (Theorem 3.6). And from this, for example, the results follow that every bipartite split graph is an absolute retract or that an \(n\)- chromatic split graph is an absolute retract iff there exists an unique \(n\)-colouring of \(G\). In the last section reflexive split graphs \(G\) are investigated (in this case a loop is added at each vertex of \(G\)). In Theorem 4.1 equivalent conditions for reflexive split graphs are given to be also an absolute retract. From this it follows that the split graphs \(J_ n\), \(n\geq 3\), are precisely the forbidden retracts of the absolute retracts of reflexive split graphs. Here \(J_ n\) is a reflexive graph with \(V(J_ n)= X_ n\cup Y_ n\) where \(X_ n= \{x_ 1, x_ 2,\dots, x_ n\}\) is a complete set and \(Y_ n= \{y_ 1, y_ 2,\dots, y_ n\}\) a stable one, and two vertices \(x_ i\) and \(y_ j\) are adjacent if \(i\neq j\).

Recommendations

Cites work

Cited in

(11)

This page was built for publication: Absolute retracts of split graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1339865)