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.展开更多
An L（2, 1）-labeling of a graph G is a function f from the vertex set V（G） to the set of all nonnegative integers such that ｜f（x） - f（y）｜ 〉 2 if d（x, y） = 1 and ｜f（x）-f（y）｜ ≥ 1 ifd（x, y） = 2. The ...An L（2, 1）-labeling of a graph G is a function f from the vertex set V（G） to the set of all nonnegative integers such that ｜f（x） - f（y）｜ 〉 2 if d（x, y） = 1 and ｜f（x）-f（y）｜ ≥ 1 ifd（x, y） = 2. The L（2, 1）-labeling number λ（G） of G is the smallest number k such that G has an L（2, 1）-labeling with max{f（v） ： v ∈ V（G）} = k. We study the L（3, 2, 1）-labeling which is a generalization of the L（2, 1）-labeling on the graph formed by the （Cartesian） product and composition of 3 graphs and derive the upper bounds of λ3（G） of the graph.展开更多
A generalized strongly regular graphof grade p,as anew generalization of strongly regular graphs,is a regular graph such that the number of common neighbours of both any two adjacent vertices and any two non-adjacent ...A generalized strongly regular graphof grade p,as anew generalization of strongly regular graphs,is a regular graph such that the number of common neighbours of both any two adjacent vertices and any two non-adjacent vertices takes on p distinct values.For any vertex u of a generalized strongly regular graph of grade 2 with parameters(n,k;a_(1),a_(2);c_(1),c_(2)),if the number of the vertices that are adjacent to u and share ai(i=1,2)common neighbours with u,or are non-adjacent to u and share c,(i=1,2)common neighbours with is independent of the choice of the vertex u,then the generalized strongly regular graph of grade 2 is free.In this paper,we investigate the generalized strongly regular graph of grade 2 with parameters(n,k;k-1,a_(2);k-1,c_(2))and provide the sufficient and necessary conditions for the existence of a family of free generalized strongly regular graphs of grade 2.展开更多
基金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.
文摘An L（2, 1）-labeling of a graph G is a function f from the vertex set V（G） to the set of all nonnegative integers such that ｜f（x） - f（y）｜ 〉 2 if d（x, y） = 1 and ｜f（x）-f（y）｜ ≥ 1 ifd（x, y） = 2. The L（2, 1）-labeling number λ（G） of G is the smallest number k such that G has an L（2, 1）-labeling with max{f（v） ： v ∈ V（G）} = k. We study the L（3, 2, 1）-labeling which is a generalization of the L（2, 1）-labeling on the graph formed by the （Cartesian） product and composition of 3 graphs and derive the upper bounds of λ3（G） of the graph.
基金supported by National Natural Science Foundation of China(No.11571091)Natural Science Foundation of Hebei Province,China(No.F2019205147)Innovation Program of Hebei Normal University,China(No.CXZZSS2020050).
文摘A generalized strongly regular graphof grade p,as anew generalization of strongly regular graphs,is a regular graph such that the number of common neighbours of both any two adjacent vertices and any two non-adjacent vertices takes on p distinct values.For any vertex u of a generalized strongly regular graph of grade 2 with parameters(n,k;a_(1),a_(2);c_(1),c_(2)),if the number of the vertices that are adjacent to u and share ai(i=1,2)common neighbours with u,or are non-adjacent to u and share c,(i=1,2)common neighbours with is independent of the choice of the vertex u,then the generalized strongly regular graph of grade 2 is free.In this paper,we investigate the generalized strongly regular graph of grade 2 with parameters(n,k;k-1,a_(2);k-1,c_(2))and provide the sufficient and necessary conditions for the existence of a family of free generalized strongly regular graphs of grade 2.
