On the reliability of generalized Petersen graphs

The super-connectivity (super-edge-connectivity) of a connected graph G is the minimum number of vertices (edges) that need to be deleted from G in order to disconnect G without creating isolated vertices. We determine when the generalized Petersen graphs GP[n,k] are super-connected and super edge-c...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2019-01, Vol.252, p.2-9
Main Authors: Boruzanlı Ekinci, Gülnaz, Gauci, John Baptist
Format: Article
Language:English
Subjects:
Apexes
Connectivity
Fault tolerance
Generalized Petersen graph
Graph theory
Graphs
Network reliability
Networks
Reliability
Super-connectivity
Super-edge-connectivity
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:The super-connectivity (super-edge-connectivity) of a connected graph G is the minimum number of vertices (edges) that need to be deleted from G in order to disconnect G without creating isolated vertices. We determine when the generalized Petersen graphs GP[n,k] are super-connected and super edge-connected, and show that their super-connectivity and their super-edge-connectivity are both equal to four when n∉{2k,3k}. These results partially answer a question by Harary (1983) and are of interest especially in the study of reliability and fault tolerance of interconnection networks, since the graphs in this class are good candidates for such networks.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2017.02.002