Advances in Pure Mathematics, 2011, 1, 160-162
doi:10.4236/apm.2011.14029 Published Online July 2011 (http://www.SciRP.org/journal/apm)
Vertex-Neighbor-Scattering Number of Trees
Zongtian Wei1,2, Yong Liu2, Anchan Mai3
1Department of Applied Mathematics, Northwestern Polytechnical University, Xi’an, China
2School of Science, Xi’an University of Architecture and Technology, Xi’an, China
3Science-Cultural Institute, Xi’an Military Academy, Xi’an, China
Received April 29, 2011; revised May 15, 2011; accepted May 25, 2011
Abstract
A vertex subversion strategy of a graph


=,GVE is a set of vertices


SVG whose closed neighbor-
hood is deleted from . The survival subgraph is denoted by GGS. We call a cut-strategy of if S G
GS is disconnected, or is a clique, or is

. The vertex-neighbor-scattering number of is defined to be G
  
()
=max
SVG
VNS GGS 
S, where is any cut-strategy of , and S G


GG  is the number of the com-
ponents of GS. It has been proved that the computing problem of this parameter is complete, so we
discuss the properties of vertex-neighbor-scattering number of trees in this paper.
NP 
Keywords: Vertex-Neighbor-Scattering Number, Tree, Path, Star, Comet
1. Introduction
In [1] we introduced a new graph parameter called
“vertex-neighbor-scattering number.” We motivate the
use of this parameter by viewing a graph as a model of a
spy network whose vertices represent agents and whose
edges represent lines of communication. If a spy is
discovered, the espionage agency can no longer trust any
of the spies with whom he was in direct communication.
It has been shown that the parameter can measure the
“neighbor” stability of graphs [1]. As many graphic
parameters, the computing problem of this parameter is
complete [2]. So we discuss the properties of the
vertex-neighbor-scattering number of trees in this paper.
Our definitions follow [3].
NP 
Let be a graph and u a vertex in G.
and v are is the
open neighborhood of u, and

=,GVE
  
=v VG
The vertex-neighbor-scattering number (VN ) of a
connected noncomplete graph is defined as
S
G






()
=max
SVG
VNSGG SS 
, where is any cut- S
strategy of , and G


GS  is the number of the com-
ponents of GS. We call a

*
SVGVN S

set of G
if




*
VNSGG SS* =  . In particular, we define
the vertex-neighbor-scattering number of a complete
graph n
K
to be 1.
A comet is a graph obtained by identifying one
end of a path
,tr
C


2
t
P with the center of a star


1, 2 r
Sr
,. tr
C
. The center of is called the center of
1,r
S

,

|Nuu vu

adjacent





=Nu
u
Nuu is
the closed neighborhood of . A vertex in G is
said to be subverted if its closed neighborhood
u


Nu
is deleted from . A set of vertices
G


GSV
G
is
called a vertex subversion strategy of if each of the
vertices in has been subverted from G. By SGS
we denote the survival subgraph left after each vertex of
has been subverted from . is called a cut-
strategy of G if the survival subgraph
SG S
GS is dis-
connected, or is a clique, or is

.
The following lemmata will be used in the next
section.
Theorem 1: [1] Let be a path with order
n
P


3.n Then

0,if=3, 4
=1, if5
n
n
VNS Pn



Theorem 2: [1] Let


1, 2 r
Sr be a star. Then


1, =2 r
VNS Sr.

Theorem 3: [1] Let be a comet, both and
are at least Then
,tr
Ct r
2.

Z. T. WEI ET AL.
161
.

,
1,if= 2,3
=,if4
tr
rt
VNS Crt




2. Vertex-Neighbor-Scattering Number of
Trees
Theorem 4: Let be a tree with order Then T
13

5.n

VNS Tn
Proof. 1) For any vertex ,

vVT


2Nv , so

2TS n  . On the other hand, is connected
and with order , then for its any VN
T
5nS

set , S
1S and

2TS n  . Thus we have
  
()
21 3
max
SVT
VNS TTSSnn 


2) We distinguish two cases to prove .

1VNS T
Case 1: . Since , there must exist a
vertex such that
n
TP

T
5n
vV



=2Tv  . So


 
  
()
max
211
SVT
VNS TTSS
Tv v





Case 2: . Then there exist at least one vertex in
, say , such that . Let be any vertex
adjacent to . Then
n
TP
v
Tv

3dv

u
2Tu  , this means
 
2| |=21=1VNS TTuu  
Combing Case 1 and Case 2, we have


1.VNS T
Thus the proof is completed.

