### Journal Menu >> Advances in Pure Mathematics, 2011, 1, 160-162 doi:10.4236/apm.2011.14029 Published Online July 2011 (http://www.SciRP.org/journal/apm) Copyright © 2011 SciRes. 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 E-mail: wzt6481@163.com, xianliuyong@126.com, anchan.mai@eyou.com 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 GGS is disconnected, or is a clique, or is . The vertex-neighbor-scattering number of is defined to be G ()=maxSVGVNS 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  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 . As many graphic parameters, the computing problem of this parameter is complete . So we discuss the properties of the vertex-neighbor-scattering number of trees in this paper. Our definitions follow . 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 SG()=maxSVGVNSGG SS, where is any cut- Sstrategy 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 nK to be 1. A comet is a graph obtained by identifying one end of a path ,trC2tP with the center of a star 1, 2rSr,.trC. The center of is called the center of 1,rS,|Nuu vuadjacent=NuuNuu 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 SGS is dis- connected, or is a clique, or is . The following lemmata will be used in the next section. Theorem 1:  Let be a path with order nP3.n Then 0,if=3, 4=1, if5nnVNS Pn Theorem 2:  Let 1, 2rSr be a star. Then 1, =2rVNS Sr. Theorem 3:  Let be a comet, both and are at least Then ,trCt r2. Z. T. WEI ET AL. 161.,1,if= 2,3=,if4trrtVNS Crt 2. Vertex-Neighbor-Scattering Number of Trees Theorem 4: Let be a tree with order Then T13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 VNT5nSset , S1S and 2TS n. Thus we have  ()21 3maxSVTVNS TTSSnn 2) We distinguish two cases to prove . 1VNS TCase 1: . Since , there must exist a vertex such that nTPT5nvV=2Tv. So ()max211SVTVNS TTSSTv v Case 2: . Then there exist at least one vertex in , say , such that . Let be any vertex adjacent to . Then nTPvTv3dvu2Tu, 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,3n3P=.nVNS TVNSP1,3S When , there are two diffe- rent trees with order in isomorphism sense, i.e., and . By Theorem 1 and Theorem 2, =4nn4P4VNS P=0, 1,3 =1.VNS SRemark 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 lT13lnn=VNSTl. Proof. If , then . By Theorem 3, is a tree of order satisfying , the conclu- sion holds. =4n4=1l2,2C2,2 =1VNS CNow we assume and distinguish two cases. 5nCase 1: or =1l3n. If , by Theorem 1, is a tree of order satisfying ; if 3nnPn=1nVNS P=ln3, by Theorem 2, S is a tree of order satisfying 1, 1nn1=n1,nS3VNS, the conclusion holds. Case 2: 1<<3ln. Then . By Theorem 3, 4nl,nllC is a tree satisfying , the con- clusion holds. ,nllVNSC =l Theorem 6: 1) When , is the unique tree with order such that . 5nVNS1, 1nSTTn=3n2) When , is the unique tree with order such that 7nnP TnT=n3VNS. Proof. 1) Let T be a tree with order such that n=VNS Tn3. Assume is an VN set of , SSTthen . 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,1nS, is the unique tree in this case. 2) If and is not isomorphic to , then 7nTnP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,st, say , such that . Thus sds23Tu, and 2VNS T. Case 1.3: The degree of ,xy and all are at most . We discuss three possibilities. z2Copyright © 2011 SciRes. APM Z. T. WEI ET AL. Copyright © 2011 SciRes. APM 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  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=nT if , con- tradicted to . Thus and the proof is completed. nTP=1VNS TP  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. 5PVNS63,2C5=16=1VNS J. A. Bondy and U. S. R. Murty, “Graph Theory with Applications,” Macmillan, London, 1976.