A k-tree of a connected graph G is a spanning tree with maximum degree at most k. The rupture degree for a connected graph G is defined by , where and , respectively, denote the order of the largest component and numb...A k-tree of a connected graph G is a spanning tree with maximum degree at most k. The rupture degree for a connected graph G is defined by , where and , respectively, denote the order of the largest component and number of components in . In this paper, we show that for a connected graph G, if for any cut-set , then G has a k-tree.展开更多
Abstract The paper proves that if G is a k tree, then the bandwidth B(G) of the complement G of G is given by B(G)=n-k-1, when GK k+K n-k , n-k-2, otherwise.
Let G be a graph, in which each vertex (job) v has a positive integer weight (processing time) p(v) and eachedge (u,v) represented that the pair of jobs u and v cannot be processed in the same slot. In this paper we a...Let G be a graph, in which each vertex (job) v has a positive integer weight (processing time) p(v) and eachedge (u,v) represented that the pair of jobs u and v cannot be processed in the same slot. In this paper we assume that every job is non-preemptive. Let C={1,2,...} be a color set. A multicoloring (scheduling) F of G is to assign each job v a set of p(v) consecutive positive integers (processing consecutive time slots) in C so that any pair of adjacent vertices receive disjoint sets. Such a multicoloring is called a non-preemptive scheduling. The cost non-preemptive scheduling problem is to find an optimal multicoloring of G.展开更多
A k-tree is a tree with maximum degree at most k. In this paper, we give a sharp degree sum condition for a graph to have a spanning k-tree in which specified vertices have degree less than t, where 1≤t≤k.We denote ...A k-tree is a tree with maximum degree at most k. In this paper, we give a sharp degree sum condition for a graph to have a spanning k-tree in which specified vertices have degree less than t, where 1≤t≤k.We denote by σ_k(G) the minimum value of the degree sum of k independent vertices in a graph G. Let k≥2,s≥0 and 1≤t≤k be integers, and suppose G is an(s + 1)-connected graph with σ_k(G)≥|G|+(k-t)s-1.Then for any s specified vertices, G contains a spanning k-tree in which every specified vertex has degree at most t. This improves a result obtained by Matsuda and Matsumura.展开更多
The edge-tenacity of a graph G(V,E) is denned as min{(|S|+T(G-S))/ω(G-S):S(?)E(G)},where T(G ?S) and ω(G-S), respectively, denote the order of the largest component and the number of the components of G-S. This is a...The edge-tenacity of a graph G(V,E) is denned as min{(|S|+T(G-S))/ω(G-S):S(?)E(G)},where T(G ?S) and ω(G-S), respectively, denote the order of the largest component and the number of the components of G-S. This is a better parameter to measure the stability of a network G, as it takes into account both the quantity and the order of components of the graph G-S. In a previous work, we established a necessary and sufficient condition for a graph to be edge-tenacious. These results are applied to prove that K-trees are strictly edge-tenacious. A number of results are given on the relation of edge-tenacity and other parameters, such as the higher-order edge toughness and the edge-toughness.展开更多
文摘A k-tree of a connected graph G is a spanning tree with maximum degree at most k. The rupture degree for a connected graph G is defined by , where and , respectively, denote the order of the largest component and number of components in . In this paper, we show that for a connected graph G, if for any cut-set , then G has a k-tree.
文摘Abstract The paper proves that if G is a k tree, then the bandwidth B(G) of the complement G of G is given by B(G)=n-k-1, when GK k+K n-k , n-k-2, otherwise.
文摘Let G be a graph, in which each vertex (job) v has a positive integer weight (processing time) p(v) and eachedge (u,v) represented that the pair of jobs u and v cannot be processed in the same slot. In this paper we assume that every job is non-preemptive. Let C={1,2,...} be a color set. A multicoloring (scheduling) F of G is to assign each job v a set of p(v) consecutive positive integers (processing consecutive time slots) in C so that any pair of adjacent vertices receive disjoint sets. Such a multicoloring is called a non-preemptive scheduling. The cost non-preemptive scheduling problem is to find an optimal multicoloring of G.
基金Partially supported by National Natural Science Foundation of China(No.11771172)key scientific and technological project of higher education of Henan Province(No.19A110019)+1 种基金Science and technology innovation fund of Henan Agricultural University(No.KJCX2019A15)Partially supported by the Ph D Research Foundation of Henan Agricultural University(No.30500614)
文摘A k-tree is a tree with maximum degree at most k. In this paper, we give a sharp degree sum condition for a graph to have a spanning k-tree in which specified vertices have degree less than t, where 1≤t≤k.We denote by σ_k(G) the minimum value of the degree sum of k independent vertices in a graph G. Let k≥2,s≥0 and 1≤t≤k be integers, and suppose G is an(s + 1)-connected graph with σ_k(G)≥|G|+(k-t)s-1.Then for any s specified vertices, G contains a spanning k-tree in which every specified vertex has degree at most t. This improves a result obtained by Matsuda and Matsumura.
基金SuppoSed by the Ministry of Communication(200332922505) the Doctoral Foundation of Ministry of Education(20030151005)
文摘The edge-tenacity of a graph G(V,E) is denned as min{(|S|+T(G-S))/ω(G-S):S(?)E(G)},where T(G ?S) and ω(G-S), respectively, denote the order of the largest component and the number of the components of G-S. This is a better parameter to measure the stability of a network G, as it takes into account both the quantity and the order of components of the graph G-S. In a previous work, we established a necessary and sufficient condition for a graph to be edge-tenacious. These results are applied to prove that K-trees are strictly edge-tenacious. A number of results are given on the relation of edge-tenacity and other parameters, such as the higher-order edge toughness and the edge-toughness.
