Vertex-neighbor-integrity of powers of cycles

Margaret B. Cozzens, Shu Shih Y. Wu

Research output: Contribution to journalArticlepeer-review

17 Scopus citations

Abstract

Let G be a graph. A vertex subversion strategy of G, S, is a set of vertices in G whose closed neighborhood is deleted from G. The survival-subgraph is denoted by G/S. The vertex-neighbor-integrity of G, VNI(G), is defined to be VNI(G) = min {|S| + ω(G/S)}, where S is any vertex subversion strategy of G, and ω(G/S) is the maximum order of the components of G/S. In this paper, we evaluate the vertex-neighbor-integrity of the powers of cycles, and show that among the powers of the n-cycle, the maximum vertex-neighbor-integrity is ⌈2√n⌉ - 3 and the minimum vertex-neighbor-integrity is ⌈n/(2⌊n/2⌋ + 1)⌉.

Original languageEnglish (US)
Pages (from-to)257-270
Number of pages14
JournalArs Combinatoria
Volume48
StatePublished - Apr 1 1998
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Mathematics(all)

Fingerprint Dive into the research topics of 'Vertex-neighbor-integrity of powers of cycles'. Together they form a unique fingerprint.

Cite this