1.
Centrality in connected graphs via convexity or concavityDinesh Pandey,
Kamal Lochan Patra, 2026, original scientific article
Abstract: In graph theory, several central parts of graphs have been defined. The center, median and the security center are three such concepts defined for any connected graph, while others are specific to trees. These definitions typically involve a function defined on the vertex set of the graph.
This paper generalizes the concepts of convex and concave functions, originally defined for trees, to connected graphs. Using this, we provide a unified approach to prove the known results that each of the center, median, and security center of a connected graph is either a cut vertex or lies within a block. Additionally, we introduce three new central parts of a connected graph as generalizations of the subtree core, core vertices, and characteristic set of a tree, and examine their properties in relation to the center, median, and security center. We also show that for any graph G, there exists a supergraph G' such that the subgraph induced by the characteristic center of G' is isomorphic to G. Finally, we propose several open problems related to subgraph core and core center.
Keywords: Center, characteristic center, convex and concave functions, core center, median, security center, subgraph core
Published in RUP: 17.08.2026; Views: 254; Downloads: 4
Full text (388,93 KB)
