Incidence dimension and 2-packing number in graphs

Dragana Božović (Avtor), Aleksander Kelenc (Avtor), Iztok Peterin (Avtor), Ismael G. Yero (Avtor)

Povzetek

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.

Ključne besede

incidenčna dimenzija;incidenčni generator;2-pakiranje;incidence dimension;incidence generator;2-packing;

Podatki

Jezik:	Angleški jezik
Leto izida:	2022
Tipologija:	1.01 - Izvirni znanstveni članek
Organizacija:	UM FERI - Fakulteta za elektrotehniko, računalništvo in informatiko
UDK:	519.17
COBISS:	96612611
ISSN:	0399-0559
Št. ogledov:	8
Št. prenosov:	1
Ocena:	0 (0 glasov)
Metapodatki:

Ostali podatki

Sekundarni jezik:	Slovenski jezik
Sekundarni naslov:	Incidenčna dimenzija in 2-pakirno število grafov
Sekundarni povzetek:	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.
Sekundarne ključne besede:	incidenčna dimenzija;incidenčni generator;2-pakiranje;
Vrsta dela (COBISS):	Znanstveno delo
Strani:	str. 199-211
Letnik:	ǂVol. ǂ56
Zvezek:	ǂno. ǂ1
Čas izdaje:	Jan.-Feb. 2022
DOI:	10.1051/ro/2022001
ID:	19818210