کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
419229 | 683758 | 2016 | 8 صفحه PDF | دانلود رایگان |
The first-order edge-tenacity T1(G)T1(G) of a graph GG is defined as T1(G)=min{|X|+τ(G−X)ω(G−X)−1} where the minimum is taken over every edge-cutset XX that separates GG into ω(G−X)ω(G−X) components, and by τ(G−X)τ(G−X) we denote the order (the number of edges) of a largest component of G−XG−X.The objective of this paper is to study this concept of edge-tenacity and determining this quantity for some special classes of graphs. We calculate the first-order edge-tenacity of a complete nn-partite graph. We shall obtain the first-order edge-tenacity of maximal planar graphs, maximal outerplanar graphs, and kk-trees. Let GG be a graph of order pp and size qq, we shall call the least integer rr, 1≤r≤p−11≤r≤p−1, with Tr(G)=qp−r the balancity of GG and denote it by b(G)b(G). Note that the balancity exists since Tr(G)=qp−r if r=p−1r=p−1. In general, it is difficult to determine the balancity of a graph. In this paper, we shall first determine the balancity of a special class of graphs and use this to find an upper bound for the balancity of an arbitrary graph.
Journal: Discrete Applied Mathematics - Volume 205, 31 May 2016, Pages 8–15