Study On Vertex And Edeg-neighbor-integrities Of Graphs

A vertex u ∈ V(G) is subverted from a graph G by removing the closed neighborhood N[u] from G, the vertex subversion strategy S of G is a set of vertices in G whose closed neighborhood is deleted from G. Define the survival subgraph G/S to be the subgraph left after the subversion strategy S is applied to G, i.e., G/S = G\N[S). The vertex-neighbor-integrity(VNI) of G denoted by VNI(G), is defined to beVNI(G)= mm {|S|\+ω(G/S)},where S is any vertices subset of G and u{G/S) is order of the largest connected components in the G/S.An edge e = [u, v] in graph G is said to be subverted when the incident vertices, u, v, of the edge e are deleted from G. A set of edges T is called an edge subversion strategy of G if each of the edges in T has been subverted from G. Let G/T be the survival subgraph left when T has been an edge subversion strategy of G. The edge-neighbor-integrity(ENI) of a graph G, ENI(G) is defined to beENI(G)= min {|T|+u(G/T)},where T is any edge subversion strategy of G and u(G/T) is maximum order of the components of G/T.In this paper, first of all, the relation between VNI and ENI of trees and cycles is obtained. Then VNI of a special graph T_n,k is derived. In the following, trees whose VNI = 1 and VNI = 2 are characterized. We also show that for any integer l between the extreme values there is a tree with VNI equals to l. We verify the conjecture proposed by Marci J. Gambrell : for any connected n-vertex graph G, VNI(G) ≤ [n/3]. At last, lower and upper bounds of VNI and ENI of binary operations, union, intersection and cartesian product of graphs are derived.