×

Isolated scattering number of split graphs and graph products. (English) Zbl 1373.90029

Summary: Computer or communication networks are so designed that they do not easily get disrupted under external attack. Moreover, they are easily reconstructed when they do get disrupted. These desirable properties of networks can be measured by various parameters, such as connectivity, toughness and scattering number. Among these parameters, the isolated scattering number is a comparatively better parameter to measure the vulnerability of networks. In this paper we first prove that for split graphs, this number can be computed in polynomial time. Then we determine the isolated scattering number of the Cartesian product and the Kronecker product of special graphs and special permutation graphs.

MSC:

90B18 Communication networks in operations research
94C15 Applications of graph theory to circuits and networks
05C40 Connectivity
05C90 Applications of graph theory
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Alon, N.; Lubetzky, E., Independent set in tensor graph powers, J. Graph Theory, 54, 73-87, (2007) · Zbl 1108.05068 · doi:10.1002/jgt.20194
[2] Arika, T.; Shibata, Y., Optimal design of diagnosable systems on networks constructed by graph operations, Electron. Commun. Japan, 85, 1-9, (2002)
[3] Barefoot, C. A.; Entringer, R.; Swart, H., Vulnerability in graphs - A comparative survey, J. Combin. Math. Combin. Comput., 1, 12-22, (1987) · Zbl 0646.05042
[4] Bondy, J. A.; Murty, U. S. R., Graph theory with applications, pp., (1976), North-Holland, New York · Zbl 1226.05083 · doi:10.1007/978-1-349-03521-2
[5] Bres̆ar, B.; Imrich, W.; Klavz̆ar, S.; Zmazek, B., Hypercubes as direct products, SIAM J. Discrete Math., 18, 778-786, (2005) · Zbl 1075.05073 · doi:10.1137/S0895480103438358
[6] Chartrand, G.; Harary, F., Planar permutation graphs, Ann. Inst. H. Poincaré Sec. B (N.S.), 3, 433-438, (1967) · Zbl 0162.27605
[7] Chvátal, V., Tough graphs and Hamiltonian circuits, Discrete Math., 5, 215-228, (1973) · Zbl 0256.05122 · doi:10.1016/0012-365X(73)90138-6
[8] Cozzens, M.; Moazzami, D.; Stueckle, S., The tenacity of a graph, Proceedings of 7th International Conference on the Theory and Applications of Graphs, 1111-1122, (1995), Wiley, New York · Zbl 0845.05088
[9] Foldes, S.; Hammer, P. L., Split graphs having dilworth number two, Can. J. Math., 29, 666-672, (1977) · Zbl 0335.05130 · doi:10.4153/CJM-1977-069-1
[10] Ghozati, S. A., A finite automata approach to modeling the cross product of interconnection networks, Math. Comput. Modelling, 30, 185-200, (1999) · Zbl 1042.68505 · doi:10.1016/S0895-7177(99)00173-9
[11] Grötschel, M.; Lovász, L.; Schrijver, A., Geometric algorithms and combinatorial optimization, pp., (1988), Springer, Berlin · Zbl 0634.05001 · doi:10.1007/978-3-642-97881-4
[12] Jung, H. A., On maximal circuits in finite graphs, Ann. Discrete Math., 3, 129-144, (1978) · Zbl 0399.05039 · doi:10.1016/S0167-5060(08)70503-X
[13] Lammprey, R. H.; Barnes, B. H., Products of graphs and applications, Model. Simul., 5, 1119-1123, (1974)
[14] Li, F. W., Isolated rupture degree of trees and gear graphs, Neural Network World, 25, 287-300, (2015) · doi:10.14311/NNW.2015.25.015
[15] Li, F. W., On isolated rupture degree of graphs, Util. Math., 96, 33-47, (2015) · Zbl 1321.05131
[16] Li, Y. K.; Zhang, S. G.; Li, X. L., Rupture degree of graphs, Int. J. Comput. Math., 82, 793-803, (2005) · Zbl 1074.05053 · doi:10.1080/00207160412331336062
[17] Mamut, A.; Vumar, E., Vertex vulnerability parameters of Kronecker products of complete graphs, Inform. Process. Lett., 106, 258-262, (2008) · Zbl 1185.05093 · doi:10.1016/j.ipl.2007.12.002
[18] Quinn, M. J., Parallel computing: theory and practice, pp., (1994), McGraw-Hill, New York
[19] Schrijver, A., A combinatorial algorithm minimizing submodular functions in strongly polynomial time, J. Combin. Theory Ser. B, 80, 346-355, (2000) · Zbl 1052.90067 · doi:10.1006/jctb.2000.1989
[20] Wang, S. Y.; Yang, Y. X.; Lin, S. W.; Li, J.; Hu, Z. M., The isolated scattering number of graphs, Acta Math. Sinica, 54, 861-874, (2011) · Zbl 1249.05226
[21] Woeginger, G. J., The toughness of split graphs, Discrete Math., 190, 295-297, (1998) · Zbl 0955.05103 · doi:10.1016/S0012-365X(98)00156-3
[22] Zhang, S. G.; Li, X. L.; Han, X. L., Computing the scattering number of graphs, Int. J. Comput. Math., 79, 179-187, (2002) · Zbl 1017.05095 · doi:10.1080/00207160211919
[23] Zhang, S. G.; Zhang, Q. L.; Yang, H. W., Vulnerability parameters of split graphs, Int. J. Comput. Math., 85, 19-23, (2008) · Zbl 1130.05033 · doi:10.1080/00207160701365721
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.