20.500.12556/RUP-22009 On a generalization of median graphs: k-median graphs Posplošitev medianskih grafov: k-medianski grafi Median graphs are connected graphs in which for all three vertices there is a unique vertex that belongs to shortest paths between each pair of these three vertices. To be more formal, a graph G is a median graph if, for all μ, u, v ∈ V(G), it holds that |I(μ, u) ∩ I(μ, v) ∩ I(u, v)| = 1 where I(x, y) denotes the set of all vertices that lie on shortest paths connecting x and y. In this paper we are interested in a natural generalization of median graphs, called k-median graphs. A graph G is a k-median graph, if there are k vertices μ1, …, μk ∈ V(G) such that, for all u, v ∈ V(G), it holds that |I(μ_i, u) ∩ I(μ_i, v) ∩ I(u, v)| = 1, 1 ≤ i ≤ k. By definition, every median graph with n vertices is an n-median graph. We provide several characterizations of k-median graphs that, in turn, are used to provide many novel characterizations of median graphs. median graph convexity meshed and quadrangle property modular interval medianski graf konveksnost mrežna in štirikotniška lastnost modularen interval true false true Založba Univerze na Primorskem Angleški jezik Slovenski jezik Članek v reviji 2025-10-22 13:02:56 2025-10-22 13:02:56 2025-11-14 03:04:47 0000-00-00 00:00:00 2025 0 0 27 str. no. 3, [article no.] P3.06 Vol. 25 2025 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 2025-05-29 519.17 1855-3974 https://doi.org/10.26493/1855-3974.3134.87b AMC_Hellmuth,Thekkumpadan_Puthiyaveedu_2025.pdf AMC_Hellmuth,Thekkumpadan_Puthiyaveedu_2025.pdf 1 0CD964F4071F89B35B1242D37990B92E 6b336e1c10dbc0257d6db82ad26ef8a6b1b561f37d1d4bcdff5ad49fea1492a8 648a08e8-af37-11f0-8f0b-005056ac49c0 https://repozitorij.upr.si/Dokument.php?lang=slv&id=31945 Založba Univerze na Primorskem 0 0 0