RT journal article
T1 Incidence dimension and 2-packing number in graphs
A1 Bozovic, Dragana
A1 Kelenc, Aleksander
A1 Peterin, Iztok
A1 González Yero, Ismael
A2 Matemáticas
K1 incidence dimension
K1 incidence generator
K1 2-packing
AB 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 is an element of 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 subset of 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.
PB EDP SCIENCES S A
SN 0399-0559
YR 2022
FD 2022
LK http://hdl.handle.net/10498/26570
UL http://hdl.handle.net/10498/26570
LA eng
NO Dragana Bozovic, Aleksander Kelenc and Iztok Peterin are partially supported by the Slovenian Research Agency by the project No. J1-1693 and J1-9109. Ismael G. Yero has been partially supported by the Spanish Ministry of Science and Innovation through the grant PID2019-105824GB-I00.
DS Repositorio Institucional de la Universidad de Cádiz
RD 13-nov-2026