期刊文献+
共找到2篇文章
< 1 >
每页显示 20 50 100
Neighbor Sum Distinguishing Edge Coloring of Subcubic Graphs 被引量:7
1
作者 Xiao Wei YU Guang Hui WANG +1 位作者 Jian Liang WU Gui Ying YAN 《Acta Mathematica Sinica,English Series》 SCIE CSCD 2017年第2期252-262,共11页
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 e... 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 X(G ) denote the smallest value k in such a ' G 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 then x'(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. 展开更多
关键词 Proper edge coloring neighbor sum distinguishing edge coloring maximum average de-gree subcubic graph planar graph
原文传递
On k-Star Arboricity of Graphs
2
作者 陶昉昀 林文松 《Journal of Donghua University(English Edition)》 EI CAS 2014年第3期335-338,共4页
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... 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. 展开更多
关键词 star arboricity k-star arboricity linear k-arboricity cubic graphs subcubic graphs
下载PDF
上一页 1 下一页 到第
使用帮助 返回顶部