| 【中文题名】 | 关于图的测地数的一些结果 |
| 【英文题名】 | Some Results on the Geodetic Number of Graphs |
| 【学科专业】 | 运筹学与控制论 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2006-9-11 |
| 【中关键词】 | 凸集,测地集,测地谱,测地数,弦图,竞赛图 |
| 【英关键词】 | Convex set,Geodesic set,Geodetic spectrum,Geodetic number,Chordal graph,Tournament,Strong connected, |
| 【分类导航】 | 数理科学和化学>数学>代数、数论、组合理论>组合数学（组合学）>图论> |
| 【论文摘要】 | 图的测地数以及测地谱是揭示图的结构特性的一个重要参数。它可以看作凸集概念在图论中的某种推广。
本文主要介绍图和有向图的测地数的研究进展和本人在这方面所做的工作，主要的工作包括以下四个部分：(1)无向图及其定向图的测地集的一些性质；(2)下测地数g~-(G)的一些界；(3)对问题g(G)≤g~+(G)的努力以及从中得到的二者的一些界；(4)特殊定向规则下的几类特殊图的测地谱的探讨。
本文的主要结果有：
1．测地集与点割集，连通分支间的一些关系。
2．对于连通图G的任意一棵生成树T，下测地数g~-(G)不超过树T叶子的个数l(T)。
3．对于弦图，不含3圈的图，以及色数x(G)≤4或x(G)≥n-4的n阶连通图，都有g(G)≤g~+(G)。
4．当n充分大时，几乎所有的n阶竞赛图(?)的测地数g((?))≤[n/2]+1
且当n≥3时，n阶完全图的强连通定向测地谱
S_s(K_n)(?){2，3，…，[n/2]} |
| 【论文题纲】 |
|
论文摘要 |
5-6 |
|
ABSTRACT |
6-8 |
|
第一章 引言 |
8-12 |
|
§1.1 图的一些基本概念 |
8-10 |
|
§1.2 图的测地数的由来与相关概念 |
10-12 |
|
第二章 关于测地集的一些性质 |
12-15 |
|
§2.1 测地集以及测地数的一些已有结果 |
12-13 |
|
§2.2 点割集、连通分支与测地集 |
13-15 |
|
第三章 图的测地数及其上、下测地数 |
15-24 |
|
§3.1 下测地数的一些界 |
15-17 |
|
§3.2 关于问题g(G)≤g~+(G)及其相应的一些界 |
17-24 |
|
第四章 几类特殊图在限制定向下的测地谱 |
24-31 |
|
§4.1 无有向圈定向下几类特殊图的测地谱 |
24-26 |
|
§4.2 强连通定向下几类图的测地谱 |
26-31 |
|
作者申请硕士学位期间完成的工作 |
31-32 |
|
致谢 |
32 |
|
| 【DOI】 | LunWen.ID:2.2008.11677 |
