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.展开更多
A graph is NIC-planar if it admits a drawing in the plane with at most one crossing per edge and such that two pairs of crossing edges share at most one common end vertex. It is proved that every NIC-planar graph with...A graph is NIC-planar if it admits a drawing in the plane with at most one crossing per edge and such that two pairs of crossing edges share at most one common end vertex. It is proved that every NIC-planar graph with minimum degree at least 2(resp. 3) contains either an edge with degree sum at most 23(resp. 17) or a 2-alternating cycle(resp. 3-alternating quadrilateral). By applying those structural theorems, we confirm the Linear Arboricity Conjecture for NIC-planar graphs with maximum degree at least 14 and determine the linear arboricity of NIC-planar graphs with maximum degree at least 21.展开更多
The arboricity of graph G=(V,E), denoted by a(G), is defined as a(G)=min{n | E can be partitioned into n subsets E1,E2,...,En, such that each subset spans a subgraph of G so as to be a forest}.In this paper the follow...The arboricity of graph G=(V,E), denoted by a(G), is defined as a(G)=min{n | E can be partitioned into n subsets E1,E2,...,En, such that each subset spans a subgraph of G so as to be a forest}.In this paper the following results have been obtained. For any graph G of order p,and the bounds are sharp; especially as an integer function, 5p+7 could not be decreased. Furthermore, Nordhaus-Gaddum Theorem for arboricity has also been got.展开更多
A graph is outer-1-planar if it can be drawn in the plane so that all vertices are on the outer face and each edge is crossed at most once.Zhang et al.(Edge covering pseudo-outerplanar graphs with forests,Discrete Mat...A graph is outer-1-planar if it can be drawn in the plane so that all vertices are on the outer face and each edge is crossed at most once.Zhang et al.(Edge covering pseudo-outerplanar graphs with forests,Discrete Math 312:2788-2799,2012;MR2945171)proved that the linear arboricity of every outer-1-planar graph with maximum degree△is exactly[△/2] provided that△=3or△≥5 and claimed that there are outer-1-planar graphs with maximum degree △=4 and linear arboricity[[(O+1)/2]=3.It is shown in this paper that the linear arboricity of every outer-1-planar graph with maximum degree 4 is exactly 2 provided that it admits an outer-1-planar drawing with crossing distance at least 1 and crossing width at least 2,and moreover,none of the above constraints on the crossing distance and Crossing width can be removed..Besides,a polynomial-time algorithm for constructing a path-2-coloring(i.e.,an edge 2-coloring such that each color class induces a linear forest,a disjoint union of paths)of such an outer-1-planar drawing is given.展开更多
The equitable tree-coloring can formulate a structure decomposition problem on the communication network with some security considerations.Namely,an equitable tree-Zc-coloring of a graph is a vertex coloring using k d...The equitable tree-coloring can formulate a structure decomposition problem on the communication network with some security considerations.Namely,an equitable tree-Zc-coloring of a graph is a vertex coloring using k distinct colors such that every color class induces a forest and the sizes of any two color classes differ by at most one.In this paper,we show some theoretical results on the equitable tree-coloring of graphs by proving that every d-degenerate graph with maximum degree at most Δ is equitably tree-fc-colorable for every integer k≥(Δ+1)/2 provided that Δ≥9.818d,confirming the equitable vertex arboricity conjecture for graphs with low degeneracy.展开更多
The linear arboricity la(G) of a graph G is the minimum number of linear forests which partition the edges of G. Akiyama, Exoo and Harary conjectured that la(G) = [△(G)+1/2] for any regular graph G. In this paper, we...The linear arboricity la(G) of a graph G is the minimum number of linear forests which partition the edges of G. Akiyama, Exoo and Harary conjectured that la(G) = [△(G)+1/2] for any regular graph G. In this paper, we prove the conjecture for some composition graphs, in particular, for complete multipartite graphs.展开更多
A linear directed forest is a directed graph in which every component is a directed path.The linear arboricity la(D) of a digraph D is the minimum number of linear directed forests in D whose union covers all arcs of ...A linear directed forest is a directed graph in which every component is a directed path.The linear arboricity la(D) of a digraph D is the minimum number of linear directed forests in D whose union covers all arcs of D. For every d-regular digraph D, Nakayama and P′eroche conjecture that la(D) = d + 1. In this paper, we consider the linear arboricity for complete symmetric digraphs,regular digraphs with high directed girth and random regular digraphs and we improve some wellknown results. Moreover, we propose a more precise conjecture about the linear arboricity for regular digraphs.展开更多
The community characteristics of natural secondary forests on the north slope of Changbai Mountain after selective cutting were investigated, and the dynamics of arborous species diversity during the restoration perio...The community characteristics of natural secondary forests on the north slope of Changbai Mountain after selective cutting were investigated, and the dynamics of arborous species diversity during the restoration period of 28 years were studied. The results showed that the arborous species richness (S) had little change and kept the range of 18-22 all along, the Simpson index (D) of the secondary layer and regeneration layer and whole stand had similar trends of change, but that of the canopy layer descended slowly in initial 15 years and had little change later, and the change of diversity index was not obvious and the Shannon-Wiener index (H? fluctuated in a very small scopes (H±10%).展开更多
The structure and principle of the PMAC (Programmable Multi-Axis Controller) were described.The implementation of PMAC hardware was illustrated by taking the winding process of one cell for example.The main obvious ch...The structure and principle of the PMAC (Programmable Multi-Axis Controller) were described.The implementation of PMAC hardware was illustrated by taking the winding process of one cell for example.The main obvious character of PMAC is to complete a movement program in turns of movement sequence.When PMAC is notified to execute a motion program, it will process one command every time and finish all the calculation to be ready for real action.PMAC card works always prior to real action, when necessary, it can always coordinate correctly with the action which will be carried out soon PMAC will automatically carry out the function of resource management periodically to make sure that the whole system is in correct condition.And also, it can communicate with host computer anytime even during a movement series.The responsibility of PMAC is to organize command according to priority to optimize the system, so as to run the application program safely and efficiently.The function and application of control were emphasized.展开更多
In the urbanized territory (the Irkutsk city), the content of sulfur and heavy metals (lead, cadmium, copper, zinc) in soil profile horizons and leaves (needles) arboreal plants were studied. High accumulation of poll...In the urbanized territory (the Irkutsk city), the content of sulfur and heavy metals (lead, cadmium, copper, zinc) in soil profile horizons and leaves (needles) arboreal plants were studied. High accumulation of polluting elements in pine and larch needles, birch and poplar leaves, as well as in all genetic horizons of the city soils was shown. There were revealed elements disbalance in city trees assimilation organs showing in the increase of the polluting elements quota with the parallel decrease of the quota of nitrogen, phosphorus, calcium, magnesium, potassium, manganese. Pollutants concentration in trees needles (leaves) was shown to be closely related to their content in soil horizons. The results speak in favor of high migration ability of polluting elements in soil profile and about possibility their entrance in trees root system and further to assimilation organs from all city soils horizons. It can be concluded that data on accumulation and migration of polluting elements in soils and arboreal trees assimilation organs contribute to adequate assessment of technogenic load on urban ecosystems.展开更多
基金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.
基金Supported by the National Natural Science Foundation of China(Nos.11871055,11301410)the Natural Science Basic Research Plan in Shaanxi Province of China(No.2017JM1010)the Fundamental Research Funds for the Central Universities(Nos.JB170706)
文摘A graph is NIC-planar if it admits a drawing in the plane with at most one crossing per edge and such that two pairs of crossing edges share at most one common end vertex. It is proved that every NIC-planar graph with minimum degree at least 2(resp. 3) contains either an edge with degree sum at most 23(resp. 17) or a 2-alternating cycle(resp. 3-alternating quadrilateral). By applying those structural theorems, we confirm the Linear Arboricity Conjecture for NIC-planar graphs with maximum degree at least 14 and determine the linear arboricity of NIC-planar graphs with maximum degree at least 21.
文摘The arboricity of graph G=(V,E), denoted by a(G), is defined as a(G)=min{n | E can be partitioned into n subsets E1,E2,...,En, such that each subset spans a subgraph of G so as to be a forest}.In this paper the following results have been obtained. For any graph G of order p,and the bounds are sharp; especially as an integer function, 5p+7 could not be decreased. Furthermore, Nordhaus-Gaddum Theorem for arboricity has also been got.
基金supported by the Fundamental Research Funds for the Central Universities(No.JB170706)the Natural Science Basic Research Plan in Shaanxi Province of China(No.2017JM1010)+2 种基金the National Natural Science Foundation of China(Nos.11871055 and 11301410)supported by the Natural Science Basic Research Plan in Shaanxi Province of China(No.2017JQ1031)the National Natural Science Foundation of China(Nos.11701440 and 11626181).
文摘A graph is outer-1-planar if it can be drawn in the plane so that all vertices are on the outer face and each edge is crossed at most once.Zhang et al.(Edge covering pseudo-outerplanar graphs with forests,Discrete Math 312:2788-2799,2012;MR2945171)proved that the linear arboricity of every outer-1-planar graph with maximum degree△is exactly[△/2] provided that△=3or△≥5 and claimed that there are outer-1-planar graphs with maximum degree △=4 and linear arboricity[[(O+1)/2]=3.It is shown in this paper that the linear arboricity of every outer-1-planar graph with maximum degree 4 is exactly 2 provided that it admits an outer-1-planar drawing with crossing distance at least 1 and crossing width at least 2,and moreover,none of the above constraints on the crossing distance and Crossing width can be removed..Besides,a polynomial-time algorithm for constructing a path-2-coloring(i.e.,an edge 2-coloring such that each color class induces a linear forest,a disjoint union of paths)of such an outer-1-planar drawing is given.
基金Supported by National Natural Science Foundation of China(Grant Nos.11871055,11701440)。
文摘The equitable tree-coloring can formulate a structure decomposition problem on the communication network with some security considerations.Namely,an equitable tree-Zc-coloring of a graph is a vertex coloring using k distinct colors such that every color class induces a forest and the sizes of any two color classes differ by at most one.In this paper,we show some theoretical results on the equitable tree-coloring of graphs by proving that every d-degenerate graph with maximum degree at most Δ is equitably tree-fc-colorable for every integer k≥(Δ+1)/2 provided that Δ≥9.818d,confirming the equitable vertex arboricity conjecture for graphs with low degeneracy.
基金This work is partially supported by National Natural Science foundation of China Doctoral foundation of the Education Committee of China.
文摘The linear arboricity la(G) of a graph G is the minimum number of linear forests which partition the edges of G. Akiyama, Exoo and Harary conjectured that la(G) = [△(G)+1/2] for any regular graph G. In this paper, we prove the conjecture for some composition graphs, in particular, for complete multipartite graphs.
基金Supported by NSFC(Grant Nos.11601093 and 11671296)
文摘A linear directed forest is a directed graph in which every component is a directed path.The linear arboricity la(D) of a digraph D is the minimum number of linear directed forests in D whose union covers all arcs of D. For every d-regular digraph D, Nakayama and P′eroche conjecture that la(D) = d + 1. In this paper, we consider the linear arboricity for complete symmetric digraphs,regular digraphs with high directed girth and random regular digraphs and we improve some wellknown results. Moreover, we propose a more precise conjecture about the linear arboricity for regular digraphs.
基金This research was supported by Institute of Shenyang Applied Ecology CAS (SCXMS0101),National Key Technologies R&D Program (NKTRDP. 2002BA516A20) and the Scientific Research Foundation for the Returned Overseas Chinese Scholars, Ministry of Education
文摘The community characteristics of natural secondary forests on the north slope of Changbai Mountain after selective cutting were investigated, and the dynamics of arborous species diversity during the restoration period of 28 years were studied. The results showed that the arborous species richness (S) had little change and kept the range of 18-22 all along, the Simpson index (D) of the secondary layer and regeneration layer and whole stand had similar trends of change, but that of the canopy layer descended slowly in initial 15 years and had little change later, and the change of diversity index was not obvious and the Shannon-Wiener index (H? fluctuated in a very small scopes (H±10%).
文摘The structure and principle of the PMAC (Programmable Multi-Axis Controller) were described.The implementation of PMAC hardware was illustrated by taking the winding process of one cell for example.The main obvious character of PMAC is to complete a movement program in turns of movement sequence.When PMAC is notified to execute a motion program, it will process one command every time and finish all the calculation to be ready for real action.PMAC card works always prior to real action, when necessary, it can always coordinate correctly with the action which will be carried out soon PMAC will automatically carry out the function of resource management periodically to make sure that the whole system is in correct condition.And also, it can communicate with host computer anytime even during a movement series.The responsibility of PMAC is to organize command according to priority to optimize the system, so as to run the application program safely and efficiently.The function and application of control were emphasized.
文摘In the urbanized territory (the Irkutsk city), the content of sulfur and heavy metals (lead, cadmium, copper, zinc) in soil profile horizons and leaves (needles) arboreal plants were studied. High accumulation of polluting elements in pine and larch needles, birch and poplar leaves, as well as in all genetic horizons of the city soils was shown. There were revealed elements disbalance in city trees assimilation organs showing in the increase of the polluting elements quota with the parallel decrease of the quota of nitrogen, phosphorus, calcium, magnesium, potassium, manganese. Pollutants concentration in trees needles (leaves) was shown to be closely related to their content in soil horizons. The results speak in favor of high migration ability of polluting elements in soil profile and about possibility their entrance in trees root system and further to assimilation organs from all city soils horizons. It can be concluded that data on accumulation and migration of polluting elements in soils and arboreal trees assimilation organs contribute to adequate assessment of technogenic load on urban ecosystems.
