The L(2,1)-labelling number of distance graphs G(D), denoted by λ(D), isstudied. It is shown that distance graphs satisfy λ(G) ≤Δ~2. Moreover, we prove λ({1,2, ..., k})=2k +2 and λ({1,3,..., 2k -1}) =2k + 2 for ...The L(2,1)-labelling number of distance graphs G(D), denoted by λ(D), isstudied. It is shown that distance graphs satisfy λ(G) ≤Δ~2. Moreover, we prove λ({1,2, ..., k})=2k +2 and λ({1,3,..., 2k -1}) =2k + 2 for any fixed positive integer k. Suppose k, a ∈ N and k,a≥2. If k≥a, then λ({a, a + 1,..., a + k - 1}) = 2(a + k-1). Otherwise, λ({a, a + 1, ..., a + k- 1}) ≤min{2(a + k-1), 6k -2}. When D consists of two positive integers,6≤λ(D)≤8. For thespecial distance sets D = {k, k + 1}(any k ∈N), the upper bound of λ(D) is improved to 7.展开更多
L (2, 1)-labeling number, λ(G( Z , D)) , of distance graph G( Z , D) is studied. For general finite distance set D , it is shown that 2D+2≤λ(G( Z , D))≤D 2+3D. Furthermore, λ(G( Z , D)) ≤8 when...L (2, 1)-labeling number, λ(G( Z , D)) , of distance graph G( Z , D) is studied. For general finite distance set D , it is shown that 2D+2≤λ(G( Z , D))≤D 2+3D. Furthermore, λ(G( Z , D)) ≤8 when D consists of two prime positive odd integers is proved. Finally, a new concept to study the upper bounds of λ(G) for some special D is introduced. For these sets, the upper bound is improved to 7.展开更多
A linear forest is a forest whose components are paths. The linear arboricity la （G） of a graph G is the minimum number of linear forests which partition the edge set E（G） of G. The Cartesian product G□H of two g...A linear forest is a forest whose components are paths. The linear arboricity la （G） of a graph G is the minimum number of linear forests which partition the edge set E（G） of G. The Cartesian product G□H of two graphs G and H is defined as the graph with vertex set V（G□H） = {（u, v）｜ u ∈V（G）, v∈V（H） } and edge set E（G□H） = { （ u, x） （ v, Y）｜u=v and xy∈E（H）, or uv∈E（G） and x=y}. Let Pm and Cm,, respectively, denote the path and cycle on m vertices and K, denote the complete graph on n vertices. It is proved that （Km□Pm）=[n＋1/2]for m≥2,la（Km□Cm）=[n＋2/2],and la（Km□Km）=[n＋m-1/2]. The methods to decompose these graphs into linear forests are given in the proofs. Furthermore, the linear arboricity conjecture is true for these classes of graphs.展开更多
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.展开更多
文摘The L(2,1)-labelling number of distance graphs G(D), denoted by λ(D), isstudied. It is shown that distance graphs satisfy λ(G) ≤Δ~2. Moreover, we prove λ({1,2, ..., k})=2k +2 and λ({1,3,..., 2k -1}) =2k + 2 for any fixed positive integer k. Suppose k, a ∈ N and k,a≥2. If k≥a, then λ({a, a + 1,..., a + k - 1}) = 2(a + k-1). Otherwise, λ({a, a + 1, ..., a + k- 1}) ≤min{2(a + k-1), 6k -2}. When D consists of two positive integers,6≤λ(D)≤8. For thespecial distance sets D = {k, k + 1}(any k ∈N), the upper bound of λ(D) is improved to 7.
文摘L (2, 1)-labeling number, λ(G( Z , D)) , of distance graph G( Z , D) is studied. For general finite distance set D , it is shown that 2D+2≤λ(G( Z , D))≤D 2+3D. Furthermore, λ(G( Z , D)) ≤8 when D consists of two prime positive odd integers is proved. Finally, a new concept to study the upper bounds of λ(G) for some special D is introduced. For these sets, the upper bound is improved to 7.
基金The National Natural Science Foundation of China(No.10971025)
文摘A linear forest is a forest whose components are paths. The linear arboricity la （G） of a graph G is the minimum number of linear forests which partition the edge set E（G） of G. The Cartesian product G□H of two graphs G and H is defined as the graph with vertex set V（G□H） = {（u, v）｜ u ∈V（G）, v∈V（H） } and edge set E（G□H） = { （ u, x） （ v, Y）｜u=v and xy∈E（H）, or uv∈E（G） and x=y}. Let Pm and Cm,, respectively, denote the path and cycle on m vertices and K, denote the complete graph on n vertices. It is proved that （Km□Pm）=[n＋1/2]for m≥2,la（Km□Cm）=[n＋2/2],and la（Km□Km）=[n＋m-1/2]. The methods to decompose these graphs into linear forests are given in the proofs. Furthermore, the linear arboricity conjecture is true for these classes of graphs.
基金National Natural Science Foundation of China(No.10971025)
文摘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.
