• Masrurotullaily Masrurotullaily Department of Mathematics Education, Universitas Islam Negeri Kiai Haji Achmad Siddiq Jember
Keywords: degree, betweenness, closeness, centrality, Brinkmann, node deletion


Brinkmann graph is a 4-regular graph with 21 nodes and 42 edges discovered by Gunnar Brinkmann in 1992. To our knowledge, the research specifically on Brinkmann graph is still hard to find. Therefore, this research was carried out to analyze the Brinkmann graph in term of its centrality. The centrality measures used are degree, betweenness, and closeness centrality. In this paper, we presented the centrality measures not only on the Brinkmann graph but also on the Brinkmann graph after node deletion to see how the impact of node deletion to the centrality of graph. Before deletion, the results showed that according to the betweenness centrality, there exist 7 nodes who act as mediators or bridges in the Brinkmann graph. Therefore, when a node among these nodes has deleted, it affected not only any other mediator nodes and the furthest nodes from the deleted node but also the nodes that are adjacent to the deleted nodes.


Download data is not yet available.


W. D. Joyner and C. G. Melles, Adventures in Graph Theory. Springer International Publishing, 2017. [Online]. Available: https://books.google.co.id/books?id=NdFEDwAAQBAJ

W. Commons, “File:Brinkmann graph LS.svg — Wikimedia Commons, the free media repository.” 2020. [Online]. Available: https://commons.wikimedia.org/w/index.php?title=File:Brinkmann_graph_LS.svg&oldid=453381461

J. Liang, D. Lou, Z. Qin, and Q. Yu, “A polynomial algorithm determining cyclic vertex connectivity of 4-regular graphs,” J Comb Optim, vol. 38, no. 2, pp. 589–607, 2019.

N. Ramya and M. Muthukumar, “On coloring of 4-regular graphs,” International Journal of Pure and Applied Mathematics, vol. 116, 2020.

G. Lancia, E. Pippia, and F. Rinaldi, “Proving hamiltonian properties in connected 4-regular graphs: an ILP-based approach,” arXiv preprint arXiv:2112.05087, 2021.

W. Liu, Q. Cui, and Y. Wang, “On 4-connected 4-regular graphs without even cycle decompositions,” Discrete Mathematics, vol. 345, no. 10, p. 113012, 2022, doi: https://doi.org/10.1016/j.disc.2022.113012.

S. P. Tahalea, E. Salouw, and A. W. A. Wibowo, “TOURISM ON INSTAGRAM: A SOCIAL NETWORK ANALYSIS,” BAREKENG, vol. 16, no. 1, pp. 199–206, Mar. 2022.

J. Zhang and Y. Luo, “Degree centrality, betweenness centrality, and closeness centrality in social network,” in 2017 2nd international conference on modelling, simulation and applied mathematics (MSAM2017), 2017, pp. 300–303.

C. Sciarra, G. Chiarotti, F. Laio, and L. Ridolfi, “A change of perspective in network centrality,” Scientific Reports, vol. 8, no. 1, p. 15269, 2018, doi: 10.1038/s41598-018-33336-8.

K. Das, S. Samanta, and M. Pal, “Study on centrality measures in social networks: a survey,” Social Network Analysis and Mining, vol. 8, no. 1, p. 13, 2018, doi: 10.1007/s13278-018-0493-2.

R. B. Bapat, Graphs and Matrices. Springer London, 2014. [Online]. Available: https://books.google.co.id/books?id=LWCSBAAAQBAJ

Y. Yustiawan, W. Maharani, and A. A. Gozali, “Degree Centrality for Social Network with Opsahl Method,” Procedia Computer Science, vol. 59, pp. 419–426, 2015, doi: 10.1016/j.procs.2015.07.559.

J. Matta, G. Ercal, and K. Sinha, “Comparing the speed and accuracy of approaches to betweenness centrality approximation,” Computational Social Networks, vol. 6, no. 1, p. 2, 2019, doi: 10.1186/s40649-019-0062-5.

I. Tsalouchidou, R. Baeza-Yates, F. Bonchi, K. Liao, and T. Sellis, “Temporal betweenness centrality in dynamic graphs,” International Journal of Data Science and Analytics, vol. 9, no. 3, pp. 257–272, 2020, doi: 10.1007/s41060-019-00189-x.

R. Goldstein and M. S. Vitevitch, “The influence of closeness centrality on lexical processing,” Front Psychol, vol. 8, p. 1683, 2017.

How to Cite
M. Masrurotullaily, “CENTRALITY MEASURES ON BRINKMANN GRAPH: BEFORE AND AFTER NODE DELETION”, BAREKENG: J. Math. & App., vol. 16, no. 3, pp. 1097-1104, Sep. 2022.