The Isolated Scattering Number of Graphs

doi:10.12386/A2011sxxb0087

Acta Mathematica Sinica, Chinese Series 鈥衡�� 2011, Vol. 54 鈥衡�� Issue (5): 861-874.DOI: 10.12386/A2011sxxb0087

鈥� Articles 鈥� Previous Articles Next Articles

The Isolated Scattering Number of Graphs

Shi Ying WANG¹, Yu Xing YANG², Shang Wei LIN¹, Jing LI¹, Zhi Ming HU¹

1. School of Mathematical Science, Shanxi University, Taiyuan, 030006, P. R. China
2. School of Computer Science and Technology, Shanxi University,Taiyuan 030006, P. R. China

Received:2010-08-23 Revised:2011-04-02 Online:2011-09-15 Published:2011-09-15

鍥剧殑瀛ょ珛鏂搴�

鐜嬩笘鑻�¹, 鏉ㄧ帀鏄�², 鏋椾笂涓�¹, 鏉庢櫠¹, 鑳″織鏄�¹

1. 灞辫タ澶у鏁板绉戝瀛﹂櫌澶師 030006
2. 灞辫タ澶у璁＄畻鏈轰笌淇℃伅鎶�鏈闄� 澶師 030006

鍩洪噾璧勫姪:
鍥藉鑷劧绉戝鍩洪噾璧勫姪椤圭洰(61070229)

Abstract

Abstract: The isolated scattering number isc(G) = max{i(G - S) - |S| : S ∈ C(G)}, where G is a connected graph, i(G - S) is the number of isolated vertices of G - S and C(G) is the set of vertex cuts of G. In this paper, we investigate the relationships between the isolated scattering number and other parameters of a graph G, and discuss the graphs with special isolated scattering numbers. We prove that the isolated scattering numbers of a cycle, a connected bipartite graph, the join of connected bipartite graphs and the complement of a tree and a cycle are minimal, and give the maximum and minimum isolated scattering numbers of trees with given order and maximum degree.

Key words: networks, vulnerability, isolated scattering number

鎽樿锛� 杩為�氬浘G鐨勫绔嬫柇瑁傚害isc(G)=max{i(G-S)-|S|: S ∈ C(G)}, 鍏朵腑i(G-S)鏄�G-S涓殑瀛ょ珛鐐规暟, C(G)鏄�G鐨勭偣鍓查泦.鏈枃鐮旂┒浜嗗绔嬫柇瑁傚害鍜屽浘鐨勫叾瀹冧竴浜涘弬鏁扮殑鍏崇郴.璁ㄨ浜嗗绔嬫柇瑁傚害鍙栫壒娈婂�肩殑涓�浜涘浘,璇佹槑浜嗗湀銆佽繛閫氫簩閮ㄥ浘銆佽繛閫氫簩閮ㄥ浘鐨勮仈鍥句互鍙婃爲鍜屽湀鐨勮ˉ鍥剧殑瀛ょ珛鏂搴﹂兘杈惧埌鏈�灏�.缁欏嚭浜嗗叿鏈夌粰瀹氶樁鏁板拰鏈�澶у害鐨勬爲鐨勬渶澶с�佹渶灏忓绔嬫柇瑁傚害.

鍏抽敭璇�: 缃戠粶, 鍙潬鎬�, 瀛ょ珛鏂搴�

CLC Number:

O157.5

Shi Ying WANG, Yu Xing YANG, Shang Wei LIN, Jing LI, Zhi Ming HU. The Isolated Scattering Number of Graphs[J]. Acta Mathematica Sinica, Chinese Series, 2011, 54(5): 861-874.

鐜嬩笘鑻�, 鏉ㄧ帀鏄�, 鏋椾笂涓�, 鏉庢櫠, 鑳″織鏄�. 鍥剧殑瀛ょ珛鏂搴J]. 鏁板瀛︽姤, 2011, 54(5): 861-874.

References

[1] Bondy J. A., Murty U. S. R., Graph Theory, New York: Springer, 2007.

[2] Bauer D., Broersma H. J., Morgana A., Schmeichel E., Tutte sets in graphs I: maximal Tutte sets and D-graphs, Journal of Graph Theory, 2007, 55(4): 343–358.

[3] Bauer D., Broersma H. J., Kahl N., Morgana A., Schmeichel E., Surowiec T., Tutte sets in graphs II: The complexity of finding maximum Tutte sets, Discrete Applied Mathematics, 2007, 155(15): 1336–1343.

[4] Busch A., Ferrara M-, Kahl N., Generalizing D-graphs, Discrete Applied Mathematics, 2007, 155(18): 2487–2495.

[5] Traldi L., Parallel connections and coloured Tutte polynomials, Discrete Mathematics, 2005, 290(2/3): 291–299.

[6] Jung H. A., On a class of posets and the corresponding comparability graphs, Journal of Combinatorial Theory Series B, 1978, 24(2): 125–133.

