| 关于区间距离单调图猜想的证明 |
| Alternative Title | The Proof of the Conjecture of Interval Distance Monotone Graphs
|
| 王广富 |
| Thesis Advisor | 张和平
|
| 2004-05-10
|
| Degree Grantor | 兰州大学
|
| Place of Conferral | 兰州
|
| Degree Name | 硕士
|
| Keyword | 区间
距离单调
区间单调
区间距离单调
Hamming图
超立方图
|
| Abstract | 图$G$的两顶点$u$和$v$之间的区间$I(u,v)$是指$u$和$v$之间所有最短路上的点构成的集合. 图$G$称为区间距离单调图,如果对$G$的任意两点$u$和$v$, 区间$I(u, v)$导出一个距离单调图. 在本文中, 我们证实了M. A {\i}der 和M.Aouchiche提出的猜想:图$G$是区间距离单调的当且仅当它的每个区间要么是一条路,要么同构于一个偶圈,要么同构于一个超立方图. Burosch 等给出了是距离单调而不是区间单调的, 是区间单调而不是距离单调的例子,我们则从整体上讨论了区间单调、距离单调和区间距离单调三者之间的关系,最后用区间距离单调性给出了Hamming图的一个等价刻画. |
| Other Abstract | The interval I(u, v) between two vertices $u$ and $v$ of a graph $G$ is the set of vertices on shortest paths between $u$ and $v$. A simple connected graph $G$ is said to be interval distance monotone if for any two vertices $u$ and $v$ in $G$, the interval $I(u, v)$ induces a distance monotone graph. In this paper, we prove that the conjecture of M. A der and M. Aouchiche: A graph $G$ is interval distance monotone if and only if each of its interval is either isomorphic to a path or to an even cycle or to a hypercube. Burosch et al. had gived one example which is distance monotone but not interval monotone, the other example which is interval monotone but not distance monotone. we generally discuss the relationships among distance monotone, interval monotone and interval distance monotone and characterize Hamming graph by the notion of interval distance monotonicity finally. |
| URL | 查看原文
|
| Language | 中文
|
| Document Type | 学位论文
|
| Identifier | https://ir.lzu.edu.cn/handle/262010/225345
|
| Collection | 数学与统计学院
|
Recommended Citation
GB/T 7714 |
王广富. 关于区间距离单调图猜想的证明[D]. 兰州. 兰州大学,2004.
|
Items in the repository are protected by copyright, with all rights reserved, unless otherwise indicated.
