论文标题
弱的通行凸和正确的间隔图
Weakly toll convexity and proper interval graphs
论文作者
论文摘要
如果$ u_0u_i \ in E（g）$ in（g）$含义$ u_i = u_1 $ = u_1 $ and $ u_ju_k \ in E（g）in（g）$ u_ju_k \ in E（g）$ u_j = u_j = u_j = u_j = u_j = u_j = u__-1} $。如果对于任何两个非附属顶点$ x，y \ in s $ in s $ s $ soby tolly Toll步行，则$ g $的$ s $是$ g $的$ s $是{\它弱的通行费}}。 {\ em弱的TOLL凸度}是在弱的Toll凸点集上定义的图形凸空间。许多研究专门用于确定配备有凸空间的图是{\ em凸几何}。 \ emph {extreme vertex}是凸面$ s $的元素$ x $，因此set $ s \ backslash \ {x \} $也是凸。如果图凸空间满足Minkowski-krein-Milman属性，则据说它是凸的几何形状，该属性指出每个凸形集合是其极端顶点的凸壳。众所周知，弦，托勒密，弱极化图和间隔图可以分别为凸的几何形状，分别相对于单声道，地球，$ M^3 $和TOLL凸度。其他重要的图表也可以以这种方式进行表征。在本文中，我们证明图形是相对于弱的通行凸的凸几何形状，并且仅当它是正确的间隔图时。此外，还研究了一些众所周知的图形不变性，相对于弱的通行凸度。
A walk $u_0u_1 \ldots u_{k-1}u_k$ is a \textit{weakly toll walk} if $u_0u_i \in E(G)$ implies $u_i = u_1$ and $u_ju_k\in E(G)$ implies $u_j=u_{k-1}$. A set $S$ of vertices of $G$ is {\it weakly toll convex} if for any two non-adjacent vertices $x,y \in S$ any vertex in a weakly toll walk between $x$ and $y$ is also in $S$. The {\em weakly toll convexity} is the graph convexity space defined over weakly toll convex sets. Many studies are devoted to determine if a graph equipped with a convexity space is a {\em convex geometry}. An \emph{extreme vertex} is an element $x$ of a convex set $S$ such that the set $S\backslash\{x\}$ is also convex. A graph convexity space is said to be a convex geometry if it satisfies the Minkowski-Krein-Milman property, which states that every convex set is the convex hull of its extreme vertices. It is known that chordal, Ptolemaic, weakly polarizable, and interval graphs can be characterized as convex geometries with respect to the monophonic, geodesic, $m^3$, and toll convexities, respectively. Other important classes of graphs can also be characterized in this way. In this paper, we prove that a graph is a convex geometry with respect to the weakly toll convexity if and only if it is a proper interval graph. Furthermore, some well-known graph invariants are studied with respect to the weakly toll convexity.
