20.500.12556/DKUM-85102 Incidence dimension and 2-packing number in graphs Incidenčna dimenzija in 2-pakirno število grafov Let ▫$G=(V,E)$▫ be a graph. A set of vertices ▫$A$▫ is an incidence generator for ▫$G$▫ if for any two distinct edges ▫$e,f \in E(G)$▫ there exists a vertex from ▫$A$▫ which is an endpoint of either ▫$e$▫ or ▫$f$▫. The smallest cardinality of an incidence generator for ▫$G$▫ is called the incidence dimension and is denoted by ▫$\dim_I(G)$▫. A set of vertices ▫$P \subseteq V(G)$▫ is a 2-packing of ▫$G$▫ if the distance in ▫$G$▫ between any pair of distinct vertices from ▫$P$▫ is larger than two. The largest cardinality of a 2-packing of ▫$G$▫ is the packing number of ▫$G$▫ and is denoted by ▫$\rho(G)$▫. In this article, the incidence dimension is introduced and studied. The given results show a close relationship between ▫$\dim_I(G)$▫ and ▫$\rho(G)$▫. We first note that the complement of any 2-packing in graph ▫$G$▫ is an incidence generator for ▫$G$▫, and further show that either ▫$\dim_I(G)=|V(G)|-\rho(G)$▫ or ▫$\dim_I(G)=|V(G)-|\rho(G)-1$▫ for any graph ▫$G$▫. In addition, we present some bounds for ▫$\dim_I(G)$▫ and prove that the problem of determining the incidence dimension of a graph is NP-hard. Naj bo ▫$G=(V,E)$▫ graf. Množica vozlišč ▫$A$▫ je incidenčni generator grafa ▫$G$▫, če za poljubni različni vozlišči ▫$e,f \in E(G)$▫ obstaja vozlišče iz ▫$A$▫, ki je incidenčno z ali ▫$e$▫ ali ▫$f$▫. Najmanjšemu kardinalnemu številu incidenčnega generatorja grafa ▫$G$▫ račemo incidenčna dimenzija, kar označmo z ▫$\dim_I(G)$▫. Množica vozlišč ▫$P \subseteq V(G)$▫ je 2-pakiranje grafa ▫$G$▫, če je razdalja med poljubnima vozliščema iz ▫$P$▫ vsaj tri. Največja kardinalnost 2-pakiranja grafa ▫$G$▫ je pakirno število grafa ▫$G$▫, ki ga označimo z ▫$\rho(G)$▫. V tem delu vpeljemo incidenčno dimenzijo. Predstavljeni rezultati pokažejo tesno prepletenost med ▫$\dim_I(G)$▫ in ▫$\rho(G)$▫. Najprej opazimo, da je komplement vsakega 2-pakiranja grafa ▫$G$▫ hkrati tudi incidenčni generator grafa ▫$G$▫, Nadalje pokažemo, da velja ali ▫$\dim_I(G)=|V(G)|-\rho(G)$▫ ali ▫$\dim_I(G)=|V(G)-|\rho(G)-1$▫ ua vsak graf ▫$G$▫. Dodatno predstavimo več mej za ▫$\dim_I(G)$▫ in dokažemo, da je določitveni problem incidenčne dimenzije grafa NP-težek. incidence dimension incidence generator 2-packing incidenčna dimenzija incidenčni generator 2-pakiranje true false true Angleški jezik Slovenski jezik Znanstveno delo 2023-08-18 12:55:14 2023-08-18 12:55:14 2023-08-19 03:13:22 0000-00-00 00:00:00 2022 0 0 str. 199-211 št. 1 Letn. 56 Jan.-Feb. 2022 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 2022-01-01 519.17 96612611 10.1051/ro/2022001 0399-0559 https://www.rairo-ro.org/articles/ro/abs/2022/01/ro190152/ro190152.html 1 b7eb325c-3db5-11ee-8efa-00155d000105 https://dk.um.si/Dokument.php?lang=slv&id=169757 Incidence_dimension_and_2-packing-Bozovic-2022.pdf Incidence_dimension_and_2-packing-Bozovic-2022.pdf 1 F5850F22AE513CB83BC52397E8A18D98 fe8ea6f8fa391cfa82b80917d70a87ba08ff739d83c64feee46033af2acfa126 25c18760-3db6-11ee-8efa-00155d000105 https://dk.um.si/Dokument.php?lang=slv&id=169758 Fakulteta za elektrotehniko, računalništvo in informatiko 0 0 0