20.500.12556/DKUM-90235 On general position sets in Cartesian products Množice v splošni legi v kartezičnih produktih The general position number gp(G) of a connected graph G is the cardinality of a largest set S of vertices such that no three distinct vertices from S lie on a common geodesic; such sets are refereed to as gp-sets of G. The general position number of cylinders Pr ◻ Cs is deduced. It is proved that (Cr ◻ Cs)∈{6,7} whenever r ≥ s ≥ 3, s ≠ 4, and r ≥ 6. A probabilistic lower bound on the general position number of Cartesian graph powers is achieved. Along the way a formula for the number of gp-sets in Pr ◻ Ps, where r,s ≥ 2, is also determined. Število splošne lege gp(G) povezanega grafa G je moč največje množice vozlišč S, tako da nobena trojica različnih vozlišč iz S ne leži na skupni najkrajši poti. Takim množicam na kratko pravimo gp-množice grafa G. Določeno je število splošne lege cilindrov Pr ◻ Cs. Dokazano je, da za vse r ≥ s ≥ 3, s ≠ 4, in r ≥ 6 velja (Cr ◻ Cs)∈{6,7}. Dokazana je verjetnostna spodnja meja za število splošne lege kartezičnih potenc. Izpeljana je tudi formula za število gp-množic v produktih Pr ◻ Ps, r,s ≥ 2. general position problem Cartesian product of graphs paths and cycles probabilistic constructions exact enumeration problem splošne lege kartezični produkt grafov poti in cikli verjetnostne konstrukcije točno preštevanje true false true Birkhäuser Angleški jezik Slovenski jezik Znanstveno delo 2024-08-27 08:41:47 2024-08-27 09:19:54 2024-08-28 03:19:35 0000-00-00 00:00:00 2021 0 0 Str. 1-21 Št. 3, št. članka 123 Letn. 76 Aug. 2021 0000-00-00 Zaloznikova Objavljeno NiDoloceno 2020-11-04 2021-05-17 2021-05-26 519.17 64926723 10.1007/s00025-021-01438-x 1422-6383 Klavzar-2021-On_General_Position_Sets_in_Carte.pdf Klavzar-2021-On_General_Position_Sets_in_Carte.pdf 1 C14A2A5ADF9631A8E0549ABC09E7D481 15e084d723b20c9ccc4673545e9e1091fa5de0aff8d24a2d417a005b67acebba 9be18aec-6442-11ef-af0b-00155d000105 https://dk.um.si/Dokument.php?lang=slv&id=183422 https://doi.org/10.1007/s00025-021-01438-x 0 ce718be2-6442-11ef-af0b-00155d000105 https://dk.um.si/Dokument.php?lang=slv&id=183423 Fakulteta za naravoslovje in matematiko Fakulteta za organizacijske vede 0 0 0