本文仅考虑简单图.用 G表示一个图.图中过每个顶点的圈,称为图的哈密尔顿圈.如果图中含有一个哈密尔顿圈,则该图是哈密尔顿的.哈密尔顿圈问题是是图论中的经典问题,鉴于哈密尔顿问题与四色问题,极值问题,图的结构理论等问题的紧密联系,在网络通讯结构,复杂性理论的广泛应用,哈密尔顿问题在1970年后得到了广泛的研究.由于判定一个图是否存在哈密尔顿圈是 NP-完全的.因此,研究哈密尔顿问题的充分条件成为了一个主流方向.　　 著名图论学家 Dirac在1952年证明了如果图的每个点的度都至少等于该图的顶点数的一半,则这个图是哈密尔顿的.通常,用这个方法给出一个图是哈密尔顿的充分条件需要包含图的一些度条件.1952年以后,不同的研究者得到了很多对 Dirac定理推广的结果.到目前为止,这个领域一直是哈密尔顿图理论和极值图理论研究的核心问题之一.Matthews和 Sumner[101]与 Li,Lu和 Liu[76]分别给出了2-连通和3-连通无爪图中存在哈密尔顿圈的度条件.由于在证明中,我们发现一些点的度很小,希望用一些较大的点度来代替这些小的点度来构造一个长圈,这个思路形成了隐度这一概念,它是由 Zhu,Li和 Deng[141]首先提出的.设 G是一个图,v是图中一个度为k+1的点,其中k≥0.记 N1(v)=N(v)={x∈V(G)｜sv∈E(G)},N2(v)={x∈V(G)｜d(x,v)=2},其中 d(x,v)是图中最短(x,c)-路的长度.当 N2(v)≠￠时定义 M2v=max{d(x)｜x∈N(v)}.定义 d1v≤d2v≤...≤dkv≤dkv+1≤...是 N1(v)∪N2(v)中所有点的一组度序列.记点 v的隐度为d1(v):当dkv+1>M2v或 N2(v)=￠时,d1(v)=max{dkv+1,k+1}；否则 d1(v)=max{dkv,k+1}.由隐度的定义显然可知对每个点v,d1(v)≥d(v).Zhu,Li和 Deng在[141]中给出了图中哈密尔顿圈存在的最小隐度条件,它是对Dirac定理的一个推广.在第二章,我们在Matthews和Sumner[101]给出的定理的条件下,得到了一个2-连通无爪图中存在哈密尔顿圈的隐度条件.　　 可圈集是对哈密尔顿图的另一个推广.令 S是图的一个点子集,如果存在一个圈包含 S里面的所有点,则称S在图中是可圈的.关于哈密尔顿图的一个研究方向是用独立集的度和与邻域条件给出一个图是哈密尔顿的充分条件,一些相关的结论出现在文献[13],[36],[56],[106]和[118]中.显然,如果 S=V(G),则“S是可圈的”等价于“G是哈密尔顿的”.自然的,人们将哈密尔顿性推广到图的可圈性.用独立集的度和与邻域条件保证图的可圈性是另一个研究方向,这方面的相关结果可参考[11],[18],[42],[56]和[107].我们在第三章中讨论了四个独立点的度和与邻域条件来保证可圈性.　　 若图 G的每条边都染上颜色,则称 G为边染色图.给定一个边染色图 G,关联于顶点 v的不同颜色的边的数目,称为顶点 v的色度.边染色图中的子图,如果所有边的颜色都不相同,我们称之为彩色子图.这类子图的研究得到了广泛关注.图的圈和路是图论中的基础研究领域,因此边染色图中的彩色圈和彩色路就成了一个重要的研究方向.在第四章,我们研究了边染色图中的彩色圈和彩色路.Li和 Wang[84]证明了当 dc(v)≥n+1/2时存在彩色圈.在[30]中,Chen和Li给出了如下猜想:如果边染色图中的每一个点 v满足 dc(v)≥k≥3,则图G含一条至少长为k-1的彩色路.在同篇论文中,他们还证明了3≤k≤7的情形.在[31]中证明了当 dc(v)≥k≥7时,图G有条至少长为[2k/3]+1的彩色路.我们讨论了不含三角形的图和二部图中圈长为4的彩色圈存在的色度条件,并讨论了二部图中彩色路的存在性.　　 论文的最后一部分研究了图论中的另一领域,化学图论.实际上,若仅考虑原子间的连接关系,则用图或树状图来表示分子的结构是一件非常自然的事情.1975年的诺贝尔化学奖获得者 Vlado Prelog教授曾多次强调过将图论应用于化学的重要性.化学中的分子结构、分子中的各层的能量都可以用图来表示.图和化学物质之间有两种对应关系,在化学中有很多应用:(i)一个图对应于一个分子,即顶点代表原子而边表示化学共价键(这种图可称为结构图或构造图).(ⅱ)图对应于一种反应混合物,顶点代表化学物质而边表示这些物质间的转化(这种图可称为反应图).前一类图推动了Cayley去发展一种链烷的构造异构体计数的方法；后来它又导致 Polya发现了他的强有力的计数定理,这个定理甚至可用于立体化学问题.有了化学这样一个繁殖的基地,图论被广泛用来解决化学问题.近几十年来,化学从图论的进展中得到了很多收益.化学分子图的拓扑指标理论是化学图论的一个重要研究分支.1975年著名化学家Randi(c)提出了连通性指标,即 Randi(c)指标.因为这一重要的拓扑指标和分子的物理化学性质(如分子的沸点、表面积等)和药物学性质之间有着紧密的联系,近年来得到了特别地重视.图 G的Randi(c)指标定义为R(G)=∑uv1/d(u)d(v).目前已有四部 Randi(c)指标方面的专著[52,71,72,88].Bollobás和Erd(o)s[12]给出了不含孤立点的n阶图的Randi(c)指标的紧的下界 n-1.在[38],[46],[90],[109]和[133]中,给出了一些特殊图类中 Randi(c)指标的上下界.Randi(c)指标与图论中的度、匹配数、围长、直径等很多参数相关联.在[5]中,Aouchiche,Hansen和Zheng提出了一个有关围长的猜想,我们证明了该猜想在单圈图和双圈图时成立.此外我们还研究了双圈图中含匹配和完美匹配时Randi(c)指标的界.