[7] Giakoumakis V., Roussel F., Thuillier H. Scattering number and modular decomposition, Discrete Mathematics, 1997, 165/166(15): 321–342.

[8] Kirlangic A., A measure of graph vulnerability: scattering number, International Journal of Mathematics and Mathematical Sciences, 2002, 30(1): 1–8.

[9] Li F. W., Li X. L., The neighbour-scattering number can be computed in polynomial time for interval graphs, Computers and Mathematics with Applications, 2007, 54(5): 679–686.

[10] Kratsch D., Kloks T., Müller H., Measuring the vulnerability for classes of intersection graphs, Discrete Applied Mathematics, 1997, 77(3): 259–270.

[11] Zhang S. G., Wang Z. G., Scattering number in graphs, Networks, 2001, 37(2): 102–106.

[12] Edward R., Scheinerman E, Ullman D H., Fractional Graph Theory: A Rational Approach to the Theory of Graphs, New York: John Wiley and Sons Inc, 1997.

[13] Liu Y., Liu G. Z., The fractional matching numbers of graphs, Networks, 2002, 40(4): 228–231.

[14] Bermond J. C., Homobono N, Peyrat C., Large fault-tolerant interconnection networks, Graphs and Combinatorics, 1989, 5(1): 107–123.

[15] Ou J. P., Zhang F. J., Super restricted edge connectivity of Kautz graphs, ACTA Mathematica Sinica, Chinese Series, 2004, 47(5): 931–940.

The Isolated Scattering Number of Graphs

鍥剧殑瀛ょ珛鏂搴�

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles 0

Metrics

Comments

Share

[1]	Yu FAN, Ying Ying HU, Yi SUN, Pei HENG. Marginal Markov Subgraph of Bayesian Network and Its Applications [J]. Acta Mathematica Sinica, Chinese Series, 2024, 67(3): 565-581.
[2]	Xian Yuan WU, Rui ZHU. On the Modified Newman-Watts Small World and Its Random Walk [J]. Acta Mathematica Sinica, Chinese Series, 2020, 63(2): 181-192.
[3]	Shou LIN, Yan Hui HUANG, Jing ZHANG. Point-star Networks and Images of Metric Spaces [J]. Acta Mathematica Sinica, Chinese Series, 2019, 62(6): 865-878.
[4]	Guo Chun MA, Dan Sheng YU, Ping ZHOU. On Approximation by Univariate Sigmoidal Neural Networks [J]. Acta Mathematica Sinica, Chinese Series, 2014, 57(1): 89-100.
[5]	Zhi Xiang CHEN, Fei Long CAO. Construction and Approximation of Spherical Neural Networks [J]. Acta Mathematica Sinica, Chinese Series, 2012, 55(4): 689-700.
[6]	Yong Quan ZHANGFei Long CAOZong Ben XU. Approximation for Neural Networks Operators of Cardaliguet-Eurrard Type [J]. Acta Mathematica Sinica, Chinese Series, 2008, 51(6): 1161-117.
[7]	Fei Long CAO; Yong Quan ZHANG. Interpolation and Approximation by Neural Networks in Distance Space [J]. Acta Mathematica Sinica, Chinese Series, 2008, 51(1): 91-98.
[8]	Fei Long CAO(1); Yong Quan ZHA. Neural Networks with Single Hidden Layer and the Best Polynomial Approximation [J]. Acta Mathematica Sinica, Chinese Series, 2007, 50(2): 385-392.
[9]	Shou LIN(1), Chuan LIU(2). k-Space Property of S_蠅脳X and Related Results [J]. Acta Mathematica Sinica, Chinese Series, 2006, 49(1): 29-38.
[10]	Jian Qin ZHOU. k-Tight Double Loop Networks and Their Infinite Families [J]. Acta Mathematica Sinica, Chinese Series, 2005, 48(6): -.
[11]	Ying GE(1), Shou LIN(2). Uniform Covers and Compact Images of Metric Spaces [J]. Acta Mathematica Sinica, Chinese Series, 2004, 47(6): 1149-115.
[12]	Jian Ping OU(1), Fu Ji ZHAO(2). Super Restricted Edge Connectivity of Kautz Graphs [J]. Acta Mathematica Sinica, Chinese Series, 2004, 47(5): 931-940.
[13]	Shou LIN(1),You Cheng ZHOU(2),. On Sequence-Covering 蟺-Mappings [J]. Acta Mathematica Sinica, Chinese Series, 2002, 45(6): 1157-116.
[14]	Shou LIN(1),Peng Fei YAN(2). On Sequence-Covering Compact Mappings [J]. Acta Mathematica Sinica, Chinese Series, 2001, 44(1): 175-182.
[15]	Jin Jin LI(1),Wei Yuan CAI(2). Notes on Sequence-Covering s-Mappings [J]. Acta Mathematica Sinica, Chinese Series, 2000, 43(4): 757-762.