论文标题
在诱导的路径上的凸几何形状
Convex geometries over induced paths with bounded length
论文作者
论文摘要
在许多情况下已经研究了图凸空间。特别是，一些研究专门用于确定配备有凸空间的图是否是{\ em凸几何}。众所周知，弦和托勒密图分别相对于地球和单声音凸的凸面几何形状。弱极化图，间隔图和正确的间隔图也可以通过这种方式进行表征。在本文中，我们介绍了{\ em $ l^k $ -convexity}的概念，这是对单声音凸的自然限制。令$ g $为图形，$ k \ geq 2 $一个整数。当并且仅当对于任何一对顶点$ x，y $ of $ s $的$ x，y $ of $ s $，每种诱导的长度{\ em y y $ x $ x $ x $ x $ x $和$ y $都完全包含在$ s $ $ s $ $ s $中。 {\ em $ l^k $ -convexity}由$ g $的所有$ l^k $ -convex子集组成。在这项工作中，我们表征了{\ em $ l^k $ -convex几何}（图形相对于$ l^k $ -convexity的凸几何形状），用于$ k \ in \ in \ in \ {2,3 \} $。我们表明，当$ g $是$ g $是$ g $的弦$ g $时，当$ g $是一个和弦$ p_4 $ - free graph时，以及$ l^3 $ -convex几何形状，并且仅当$ g $仅当$ g $是最多三个时的弦图时，它最多可以诱导的宝石满足特殊的“求解”属性，则仅是$ l^2 $ -convex的几何形状。据作者所知，$ l^3 $ -convex几何形状的类是非遗传类几何形状类别的第一个例子。
Graph convexity spaces have been studied in many contexts. In particular, some studies are devoted to determine if a graph equipped with a convexity space is a {\em convex geometry}. It is well known that chordal and Ptolemaic graphs can be characterized as convex geometries with respect to the geodesic and monophonic convexities, respectively. Weak polarizable graphs, interval graphs, and proper interval graphs can also be characterized in this way. In this paper we introduce the notion of {\em $l^k$-convexity}, a natural restriction of the monophonic convexity. Let $G$ be a graph and $k\geq 2$ an integer. A subset $S\subseteq V(G)$ is \textit{$l^k$-convex} if and only if for any pair of vertices $x,y$ of $S$, each induced path of length {\em at most} $k$ connecting $x$ and $y$ is completely contained in the subgraph induced by $S$. The {\em $l^k$-convexity} consists of all $l^k$-convex subsets of $G$. In this work, we characterize {\em $l^k$-convex geometries} (graphs that are convex geometries with respect to the $l^k$-convexity) for $k\in\{2,3\}$. We show that a graph $G$ is an $l^2$-convex geometry if and only if $G$ is a chordal $P_4$-free graph, and an $l^3$-convex geometry if and only if $G$ is a chordal graph with diameter at most three such that its induced gems satisfy a special "solving" property. As far as the authors know, the class of $l^3$-convex geometries is the first example of a non-hereditary class of convex geometries.
