排序方式: 共有4条查询结果,搜索用时 0 毫秒
1
1.
考虑均衡完全三部图K3(n)的线性3-荫度.利用路分解的方法给出了K3(n)的线性3-荫度la3(Κ3(n))当n≡1,2,3(mod 4)时的比较紧的上界,利用线性k-荫度的基本理论分别得到了它们的下界,进而得到了特殊情况下均衡完全三部图K3(n)的线性3-荫度的确切值. 相似文献
2.
马勤 《山东大学学报(理学版)》2007,42(10):41-43
令ak(G)表示最大度不超过k且能覆盖图G所有边的森林的最小数目.则对于任意的外平面图,当2≤k<Δ(G)时有ak(G)=「Δ(G)/k. 相似文献
3.
A star forest is a forest whose components are stars. The star arboricity of a graph G,denoted by sa( G),is the minimum number of star forests needed to decompose G. Let k be a positive integer. A k-star forest is a forest whose components are stars of order at most k + 1. The k-star arboricity of a graph G,denoted by sak( G),is the minimum number of k-star forests needed to decompose G. In this paper,it is proved that if any two vertices of degree 3 are nonadjacent in a subcubic graph G then sa2( G) ≤2.For general subcubic graphs G, a polynomial-time algorithm is described to decompose G into three 2-star forests. For a tree T and[Δ k, T)/k]t≤ sak( T) ≤[Δ( T)- 1/K]+1,where Δ( T) is the maximum degree of T.kMoreover,a linear-time algorithm is designed to determine whether sak( T) ≤m for any tree T and any positive integers m and k. 相似文献
4.
线性k-森林是每一个连通分支均为长度不超过k的路的图。一个图G的线性k-荫度是将图G的边集合能分解成的线性k-森林的最少数目,用lak(G)来表示。证明了:若G为不含4-圈和5-圈的平面图,则la2(G)≤「Δ(G)+1/2■+4。 相似文献
1