共查询到16条相似文献,搜索用时 93 毫秒
1.
李红燕 《纯粹数学与应用数学》2016,32(2):127-131
连通图G的一个k-树是指图G的一个最大度至多是k的生成树.对于连通图G来说,其毁裂度定义为r(G)=max{ω(G-X)-|X|-m(G-X)|X■V(G),ω(G-X)1}其中ω(G-X)和m(G-X)分别表示G-X中的分支数目和最大分支的阶数.本文结合毁裂度给出连通图G包含一个k-树的充分条件;利用图的结构性质和毁裂度的关系逐步刻画并给出图G包含一个k-树的毁裂度条件. 相似文献
2.
温一慧 《数学的实践与认识》2008,38(15)
通常没有有效的方法判别一般图G的k-边幻性.本文采用分析方法,讨论了一类非均匀边裂图SPE(Cn,h)的边幻性和k-边幻性,得到一些新的结果. 相似文献
3.
温一慧 《数学的实践与认识》2009,39(19)
指出了一类边裂图SEP(K1,n,f)与图K1,n的边优美性的差异.得到了对任意自然数m>0,SPE(K1,4m+1,f)不是边优美的,以及SEP(K1,n,f)是边优美图的充要条件. 相似文献
4.
单项式理想是多项式环中一类重要的理想,这类理想的生成元和超图的边之间可以一一对应.超图的边理想的很多代数性质和它的组合性质之间有密切的联系.根据线图、圈图和单项式理想的正则度的一些公式,通过构造合适的短正合列,给出了两类m-剖分图的边理想的正则度的精确公式,分别推广了m个顶点的线图和圈图的正则度公式. 相似文献
5.
6.
7.
李银奎 《纯粹数学与应用数学》2008,24(1):21-24
利用网络优化方法探讨毁度与其他网络抗毁性参数,如连通度,坚韧度、离散数、完整度、粘连度之间的关系,以便更好分析网络的稳定性,构造例子表明结果是最好可能的. 相似文献
8.
图X称为边正则图,若X的自同构群Aut(X)在X的边集上的作用是正则的.本文考察了三度边正则图与四度Cayley图的关系,给出了一个由四度Cayley图构造三度边正则图的方法,并且构造了边正则图的三个无限族. 相似文献
9.
相对于其他网络抗毁性的描述指标来说,图的粘连度是比较理想,也是比较合理的刻画参数.而完全k叉树作为重要的网络结构被广泛地应用在通信网和嵌入式系统芯片的优化设计方面.本文通过优化组合方法界定了完全k叉树的粘连度和毁裂度.从某种程度刻画了网络的抗毁性,为网络设计提供了一种客观的理论依据.完全k叉树的粘连度为1k+1(kh+1-1),如h是奇数;1k+1((kh+1-1),如h是偶数.完全k叉树的毁裂度为(2k-1)kh-12,如h是奇数;kh+22-1k-1,如h是偶数. 相似文献
10.
11.
Liming Xiong 《Journal of Graph Theory》1998,27(2):67-74
We give a best possible Dirac-like condition for a graph G so that its line graph L(G) is subpancyclic, i.e., L(G) contains a cycle of length l for each l between 3 and the circumference of G. The result verifies the conjecture posed by Xiong (Pancyclic results in hamiltonian line graphs, in: Combinatorics and Graph Theory '95, vol. 2, Proceedings of the Summer School and International Conference on Combinatorics, World Scientific). © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 67–74, 1998 相似文献
12.
Douglas R. Woodall 《Journal of Graph Theory》2019,92(4):488-490
In the article “The average degree of an edge-chromatic critical graph II” by Douglas R. Woodall (J. Graph Theory 56 (2007), 194-218), it was claimed that the average degree of an edge-chromatic critical graph with maximum degree is at least if , at least if , and at least if . Unfortunately there were mistakes in the proof of the last two of these results, which are now proved only if and , respectively. 相似文献
13.
Yehong Shao 《Discrete Mathematics》2018,341(12):3441-3446
Let be a graph and be its line graph. In 1969, Chartrand and Stewart proved that , where and denote the edge connectivity of and respectively. We show a similar relationship holds for the essential edge connectivity of and , written and , respectively. In this note, it is proved that if is not a complete graph and does not have a vertex of degree two, then . An immediate corollary is that for such graphs , where the vertex connectivity of the line graph
and the second iterated line graph are written as and respectively. 相似文献
14.
15.
A proper edge-k-coloring of a graph G is a mapping from E(G) to {1, 2,..., k} such that no two adjacent edges receive the same color. A proper edge-k-coloring of G is called neighbor sum distinguishing if for each edge uv ∈ E(G), the sum of colors taken on the edges incident to u is different from the sum of colors taken on the edges incident to v. Let χ_Σ'(G) denote the smallest value k in such a coloring of G. This parameter makes sense for graphs containing no isolated edges(we call such graphs normal). The maximum average degree mad(G) of G is the maximum of the average degrees of its non-empty subgraphs. In this paper, we prove that if G is a normal subcubic graph with mad(G) 5/2,then χ_Σ'(G) ≤ 5. We also prove that if G is a normal subcubic graph with at least two 2-vertices, 6 colors are enough for a neighbor sum distinguishing edge coloring of G, which holds for the list version as well. 相似文献
16.
The smallest number of edges that have to be deleted from a graph to obtain a bipartite spanning subgraph is called the bipartite edge frustration of G and denoted by φ(G). In this paper we determine the bipartite edge frustration of some classes of composite graphs. 相似文献