兰州大学机构库 >数学与统计学院
若干曲面多边形图的l1-嵌入
Alternative Titlel1-embeddability of some polygonal graphs on surfaces
王广富
Thesis Advisor张和平
2010-05-26
Degree Grantor兰州大学
Place of Conferral兰州
Degree Name博士
Keyword超立方图 $\lambda$-嵌入 $l_1$-图 $l_1$-嵌入 等距离子图 凸子图
Abstract连通图~$G=(V,E)$~的两个顶点~$u$~和~$v$~之间的距离~$d_{G}(u,v)$~定义为~$G$~中连接~$u$~和~$v$~的最短路的长度. 则~$d_G$~是~$V(G)$~上的一个度量, $(V(G),d_G)$~为~$G$~的伴随度量空间. 一个图~$G=(V,E)$~称为~$l_1$-图~(也称为~$l_1$-嵌入的), 如果存在正整数~$m$, 使得它的伴随度量空间~($V,d_G$)~可以等距离地嵌入到~$l_1$-空间~$(\mathbb{R}^m, d_{l_1})$~中. 即存在从~$V(G)$~到~$\mathbb{R}^m$~的一 个映射~$\phi$~使得对图~$G$~ 的任意两个顶点~$x,y$~都有~$d_G(x, y)= d_{l_1}(\phi(x),\phi(y))$~ 成立. 本文主要研究了开口纳米管在超立方图中的嵌入, 两类规则的牟比乌斯带上的六边形堆砌图的~$l_1$-嵌入, 在粘边运算下 图的~$l_1$-嵌入, 和牟比乌斯带上的四边形堆砌图的~$l_1$-嵌入. 全文共分为五章, 第一章首先介绍了~$l_1$-空间的基本概念, 其次介绍了 ~$l_1$-图的基本理论以及相关问题的研究进展, 再次介绍了特殊的 ~$l_1$-嵌入----等距离嵌入的一些理论. 本章最后罗列了本文得到的主要结果. 在第二章中, 我们研究了开口纳米管在超立方图中的嵌入. 我们证明了在所有的开口纳米管中只有三类特殊的纳米管, 即~$(0,1)$-型, $(1,0)$-型和~$(1,1)$-型的纳米管是可以等距离嵌入到超立方图中的. 在第三章中, 对两类规则的牟比乌斯带上的六边形堆砌图~$H_{2m,2k}$~和 ~$H_{2m+1,2k+1}$, 利用边的~ $l_1$-标号和~ $l_1$-图的识别算法, 我们证明了只有~ $H_{2,2}$~ 和~ $H_{3,3}$~ 是~ $l_1$-嵌入的. 在第四章中, 我们讨论了由两个 ~$l_1$-图通过粘贴一条边所得到的新图的 ~$l_1$-嵌入性. 我们证明了当至少有一个是二部图时, 两个 ~$l_1$-图通过粘贴一条边得到的新图仍是 ~$l_1$-图. 最后我们给出两个例子说明两个非二部的~ $l_1$-图通过粘贴一条边所得到的新图可能是一个~$l_1$-图, 也可能不是 一个~$l_1$-图. 在第五章中, 我们主要研究了牟比乌斯带上的四边形堆砌图的~$l_1$-嵌入性. 我们考查了牟比乌斯带和闭圆盘上的四边形堆砌图的平衡数, 得到牟比乌斯带和闭圆盘上的四边形堆砌图的平衡数分别是~0~和~4. 其次我们讨论了围长为~ 3~的~$l_1$-嵌入的牟比乌斯带上的四边形堆砌图, 并得到了其中的两个禁止子图. 对于围长为~4~的~$l_1$-嵌入的牟比乌斯带上的四边形堆砌图, 我们证明了其最短的非零伦圈是等距离圈~(也是凸的)~且是唯一的; 进一步, 沿着这个最短的非零伦圈``剪开"后所得到的新图的每个分支都是一个平面方格图. 最后我们构造了无穷多个围长为~4~的~$l_1$-嵌入的牟比乌斯带上的四边形堆砌图.
Other AbstractThe distance $d_G(u,v)$ between two vertices $u$ and $v$ of a connected graph $G=(V,E)$ is defined as the length of a shortest path connecting them in $G$. So $d_G$ is a metric on $V(G)$, and $(V(G),d_G)$ is a graphic metric space associated with $G$. A graph $G=(V,E)$ is called an $l_1$-graph (sometimes called $l_1$-embeddable),if there exists a positive integer $m$,such that its graphic metric space $(V, d_G)$ can be isometrically embedded into the $l_1$-space $(\mathbb{R}^m, d_{l_1})$,that is,there exists a mapping $\phi$ from $V(G)$ onto $\mathbb{R}^m$ such that $d_G(x, y)= d_{l_1}(\phi(x),\phi(y))$ for any two vertices $x,y$ of $G$. In this thesis, we consider the embeddability of open-ended nanotubes into hypercubes, $l_1$-embeddability of two classes of regular M\"{o}bius hexagonal tiling graphs, the $l_1$-embeddability of graphs under edge-gluing operation, and the $l_1$-embeddability of M\"{o}bius quadrilateral tiling graphs. This thesis consists of five chapters. In Chapter one, firstly we introduce the background of the $l_1$-space; secondly, we introduce the basic theory of $l_1$-graphs and the correlative research problems and their developments; thirdly, we introduce some theory of a special $l_1$-embedding----isometric embedding; finally, we present the main results obtained in the following chapters. In Chapter two, we study the embeddability of open-ended nanotubes into hypercube. Among all the open-ended nanotubes only three classes of special nanotubes, i.e., $(0,1)$-type, $(1,0)$-type and $(1,1)$-type nanotubes can be isometrically embedded into hypercubes. In Chapter three, for the two classes of regular M\"{o}bius hexagonal tiling graphs $H_{2m,2k}$ and $H_{2m+1,2k+1}$, by using $l_1$-labels of edges and the recognition algorithm of $l_1$-graphs, we obtain that only $H_{2,2}$ and $H_{3,3}$ are $l_1$-embeddalbe. In Chapter four, we discuss the $l_1$-embeddability of graphs obtained from two $l_1$-graphs by gluing an edge. Firstly, we prove that if at least one of the two graphs is bipartite, then the new graph obtained from them by gluing an edge is also an $l_1$-graph. Then, we give two examples to show that for two nonbipartite $l_1$-graphs, the new graph obtained from them by gluing an edge may be an $l_1$-graph or may not be an $l_1$-graph. In Chapter five, we mainly study the $l_1$-embeddability of M\"{o}bius quadrilateral tiling graphs. First of all, we investigate the balance number of quadrilateral tiling graphs on t...
URL查看原文
Language中文
Document Type学位论文
Identifierhttps://ir.lzu.edu.cn/handle/262010/224766
Collection数学与统计学院
Recommended Citation
GB/T 7714
王广富. 若干曲面多边形图的l1-嵌入[D]. 兰州. 兰州大学,2010.
Files in This Item:
There are no files associated with this item.
Related Services
Recommend this item
Bookmark
Usage statistics
Export to Endnote
Altmetrics Score
Google Scholar
Similar articles in Google Scholar
[王广富]'s Articles
Baidu academic
Similar articles in Baidu academic
[王广富]'s Articles
Bing Scholar
Similar articles in Bing Scholar
[王广富]'s Articles
Terms of Use
No data!
Social Bookmark/Share
No comment.
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.