Centrality in connected graphs via convexity or concavity

angleški

2026

letnik 26, številka 3, article p3.02

center   jedro centra   jedro podgrafa   karakteristični center   konveksne in konkavne funkcije   mediana   varnostni center

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

V teoriji grafov je bilo definiranih več centralnih delov grafov. Center, mediana in varnostni center so trije takšni pojmi, definirani za vsak povezan graf, medtem ko so nekateri drugi specifični za drevesa. Te definicije običajno temeljijo na funkciji, definirani na množici vozlišč grafa. V tem članku posplošimo pojma konveksne in konkavne funkcije, ki sta bila prvotno definirana za drevesa, na povezane grafe. Na tej osnovi podamo enoten pristop za dokazovanje znanih rezultatov, da je vsak izmed centra, mediane in varnostnega centra povezanega grafa bodisi ločitveno vozlišče bodisi leži znotraj bloka. Poleg tega uvedemo tri nove centralne dele povezanega grafa kot posplošitve jedra poddrevesa, jedrnih vozlišč in karakteristične množice drevesa ter preučimo njihove lastnosti v povezavi s centrom, mediano in varnostnim centrom. Pokažemo tudi, da za vsak graf G obstaja nadgraf G', tako da je podgraf, induciran s karakterističnim centrom grafa G', izomorfen grafu G. Nazadnje predlagamo več odprtih problemov, povezanih z jedrom podgrafa in jedrom centra.

27.10.2026