Incidence dimension and 2-packing number in graphs

¹ Faculty of Electrical Engineering and Computer Science, University of Maribor, Koroška cesta 46, 2000 Maribor, Slovenia
² Institute of Mathematics, Physics and Mechanics, Jadranska ulica 19, 1000 Ljubljana, Slovenia
³ Departamento de Matemáticas, Escuela Técnica Superior de Ingeniería de Algeciras, Universidad de Cádiz, Av. Ramón Puyol s/n, 11202 Algeciras, Spain

^* Corresponding author: iztok.peterin@um.si

Received: 15 May 2019
Accepted: 3 January 2020

Abstract

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 ∈ 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 ⊆ 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 ρ(G). In this article, the incidence dimension is introduced and studied. The given results show a close relationship between dim_I(G) and ρ(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)-|ρ(G) or dim_I(G) = |V(G)-|ρ(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.