A path decomposition of a graph G is a list of paths such that each edge appears in exactly one path in the list. G is said to admit a {Pl }-decomposition if G can be decomposed into some copies of Pl, where Pl is a p...A path decomposition of a graph G is a list of paths such that each edge appears in exactly one path in the list. G is said to admit a {Pl }-decomposition if G can be decomposed into some copies of Pl, where Pl is a path of length l - 1. Similarly, G is said to admit a {Pl, Pk}-decomposition if G can be decomposed into some copies of Pl or Pk. An k-cycle, denoted by Ck, is a cycle with k vertices. An odd tree is a tree of which all vertices have odd degree. In this paper, it is shown that a connected graph G admits a {P3, P4}-decomposition if and only if G is neither a 3-cycle nor an odd tree. This result includes the related result of Yan, Xu and Mutu. Moreover, two polynomial algorithms are given to find {P3}-decomposition and {P3, P4}-decomposition of graphs, respectively. Hence, {P3}-decomposition problem and {P3, P4}-decomposition problem of graphs are solved completely.展开更多
An L（2, 1）-labelling of a graph G is a function from the vertex set V（G） to the set of all nonnegative integers such that │f（u） - f（v）│≥2 if dG（u, v） = 1 and │f（u） - f（v）│ ≥ 1 if dG（u, v） = 2. Th...An L（2, 1）-labelling of a graph G is a function from the vertex set V（G） to the set of all nonnegative integers such that │f（u） - f（v）│≥2 if dG（u, v） = 1 and │f（u） - f（v）│ ≥ 1 if dG（u, v） = 2. The L（2, 1）-labelling problem is to find the smallest number, denoted by A（G）, such that there exists an L（2, 1）-labelling function with no label greater than it. In this paper, we study this problem for trees. Our results improve the result of Wang [The L（2, 1）-labelling of trees, Discrete Appl. Math. 154 （2006） 598-603].展开更多
The spectral spread of a graph is defined to be the difference between the largest and the least eigenvalue of the adjacency matrix of the graph. A graph G is said to be bicyclic, if G is connected and ｜E（G）｜ = ...The spectral spread of a graph is defined to be the difference between the largest and the least eigenvalue of the adjacency matrix of the graph. A graph G is said to be bicyclic, if G is connected and ｜E（G）｜ = ｜V （G）｜ ＋ 1. Let B（n, g） be the set of bicyclic graphs on n vertices with girth g. In this paper some properties about the least eigenvalues of graphs are given, by which the unique graph with maximal spectral spread in B（n, g） is determined.展开更多
基金Supported by the National Natural Science Foundation of China(No.10301010)Science and Technology Commission of Shanghai Municipality(No.04JC14031)Natural Science Project of Chuzhou University(No.2006kyy017)
文摘A path decomposition of a graph G is a list of paths such that each edge appears in exactly one path in the list. G is said to admit a {Pl }-decomposition if G can be decomposed into some copies of Pl, where Pl is a path of length l - 1. Similarly, G is said to admit a {Pl, Pk}-decomposition if G can be decomposed into some copies of Pl or Pk. An k-cycle, denoted by Ck, is a cycle with k vertices. An odd tree is a tree of which all vertices have odd degree. In this paper, it is shown that a connected graph G admits a {P3, P4}-decomposition if and only if G is neither a 3-cycle nor an odd tree. This result includes the related result of Yan, Xu and Mutu. Moreover, two polynomial algorithms are given to find {P3}-decomposition and {P3, P4}-decomposition of graphs, respectively. Hence, {P3}-decomposition problem and {P3, P4}-decomposition problem of graphs are solved completely.
基金Supported by the National Natural Science Foundation of China (No. 10971248,11101057)Anhui Provincial Natural Science Foundation (No. 10040606Q45)Postdoctoral Science Foundation of Jiangsu Provinc (No.1102095C)
文摘An L（2, 1）-labelling of a graph G is a function from the vertex set V（G） to the set of all nonnegative integers such that │f（u） - f（v）│≥2 if dG（u, v） = 1 and │f（u） - f（v）│ ≥ 1 if dG（u, v） = 2. The L（2, 1）-labelling problem is to find the smallest number, denoted by A（G）, such that there exists an L（2, 1）-labelling function with no label greater than it. In this paper, we study this problem for trees. Our results improve the result of Wang [The L（2, 1）-labelling of trees, Discrete Appl. Math. 154 （2006） 598-603].
基金Supported by the National Natural Science Foundation of China(No.11101057)China Postdoctoral Science Foundation(No.20110491443)+1 种基金the NSF of Education Ministry of Anhui province(No.KJ2012Z283)Scientific Research Foundation of Chuzhou University(No.2011kj004B)
文摘The spectral spread of a graph is defined to be the difference between the largest and the least eigenvalue of the adjacency matrix of the graph. A graph G is said to be bicyclic, if G is connected and ｜E（G）｜ = ｜V （G）｜ ＋ 1. Let B（n, g） be the set of bicyclic graphs on n vertices with girth g. In this paper some properties about the least eigenvalues of graphs are given, by which the unique graph with maximal spectral spread in B（n, g） is determined.
