Vertex-neighbour-integrity of composition graphs of paths and cycles

A vertex subversion strategy of a graph G is a set of vertices X⊆ V(G) whose closed neighbourhood is deleted from G. The survival subgraph is denoted by G/X. The vertex-neighbour-integrity of G is defined to be VNI(G)=min{|X|+τ(G/X):X⊆ V(G)}, where τ(G/X) is the maximum order of the components of G/...

Full description

Saved in:
Bibliographic Details
Published in:International journal of computer mathematics 2008-05, Vol.85 (5), p.727-733
Main Authors: Wei, Zongtian, Zhang, Shenggui
Format: Article
Language:English
Subjects:
C.2.0
Composition graph
Cycle
G.2.2
Path
Vertex-dominating number
Vertex-neighbour-integrity
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 vertex subversion strategy of a graph G is a set of vertices X⊆ V(G) whose closed neighbourhood is deleted from G. The survival subgraph is denoted by G/X. The vertex-neighbour-integrity of G is defined to be VNI(G)=min{|X|+τ(G/X):X⊆ V(G)}, where τ(G/X) is the maximum order of the components of G/X. This graph parameter was introduced by Cozzens and Wu to measure the vulnerability of spy networks. Gambrell proved that the decision problem of computing the vertex-neighbour-integrity of a graph is -complete. In this paper we evaluate the vertex-neighbour-integrity of the composition graphs of paths and cycles.
ISSN:0020-7160
1029-0265
DOI:10.1080/00207160701455860