Remark 1: When , the trees with order
are or , respectively. So
=2,3nn
=2,3n3 P
 
=.
n
VNS TVNSP
1,3
S
When , there are two diffe-
rent trees with order in isomorphism sense, i.e.,
and . By Theorem 1 and Theorem 2,
=4n
n4 P


4
VNS P=0,

1,3 =1.VNS S
Remark 2: The lower and upper bound in Theorem 4
is the best possible, it can be shown by paths and stars,
respectively.
Theorem 5: If is any integer, where ,
then there is a tree of order such that
l
T
13ln
n

=VNSTl.
Proof. If , then . By Theorem 3, is a
tree of order satisfying , the conclu-
sion holds.
=4n
4
=1l2,2 C

2,2 =1VNS C
Now we assume and distinguish two cases.
5n
Case 1: or =1l3n

. If , by Theorem 1,
is a tree of order satisfying ; if
3nn P
n

=1
n
VNS P
=ln3

, by Theorem 2, S is a tree of order
satisfying
1, 1nn


1=n 1,n
S3VNS

, the conclusion holds.
Case 2: 1<<3ln

. Then . By Theorem 3, 4nl
,nll
C

is a tree satisfying , the con-
clusion holds.

,nll
VNSC 

=l

Theorem 6: 1) When , is the unique tree
with order such that .
5n
VNS
1, 1n
S

T Tn=3n
2) When , is the unique tree with order
such
that
7nn P T
n


T=n3VNS

.
Proof. 1) Let T be a tree with order such that n


=VNS Tn3

. Assume is an VN set of , SST
then . Otherwise, if
T2, then

3VTSnS

,
so


3TS n   and
 
<3VNS TT SSn  

 ,
a contradiction.
Let


v be an VNS

set of . Then T


=1=TS VNSTn  2
But




2TT vn

, so and

=1dvTS is
2n

isolated vertices. Clearly, the star graph, 1,1n S

, is
the unique tree in this case.
2) If and is not isomorphic to , then 7nTn P


T3

. We distinguish two cases.
Case 1:


=3T.
Assume


uVT and


=3du , denote




=,,Nu xyz.
Case 1.1: If there are at least two vertices in


Nu
such that their degree are . Then
3


4Tu  . Thus


3VNST.
Case 1.2: If there is unique vertex, say
x
, in


Nu
such that


=3dx . Then . We con-
sider the following two possibilities.
 
2,dy dz

2
Case 1.2.1: If both


dy and are . Then

dz 2






3, 2Tu VNST  .
Case 1.2.2: If both


dy and are 1. Assume

dz






=,Nx ust. Since , there is at least one
vertex in
7n


,
s
t, say , such that . Thus s

ds2




3Tu  , and


2VNS T.
Case 1.3: The degree of ,
x
y and all are at most
. We discuss three possibilities.
z
2

Z. T. WEI ET AL.
162
Case 1.3.1: If there is unique vertex, say , such that
. Since , clearly,
z

=2dz7n


3 Tu  and

2VNS T.
Case 1.3.2: If there are exact two vertices, say ,
such that . Since , we have
, yz
 
=2,=2dy dz7n
 
3

Figure 1. The trees of order 6 such that VNS = 1.
Ty  or

3Tz  . So .

VNS T23. Acknowledgements
Case 1.3.3: If



===dx dydz2, obviously
 
3Tu  . So .

2VNS T
This work was supported by the SXESF (Grant 09JK545)
and the BSF (Grant JC0924).
Case 2: .

4T 4. References
Assume


4du

, is any vertex adjacent to .
Then
v u

3,Tv [1] Z. Wei, A. Mai and M. Zhai, “Vertex-Neighbor-Scattering
Number of Graphs,” Ars Combinatoria, Vol. 102, 2011.

2T  VNS .
Therefore, we have


2VNS T
=n T
if , con-
tradicted to . Thus and the proof is
c ompleted.
n
TP

=1VNS TP

[2] F. Li and X. Li, “Computational Complexity and Bounds
for Neighbor-Scattering Number of Graphs,” 8th Interna-
tional Symposium on Parallel Architectures, Algorithms
and Networks, Las Vegas, 7-9 December 2005, pp.
478-483. doi:10.1109/ISPAN.2005.30
Remark 3: and are the two trees with order
such that . There are six non-isomorphic
trees with order . The three trees with order such
that are shown in Figure 1.
5
P
VNS
6
3,2
C
5=1
6
=1 VNS
[3] J. A. Bondy and U. S. R. Murty, “Graph Theory with
Applications,” Macmillan, London, 1976.