On the first-order edge tenacity of a graph
| Autor: | Amin Ghodousian, Dara Moazzami, Bahareh Bafandeh |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Discrete mathematics
Strongly regular graph Applied Mathematics 0211 other engineering and technologies 021107 urban & regional planning 0102 computer and information sciences 02 engineering and technology 01 natural sciences Planar graph Combinatorics symbols.namesake 010201 computation theory & mathematics Graph power Random regular graph symbols Graph minor Discrete Mathematics and Combinatorics Bound graph Graph toughness Graph factorization Mathematics |
| Zdroj: | Discrete Applied Mathematics. 205:8-15 |
| ISSN: | 0166-218X |
| DOI: | 10.1016/j.dam.2015.10.027 |
| Popis: | The first-order edge-tenacity T 1 ( G ) of a graph G is defined as T 1 ( G ) = m i n { | X | + ? ( G - X ) ω ( G - X ) - 1 } where the minimum is taken over every edge-cutset X that separates G into ω ( G - X ) components, and by ? ( G - X ) we denote the order (the number of edges) of a largest component of 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 -partite graph. We shall obtain the first-order edge-tenacity of maximal planar graphs, maximal outerplanar graphs, and k -trees. Let G be a graph of order p and size q , we shall call the least integer r , 1 ? r ? p - 1 , with T r ( G ) = q p - r the balancity of G and denote it by b ( G ) . Note that the balancity exists since T r ( G ) = q p - r if 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect