Semicomplete Compositions of Digraphs

MaRDI QIDQ6339913zbMATH OpenFDO

Authors Yuefang Sun

Publication date 3 May 2020

Abstract: Let $T$ be a digraph with vertices $u_1,dots,u_t$ ($tge2$) and let $H_1,dots,H_t$ be digraphs such that $H_i$ has vertices $u_{i,j_i},1le{j}_{i}le{n}_i.$ Then the composition $Q=T[H_1,dots,H_t]$ is a digraph with vertex set $u_{i,j_i}colon,1leilet,1le{j}_{i}le{n}_i$ and arc set ${\displaystyle }$A(Q)=cup^t_{i=1}A(H_i)cup {u_{ij_i}u_{pq_p}colon, u_iu_pin A(T), 1le j_ile n_i, 1le q_ple n_p}.${\displaystyle }$ The composition $Q=T[H_1,dots,H_t]$ is a semicomplete composition if $T$ is semicomplete, i.e. there is at least one arc between every pair of vertices. Digraph compositions generalize some families of digraphs, including (extended) semicomplete digraphs, quasi-transitive digraphs and lexicographic product digraphs. In particular, strong semicomplete compositions form a significant generalization of strong quasi-transitive digraphs. In this paper, we study the structural properties of semicomplete compositions and obtain results on connectivity, paths, cycles, strong spanning subdigraphs and acyclic spanning subgraphs. Our results show that this class of digraphs shares some nice properties of quasi-transitive digraphs.

This page was built for publication: Semicomplete Compositions of Digraphs

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