临界h棱连通图的最大棱数及最大图的结构(Ⅱ)——指数不小于h+3的情形

本文通过临界h棱连通图的指数概念,讨论了指数不小于h+3的p阶临界h(≥4)棱连通图的最大棱数问题。     

关于指数为（h＋1）的临界h棱连通图的最大棱数

令N 是正整数集合.设p,h∈N,令(?)_h~1(p)是其指数不为1的p 阶临界h 棱连通图集合,f_h~(?)(p)是一个确定的二元函数.本文证明如下结论:设h,p_0∈N,p≥4h-2,h≥4且设G 是(?)_h~1(p_0)中具有最大棱数且指数为h+1的图.如果对任何p∈N 且p相似文献   

判定k-点连通图与k-边连通图极小性的定理

主要研究了判定ｋ－点连通图是极小的充要条件和ｋ－边连通图是极小的必要条件。     

每点都与3度点相邻的最大临界3棱连通图的结构

没G=(V,E)是3棱连通图,若对每个x∈V(G),G-x 不是3棱连通的,则称G 为临界3棱连通图.p 阶临界3棱连通图的全体记为(?)_3(p),G∈(?)_3(p)称为最大的,如果不存在H∈(?)_3(p),使|E(H)|>|E(G)|.本文给出每个点都与3度点相邻的p 阶最大临界3棱连通图的结构.     

有限简单连通图的棱凝聚度上界的估计

本文证明了有限简单连通图的棱凝聚度的最小值上界之一为ｍｉｎ｛λ（Ｇ）－Ｋ（Ｇ）＋１，［λ（Ｇ）／２］｝，从而给出了图的棱凝聚度最小值上界的进一步估计     

n棱伞图的k着色计数问题

定义了一类新的由图论中的圈图与轮图组成的n棱伞图,通过分步和分类两大计数原理及二项式反演公式,得到了n棱伞图的k着色的计数公式.     

关于k临界n连通图

介绍k临界n连通图的性质和已经证明以及尚未证明的一些猜想。     

连通图中圈数

用|V（G）|、|E（G）|和f（G）分别表示图G的顶点数、边数和圈数．设F（k）＝｛f（G）;G是满足|E（G）|－|V（G）|＝k的无环连通图｝,n（k）＝minF（k）和N（k）＝maxF（k）．证明了下述结果：（1）n（k）＝k＋1;（2）N（k）≤2k+1;（3）对每个整数k≥1,N（k）≥2k＋k（k－1）＋1且当1≤k≤4时等式成立;（4）对每个整数k≥1是奇数时,N（k）≥2k3;当k≥2是偶数时,     

图的连通控制的增强数

给出了一些图类确切的连通控制的增强数,并给出图的连通控制增强数的一些紧的界,进而推广了Hedetniemi和Laskar的一个结果.     

关于树与完全图的笛卡尔乘积图的连通测地数

给出了两个非平凡图,确定了树与完全图的笛卡尔乘积图的连通测地数.测地数与连通测地数是图的两个重要参数.树与完全图的笛卡尔乘积图的测地数已被确定.     

具有最小子树数目的单圈图与双圈图

运用删边缩边原理,探讨了3种减小子树数目的变形,每一种变形都能比较一组图的子树数目的大小。在利用这些变形的基础上,刻画了具有最小子树数目的单圈图和双圈图的结构。     

单圈图及其与完全图联图的全染色

研究单圈Cn’,一类单圈图G以及它们与完全图Km联图Cn’∨Kn,G∨Kn的全染色问题.借助于已知的完全图全染色的相关引理以及归纳总结的方法得出了Cn’,G的全色数以及其与完全图联图Cn’∨Kn,G∨Kn的全色数,从而验证了对这类图全染色猜想的正确性.     

蛛网图的邻强边染色

蛛网图是一个重要的网络拓扑结构,研究它的染色对于网络权的分配和通信网络的设计有重要的指导作用.利用穷举法和组合分析法讨论了蛛网图的邻强边染色,得到了蛛网图的邻强边色数.     

连通图二次幂图的Hamilton连通性

本文对圈和树的二次幂图的 Hamilton 连通性进行了研究。     

图的色数与其补图边色数的关系

本文对图的点色数与其补图边色数的关系进行了考察.     

网格图的剖分图的强边染色

研究了3种网格图的剖分图的强边着色.网格图的剖分图是指用一个长为2的路去替换网格图的每条边.具体给出了六边形、四边形、三角形的网格剖分图的一种着色方法,以此为基础证明了Sχ′(Γs6)=4,Sχ′(Γs4)=5,Sχ′(Γs3)=7.