Stability Theorems for Graph Vulnerability Parameters

Given a graph property P, Bondy and Chvátal defined P to be k-stable if for any nonadjacent u, v∈ 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.

Files

Metadata

Work Title Stability Theorems for Graph Vulnerability Parameters
Access
Open Access
Creators
  1. Michael Yatauro
License In Copyright (Rights Reserved)
Work Type Article
Publisher
  1. Graphs and Combinatorics
Publication Date October 23, 2020
Publisher Identifier (DOI)
  1. https://doi.org/10.1007/s00373-020-02239-9
Deposited November 19, 2021

Versions

Analytics

Collections

This resource is currently not in any collection.

Work History

Version 1
published

  • Created
  • Added Yatauro2021_Article_StabilityTheoremsForGraphVulne.pdf
  • Added Creator Michael Yatauro
  • Published
  • Updated
  • Updated