as an extension of the concept of neighbor-scattering number of graphs
we introduce the notion of neighbor-scattering number of digraphs.Let D =(V
A) be a digraph.The open and closed out-neighborhoods of a set SV are denoted by N+(S) = {u:vu∈A(D)
v∈S} and N+[S]= N+(S)∪{S}
respectively.A cut strategy of D is a subset S of V(D) such that N+[S]is deleted from D.The neighbor-scattering number S(D) of a digraph D is defined as S(D) = max sv{ω(D/S+)-|S|
S is cut-strategy of D}
where D/S+:= D-N+[S]andω(D/S+) is the number of strongly connected components in the digraph D/S+.We first discuss some basic properties of the neighbor-scattering number of digraphs
and then we study the minimum neighbor-scattering number of the orientations of Kn and Ks
t.
关键词
Keywords
references
Barefoot C A,Entringer R,Swart H.Vulnersbility in Graphs-a Comparative Survey[J].J Combin Math Combin Comput, 1987,1:13-22.
Wei Z,(supervisor Li X).On the reliability parameters of networks[C].M.S.Thesis,Northwestern Polytechnical University, Xi'an,2003,30-40.
Li F,Li X.Computational complexity and bounds for neighbor-scattering number of graphs[J].in:Proc.ISPAN 2005, IEEE Computer Society,Nevade,Las Vegas,USA,2005.
Li F,Li X.The neighbour-scattering number can be computed in polynomial time for interval graphs[J].Computers and Mathematics with Applications,2007,54:679-686.
Guo J,Vumar E.The vertex-neighbor-integrity of digraphs[J].Lecture Notes on Computer Science,2007,4489:370-376.
Vandell R C.Maximum arc-integrity of tournaments and bipartite tourment[J].to appear in:Proceedings of the ninth quadrennial international conference in graph theory,combinatorics,algorithm,and applications.
京公网安备11010802024621