The Excluded Minors for Isometric Realizability in the Plane
The Excluded Minors for Isometric Realizability in the Plane
复制标题
平面内等距可实现性的排除未成年人
DOI：
--
复制
发表时间：
2015
影响因子：
0.8
通讯作者：
Antonios Varvitsiotis
中科院分区：
文献类型：
--
作者：
Samuel Fiorini;T. Huynh;G. Joret;Antonios Varvitsiotis
设$G$是一个图，$p在[1，infty]$中.参数f_p（G）$是最小整数k$，使得对所有m$和所有向量v（G）} subseteq mathbb{R}^m$，存在满足$的向量v（G）} subseteq mathbb{R}^k$|r_v-r_w|_p=| q_v-q_w|_p， ext{ for all } vwin E（G）.$$很容易检验f_p（G）$总是有限的，并且它是次单调的。根据Robertson和Seymour的图子式定理，证明了f_p（G）leq k$的排除子式的个数是有限的.
本文确定了f_infty（G）leq 2$的完全排除子式集.两个被排除的子图是$5$顶点上的轮和通过沿着一条边粘合$K_4$的两个副本然后删除该边而获得的图。我们还证明了这两个图是$f_1（G）leq 2$的完全排除子图集。此外，我们给出了一个家庭的例子表明，$f_infty$是无界的类的平面图和$f_infty$是没有界的树宽度的函数。
Let $G$ be a graph and $p in [1, infty]$. The parameter $f_p(G)$ is the least integer $k$ such that for all $m$ and all vectors $(r_v)_{v in V(G)} subseteq mathbb{R}^m$, there exist vectors $(q_v)_{v in V(G)} subseteq mathbb{R}^k$ satisfying $$|r_v-r_w|_p=|q_v-q_w|_p, ext{ for all } vwin E(G).$$ It is easy to check that $f_p(G)$ is always finite and that it is minor monotone. By the graph minor theorem of Robertson and Seymour, there are a finite number of excluded minors for the property $f_p(G) leq k$.
In this paper, we determine the complete set of excluded minors for $f_infty(G) leq 2$. The two excluded minors are the wheel on $5$ vertices and the graph obtained by gluing two copies of $K_4$ along an edge and then deleting that edge. We also show that the same two graphs are the complete set of excluded minors for $f_1(G) leq 2$. In addition, we give a family of examples that show that $f_infty$ is unbounded on the class of planar graphs and $f_infty$ is not bounded as a function of tree-width.
具有多面体范数的有限和无穷小刚度
影响因子：
0.8
作者：
Kitson D
通讯作者：
Kitson D