Incidence dimension and 2-packing number in graphs

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\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 $di{m}_I(G)$. A set of vertices $P$ is a 2-packing if the distance between any pair of distinct vertices from $P$ is greater than two. The largest cardinality of a 2-packing of $G$ is the packing number of $G$ and is denoted by $\rho (G)$. The incidence dimension of graphs is introduced and studied in this article, and we emphasize in the closed relationship between $di{m}_I(G)$ and $\rho (G)$. We first note that the complement of any 2-packing in a graph $G$ is always an incidence generator for $G$, and further show that either $di{m}_I(G)=\rho (G)$ or $di{m}_I(G)=\rho (G)-1$ for any graph $G$. In addition, we also prove that the problem of determining the incidence dimension of a graph is NP-complete, and present some bounds for it.

16 pages