Stability Theorems for Graph Vulnerability Parameters
- PDF / 342,082 Bytes
- 19 Pages / 439.37 x 666.142 pts Page_size
- 93 Downloads / 128 Views
(0123456789().,-volV)(0123456789().,-volV)
ORIGINAL PAPER
Stability Theorems for Graph Vulnerability Parameters Michael Yatauro1 Received: 28 February 2019 / Revised: 25 September 2020 / Accepted: 9 October 2020 Ó Springer Japan KK, part of Springer Nature 2020
Abstract Given a graph property P, Bondy and Chva´tal defined P to be k-stable if for any nonadjacent u; v 2 VðGÞ, whenever G þ uv has the property P and dðuÞ þ dðvÞ k, then G itself has the property P. The smallest such k is called the stability of P. We consider the graph parameters integrity, toughness, tenacity, and binding number. For each of these parameters, we provide the stability for the property that G has a value for that parameter which is at least c, for some fixed c. We also demonstrate how stability can lead to degree sequence theorems and compare these results to known degree sequence theorems that are best possible in a certain sense. Keywords Stability Closure Degree sequence theorem Integrity Toughness Tenacity Binding number
1 Introduction We consider only finite, undirected, simple graphs. A suitable reference for any undefined terms or notation is [16]. Our terminology and notation will be standard, except as indicated. Given two graphs G and H we use G þ H to denote their join and G [ H to denote their disjoint union. If v 2 VðGÞ, then dG ðvÞ denotes the degree of v in G. We may choose to use d(v), when appropriate. If X VðGÞ, then we define the neighbor set of X in G, denoted NG ðXÞ, to be the set of all vertices in G adjacent to at least one vertex in X. If the graph G is clear from the context, then we may choose to use N(X) instead of NG ðXÞ. Given a noncomplete graph G, we define the integrity of G, denoted I(G), as in [12], the toughness of G, denoted sðGÞ, as in [9], the tenacity of G, denoted T(G), as in [12], and the binding number of G, denoted bind ðGÞ, as in [17]: & Michael Yatauro [email protected] 1
Penn State, Brandywine Campus, Media, PA 19063, USA
123
Graphs and Combinatorics
IðGÞ ¼ minfjXj þ mðG XÞ j X VðGÞ and xðG XÞ 2g; jXj X VðGÞ and xðG XÞ 2 ; sðGÞ ¼ min xðG XÞ jXj þ mðG XÞ X VðGÞ and xðG XÞ 2 ; and TðGÞ ¼ min xðG XÞ jNðXÞj bind ðGÞ ¼ min ; 6¼ X VðGÞ; NðXÞ 6¼ VðGÞ ; jXj where mðG XÞ is the order of a largest component of G X and xðG XÞ is the number of components of G X. Let Kn be the complete graph on n vertices. Then we define IðKn Þ :¼ n, sðKn Þ :¼ n 1 and TðKn Þ :¼ n. A graph G is c-integral if IðGÞ c, c-tough if sðGÞ c, c-tenacious if TðGÞ c, and c-binding if bind ðGÞ c The integrity, toughness, tenacity, and binding number are members of a class of vulnerability parameters of a graph that are often used to study network reliability. Other parameters that fall under this heading are vertex-connectivity and edgeconnectivity. Discussions of relationships between certain vulnerability parameters can be found in [1] and [14]. In terms of computational complexity, determining the integrity, toughness, or tenacity of a
Data Loading...
