论文标题
关于互补棱镜的一般职位数量
On the general position number of complementary prisms
论文作者
论文摘要
图$ g $的一般职位编号$ {\ rm gp}（g）$是最大的顶点$ s $的基数，因此$ s $的元素不在$ s $的其他两个元素之间。 $ g $的互补棱镜$ g \ overline {g} $是$ g $的不相交联合及其补充$ \ overline {g} $形成的图，通过添加它们之间的完美匹配的边缘。证明$ {\ rm gp}（g \ overline {g}）\ le n（g） + 1 $如果连接$ g $，并且$ {\ rm gp}（g \ overline {g}）\ le n（g）$如果$ g $ disconnected disconnected。图形$ g $为$ {\ rm gp}（g \ overline {g}）= n（g） + 1 $保留，只要连接$ g $和$ g $ g $和$ g overline {g} $，都可以进行特征。证明了$ {\ rm gp}（g \ overline {g}）$的尖锐下限。如果$ g $是连接的两分图或拆分图，则$ {\ rm gp}（g \ overline {g}）\ in \ {n（g），n（g）+1 \} $。 $ {\ rm gp}（g \ overline {g}）= n（g）+1 $保留的连接两分图和块图。构建了一个块图的家族，其中$ {\ rm gp} $ - 其互补棱镜的数量比其订单小。
The general position number ${\rm gp}(G)$ of a graph $G$ is the cardinality of a largest set of vertices $S$ such that no element of $S$ lies on a geodesic between two other elements of $S$. The complementary prism $G\overline{G}$ of $G$ is the graph formed from the disjoint union of $G$ and its complement $\overline{G}$ by adding the edges of a perfect matching between them. It is proved that ${\rm gp}(G\overline{G})\le n(G) + 1$ if $G$ is connected and ${\rm gp}(G\overline{G})\le n(G)$ if $G$ is disconnected. Graphs $G$ for which ${\rm gp}(G\overline{G}) = n(G) + 1$ holds, provided that both $G$ and $\overline{G}$ are connected, are characterized. A sharp lower bound on ${\rm gp}(G\overline{G})$ is proved. If $G$ is a connected bipartite graph or a split graph then ${\rm gp}(G\overline{G})\in \{n(G), n(G)+1\}$. Connected bipartite graphs and block graphs for which ${\rm gp}(G\overline{G})=n(G)+1$ holds are characterized. A family of block graphs is constructed in which the ${\rm gp}$-number of their complementary prisms is arbitrary smaller than their order.
