The Vertex-Neighbor-Integrity of Digraphs

摘要

In this paper, as an extension of the concept of vertex-neighbor-integrity of graphs, we introduce the notion of vertex-neighbor-integrity of digraphs. Let D = (V, A) be a digraph. The open and closed out-neighborhoods of a set S C V are denoted by N~+(S) = {v : uv ∈ A(D),u ∈ S, v ∈ V S} and N~+[S] = N+(S)∪ S, respectively. The vertex-neighbor-integrity of the digraph D is defined as VNI(D) = min_(S is contained in V) {|S| + m(D/S~+)}, where D/S~+ := D - N~+[S] and m(D/S~+) denotes the order of a maximum strong component of D/S~+. We first discuss some basic properties of the vertex-neighbor-integrity of digraphs, and then using these properties we study the maximum vertex-neighbor-integrity which can be obtained by orienting the edges of K_n and K_(s,t).