论文标题
挖掘的半完整组成
Semicomplete Compositions of Digraphs
论文作者
论文摘要
Let $T$ be a digraph with vertices $u_1, \dots, u_t$ ($t\ge 2$) and let $H_1, \dots, H_t$ be digraphs such that $H_i$ has vertices $u_{i,j_i},\ 1\le j_i\le n_i.$ Then the composition $Q=T[H_1, \dots, h_t] $是带顶点集的挖掘物$ \ {u_ {u_ {i，j_i} \ colon \，1 \ le i \ le i \ le t，1 \ le j_i \ le n_i \} $和arc set $$ a（q） \ {u_ {ij_i} u_ {pq_p} \ colon \，u_iu_p \ in（t），1 \ le j_i \ le n_i，1 \ le q_p \ le q_p \ le n_p \}。半完整，即每对顶点之间至少都有一个弧。 Digraph组成概括了一些挖掘的家族，包括（扩展）半完整的Digraphs，Quasi-Transistive Digraphs和词典产物二分法。特别是，强的半完整组合物形成了强大的准传输挖掘物的显着概括。 在本文中，我们研究了半完整组合物的结构特性，并获得有关连通性，路径，周期，强大的跨越子图和无环跨度子图的结果。我们的结果表明，这类Digraphs共享了准传输挖掘物的一些不错的属性。
Let $T$ be a digraph with vertices $u_1, \dots, u_t$ ($t\ge 2$) and let $H_1, \dots, H_t$ be digraphs such that $H_i$ has vertices $u_{i,j_i},\ 1\le 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\, 1\le i\le t, 1\le j_i\le n_i\}$ and arc set $$A(Q)=\cup^t_{i=1}A(H_i)\cup \{u_{ij_i}u_{pq_p}\colon\, u_iu_p\in A(T), 1\le j_i\le n_i, 1\le q_p\le n_p\}.$$ 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.
