Centrality in connected graphs via convexity or concavity

english

2026

volume 26, issue 3, article p3.02

characteristic center   convex and concave functions   core center   median   security center   subgraph core

Univerza na Primorskem, Fakulteta za naravoslovje, matematiko in informacijske tehnologije
(Obvezni izvod spletne publikacije)

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.

27.10.2026