共查询到19条相似文献,搜索用时 78 毫秒
1.
1988年,Vince定义了图的色数的一个推广——图的星色数,本文研究了有围长限制或有最大度限制的临界图的星色数,得到了三个新结果。 相似文献
3.
4.
6.
7.
如果图$G$的一个正常染色满足染任意两种颜色的顶点集合导出的子图是一些点不交的路的并,则称这个正常染色为图$G$ 的线性染色.图$G$的线性色数用lc$(G)$表示,是指$G$的所有线性染色中所用的最少颜色的个数. \qquad 证明了: 对于每一个最大度为$\Delta(G)$围长为$g(G)$的非负特征图$G$,若存在一个有序对$(\Delta,g)\in\{(13,7),(9,8),(7,9),(5,10), (3,13)\}$, 使得$G$满足$\Delta(G)\ge\Delta$且$g(G)\ge g$,则lc$(G)=\lceil \frac {\Delta(G)}2\rceil+1$. 相似文献
8.
广义随机交集图是一类重要的随机图模型,它是E-R随机图的变种,被广泛用于复杂社会网络的研究中.本文研究了在顶点度的期望趋于无穷的情况下,广义随机交集图的度分布.我们对二项模型给出了中心极限定理,并且对一致模型给出了极限定理. 相似文献
9.
10.
11.
一个有向图D称为本原的,如果存在某个正整数k,使得对于D中的任一点x到任一点y都有长为k的途径,这样的正整数k中的最小者称为D的本原指数,作为本原指数概念的推广,R.A.Brualdi和柳柏濂于1990年引入了本原有向图的广义本原指数的新概念,本文给出了对称本原图的集指数的一些性质,并对本原简单图的广义上指数的极图进行了完全刻划。 相似文献
12.
图的限制性边连通度等于其最小边度的一个充分条件 总被引:6,自引:1,他引:5
设G是有限简单无向图.D,g和δ分别表示G的直径,围长和顶点最小度,本文证明,如果D≤g-2,且δ≥3,那么λ'=ξ,这里λ'=λ'(G)和ξ=ξ(G)分别表示G的限制性边连通度和最小边度,它在条件和结论两个方面都改进了已有的研究结果。 相似文献
13.
14.
图的边覆盖染色中的分类问题(英文) 总被引:1,自引:0,他引:1
设 G是一个图 ,其边集是 E( G) ,E( G)的一个子集 S称为 G的一个边覆盖 ,若 G的每一点都是 S中一条边的端点 .G的一个 (正常 )边覆盖染色是对 G的边进行染色 ,使得每一色组都是 G的一个边覆盖 ,使 G有 (正常 )边覆盖染色所需最多颜色数 ,称为 G的边覆盖色数 ,用χ′c( G)表示 .已知的结果是对于任意简单图 G,都有 δ- 1≤ χ′c( G)≤ δ,δ是 G的最小度 .若 χ′c( G) =δ,则称 G是 CI类的 ;否则称为 CII类的 .本文主要研究了平面图及平衡的完全 r分图的分类问题 相似文献
15.
刘彦佩教授给出了平面图的辅助图.推广平面图的辅助图到射影平面,给出标号图的射影平面性的如下刻画:给定标号图$G$对应的辅助图是平衡的当且仅当$G$是射影平面图. 相似文献
16.
吴举林 《高校应用数学学报(A辑)》1991,6(3):420-426
本文研究图的导出森林独立系统.在这个独立系统中,独立集是指导出子图不含圈的点子集.文中证明了图G的导出森林独立系统是拟阵当且仅当G是块森林.文中同时给出了在强弦图上求最大导出森林的多项式算法. 相似文献
17.
18.
The edge-face chromatic number Xef (G) of a plane graph G is the least number of colors assigned to the edges and faces such that every adjacent or incident pair of them receives different colors. In this article, the authors prove that every 2-connected plane graph G with△(G)≥|G| -2△9 has Xef(G)=△(G). 相似文献
19.
图与其补图谱半径之间的关系 总被引:6,自引:0,他引:6
徐寅峰 《纯粹数学与应用数学》1993,9(2):89-90
本文我们将图与其补图结合起来,给出了图与其补图的谱半径所必须满足的两个不等式。 相似文献