### Paper Menu >>

### 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 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 * SVGVN 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 5nS 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 3nn P n =1 n VNS P =ln3 , by Theorem 2, S is a tree of order satisfying 1, 1nn 1=n 1,n S3VNS , 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 7nn 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 , SST 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 7nTn 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 7n , s t, say , such that . Thus s ds2 3Tu , and 2VNS T. Case 1.3: The degree of , x y and all are at most . We discuss three possibilities. z 2 Copyright © 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 T23. 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. |