On the first-order edge tenacity of a graph

详细信息    查看全文

• 作者：Bahareh Bafandeh^a ; Dara Moazzami^b ; ^{dmoazzami@ut.ac.ir" class="auth_mail" title="E-mail the corresponding author} ; Amin Ghodousian^b
• 关键词：Edge-tenacity ; Planar graph ; Balancity
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：31 May 2016
• 年：2016
• 卷：205
• 期：Complete
• 页码：8-15
• 全文大小：377 K

文摘

The first-order edge-tenacity T₁(G)$T_1\left(G\right)$ of a graph G$G$ is defined as where the minimum is taken over every edge-cutset X$X$ that separates G$G$ into ω(G−X)$\omega (G-X)$ components, and by τ(G−X)$\tau (G-X)$ we denote the order (the number of edges) of a largest component of G−X$G-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 n$n$-partite graph. We shall obtain the first-order edge-tenacity of maximal planar graphs, maximal outerplanar graphs, and k$k$-trees. Let G$G$ be a graph of order p$p$ and size q$q$, we shall call the least integer r$r$, 1≤r≤p−1$1\le r\le p-1$, with $T_r\left(G\right)=\frac{q}{p-r}$ the balancity of G$G$ and denote it by b(G)$b\left(G\right)$. Note that the balancity exists since $T_r\left(G\right)=\frac{q}{p-r}$ if r=p−1$r=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.