Edge Neighbor Toughness of Graphs

A new graph parameter, edge neighbor toughness is introduced to measure how difficult it is for a graph to be broken into many components through the deletion of the closed neighborhoods of a few edges. Let G=(V,E) be a graph. An edge e is said to be subverted when its neighborhood and the two endve...

Full description

Saved in:
Bibliographic Details
Published in:Axioms 2022-05, Vol.11 (6), p.248
Main Authors: Feng, Xin, Wei, Zongtian, Yang, Yucheng
Format: Article
Language:English
Subjects:
Algorithms
Connectivity
edge neighbor toughness
graph
Graph theory
Graphs
Mathematical research
NP-complete
Parameters
polynomial algorithm
Polynomials
Toughness
tree
Trees (mathematics)
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A new graph parameter, edge neighbor toughness is introduced to measure how difficult it is for a graph to be broken into many components through the deletion of the closed neighborhoods of a few edges. Let G=(V,E) be a graph. An edge e is said to be subverted when its neighborhood and the two endvertices are deleted from G. An edge set S⊆E(G) is called an edge cut-strategy if all the edges in S has been subverted from G and the survival subgraph, denoted by G/S, is disconnected, or is a single vertex, or is. The edge neighbor toughness of a graph G is defined to be tEN(G)=minS⊆E(G){|S|c(G/S)}, where S is any edge cut strategy of G, c(G/S) is the number of the components of G/S. In this paper, the properties of this parameter are investigated, and the proof of the computation problem of edge neighbor toughness is NP-complete; finally, a polynomial algorithm for computing the edge neighbor toughness of trees is given.
ISSN:2075-1680
2075-1680
DOI:10.3390/axioms11060248