Residual Closeness of Graphs with Given Parameters

doi:10.1007/s40305-022-00405-9

Journal of the Operations Research Society of China ›› 2023, Vol. 11 ›› Issue (4): 839-856.doi: 10.1007/s40305-022-00405-9

Previous Articles Next Articles

Residual Closeness of Graphs with Given Parameters

Mei-Qun Cheng, Bo Zhou

School of Mathematical Sciences, South China Normal University, Guangzhou, 510631, Guangdong, China

Received:2021-07-13 Revised:2022-02-16 Online:2023-12-30 Published:2023-12-26
Contact: Bo Zhou, Mei-Qun Cheng E-mail:zhoubo@scnu.edu.cn;1677098467@qq.com
Supported by:
This work was supported by the National Natural Science Foundation of China (No. 12071158).

Abstract

Abstract: Robustness of the network topology is a key aspect in the design of computer networks. Residual closeness is a new graph-theoretic concept defined as a measure of network robustness due to the failure of individual vertices. We identify those graphs with maximum residual closeness among connected graphs with fixed connectivity, edge connectivity and bipartiteness, respectively.

Key words: Residual closeness, Connectivity, Edge connectivity, Bipartiteness

CLC Number:

Mei-Qun Cheng, Bo Zhou. Residual Closeness of Graphs with Given Parameters[J]. Journal of the Operations Research Society of China, 2023, 11(4): 839-856.

TrendMD

References

[1] Frank, H., Frisch, I.T.: Analysis and design of survivable networks. IEEE Trans. Commun. Technol. 18(5), 501-519 (1970)
[2] Chvatal, V.: Tough graphs and Hamiltonian circuits. Discrete Math. 5(3), 215-228 (1973)
[3] Jung, H.A.: On a class of posets and the corresponding comparability graphs. J. Combin. Theory Ser. B 24(2), 125-133 (1978)
[4] Woodall, D.R.: The binding number of a graph and its Anderson number. J. Combin. Theory Ser. B 15(3), 225-255 (1973)
[5] Dangalchev, C.: Residual closeness in networks. Physica A 365(2), 556-564 (2006)
[6] Buckley, F., Harary, F.: Distance in Graphs. Addison-Wesley Publishing Company, Redwood City (1990)
[7] Jackson, M.O.: Social and Economic Networks. Princeton University Press, Princeton (2008)
[8] Dangalchev, C.: Residual closeness and generalized closeness. Int. J. Found. Comput. Sci. 22(8), 1939-1948 (2011)
[9] Dangalchev, C.: Residual closeness of generalized thorn graphs. Fundam. Inform. 162(1), 1-15 (2018)
[10] Aytac, A., Odabas, Z.N.: Residual closeness of wheels and related networks. Int. J. Found. Comput. Sci. 22(5), 1229-1240 (2011)
[11] Odabas, Z.N., Aytac, A.: Residual closeness in cycles and related networks. Fundam. Inform. 124(3), 297-307 (2013)
[12] Aytac, A., Berberler, Z.N.O.: Robustness of regular caterpillars. Int. J. Found. Comput. Sci. 28(7), 835-841 (2017)
[13] Aytac, A., Berberler, Z.N.O.: Residual closeness for helm and sunflower graphs. TWMS J. Appl. Eng. Math. 7(2), 209-220 (2017)
[14] Aytac, A., Odabas Berberler, Z.N.: Network robustness and residual closeness. RAIRO Oper. Res. 52(3), 839-847 (2018)
[15] Rupnik Poklukar, D., Žerovnik, J.: Networks with extremal closeness. Fundam. Inform. 167(3), 219-234 (2019)
[16] Zhou, B., Li, Z., Guo, H.: Extremal results on vertex and link residual closeness. Int. J. Found. Comput. Sci. 32(8), 921-941 (2021)
[17] Bondy, J.A., Murty, U.S.R.: Graph Theory. Springer, New York (2008)
[18] Lewis, J.M., Yannakakis, M.: The node-deletion problem for hereditary properties is NP-complete. J. Comput. Syst. Sci. 20(2), 219-230 (1980)
[19] Fallat, S., Fan, Y.: Bipartiteness and the least eigenvalue of signless Laplacian of graphs. Linear Algebra Appl. 436(9), 3254-3267 (2012)
[20] Yarahmadi, Z., Ashrafi, A.R.: Extremal properties of the bipartite vertex frustration of graphs. Appl. Math. Lett. 24(11), 1774-1777 (2011)
[21] Boccaletti, S., Buldú, J., Criado, R., Flores, J., Latora, V., Pello, J.: Multiscale vulnerability of complex networks. Chaos 17(4), 043110 (2007)
[22] Holme, P., Kim, B.J., Yoon, C.N., Han, S.K.: Attack vulnerability of complex networks. Phys. Rev. E. 65(5), 056109 (2002)

Residual Closeness of Graphs with Given Parameters

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 4

Recommended Articles

Metrics

Comments

[1]	Lin-Ken Tong, Er-Fang Shan. Sufficient Conditions for Maximally Edge-Connected Hypergraphs [J]. Journal of the Operations Research Society of China, 2021, 9(1): 119-129.
[2]	Jing Jin, Bao-Gang Xu. Connectivity of Minimum Non-5-injectively Colorable Planar Cubic Graphs [J]. Journal of the Operations Research Society of China, 2020, 8(1): 105-116.
[3]	Hui Shang, Eminjan Sabir, Ji-Xiang Meng. Conditional Edge Connectivity of the Locally Twisted Cubes [J]. Journal of the Operations Research Society of China, 2019, 7(3): 501-509.
[4]	Han－Yuan Deng · He Huang · Jie Zhang. On the Eigenvalues of General Sum-Connectivity Laplacian Matrix [J]. Journal of the Operations Research Society of China, 2013, 1(3): 347-358.