兰州大学机构库 >数学与统计学院
关于区间距离单调图猜想的证明
Alternative TitleThe 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 AbstractThe 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学位论文
Identifierhttps://ir.lzu.edu.cn/handle/262010/225345
Collection数学与统计学院
Recommended Citation
GB/T 7714
王广富. 关于区间距离单调图猜想的证明[D]. 兰州. 兰州大学,2004.
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.