Incidence dimension and 2-packing number in graphs

Publication date 21 February 2022

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 i n 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

d i 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

h o (G)

. The incidence dimension of graphs is introduced and studied in this article, and we emphasize in the closed relationship between

d i m_{I} (G)

and

h o (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

d i m_{I} (G) = h o (G)

or

d i m_{I} (G) = h o (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.

Recommendations

Cited in

(5)

This page was built for publication: Incidence dimension and 2-packing number in graphs