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$$(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$$(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$$(G) = |V(G)-|ρ(G) or dim$$(G) = |V(G)-|ρ(G) - 1 for any graph G. In addition, we present some bounds for dim$$(G) and prove that the problem of determining the incidence dimension of a graph is NP-hard.
Keywords: incidence dimension, incidence generator, 2-packing
@article{RO_2022__56_1_199_0,
author = {Bo\v{z}ovi\'c, Dragana and Kelenc, Aleksander and Peterin, Iztok and Yero, Ismael G.},
title = {Incidence dimension and 2-packing number in graphs},
journal = {RAIRO. Operations Research},
pages = {199--211},
year = {2022},
publisher = {EDP-Sciences},
volume = {56},
number = {1},
doi = {10.1051/ro/2022001},
mrnumber = {4376277},
zbl = {1483.05113},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ro/2022001/}
}
TY - JOUR AU - Božović, Dragana AU - Kelenc, Aleksander AU - Peterin, Iztok AU - Yero, Ismael G. TI - Incidence dimension and 2-packing number in graphs JO - RAIRO. Operations Research PY - 2022 SP - 199 EP - 211 VL - 56 IS - 1 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ro/2022001/ DO - 10.1051/ro/2022001 LA - en ID - RO_2022__56_1_199_0 ER -
%0 Journal Article %A Božović, Dragana %A Kelenc, Aleksander %A Peterin, Iztok %A Yero, Ismael G. %T Incidence dimension and 2-packing number in graphs %J RAIRO. Operations Research %D 2022 %P 199-211 %V 56 %N 1 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ro/2022001/ %R 10.1051/ro/2022001 %G en %F RO_2022__56_1_199_0
Božović, Dragana; Kelenc, Aleksander; Peterin, Iztok; Yero, Ismael G. Incidence dimension and 2-packing number in graphs. RAIRO. Operations Research, Tome 56 (2022) no. 1, pp. 199-211. doi: 10.1051/ro/2022001
[1] , Perfect codes in graphs. J. Combin. Theory Ser. B 15 (1973) 289–296. | MR | Zbl | DOI
[2] and , Graphs with unique maximum packing of closed neighborhoods. Discuss. Math. Graph Theory, in press. (2021). DOI: . | DOI | Zbl | MR
[3] , and , Generalized limited packings of some graphs with a limited number of partners. Theor. Comput. Sci. 579 (2015) 1–8. | MR | Zbl | DOI
[4] , Global domination and packing numbers. Ars Combin. 101 (2011) 489–501. | MR | Zbl
[5] , and , On the adjacency dimension of graphs. Appl. Anal. Discrete Math. 10 (2016) 102–127. | MR | Zbl | DOI
[6] and , On the (adjacency) metric dimension of corona and strong product graphs and their local variants: combinatorial and computational results. Discrete Appl. Math. 236 (2018) 183–202. | MR | Zbl | DOI
[7] and , The probabilistic approach to limited packings in graphs. Discrete Appl. Math. 184 (2015) 146–153. | MR | Zbl | DOI
[8] , , and , Limited packings in graphs. Discrete Appl. Math. 158 (2010) 1357–1364. | MR | Zbl | DOI
[9] and , Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, USA (1979). | Zbl
[10] , Metric dimension and pattern avoidance in graphs. Discrete Appl. Math. 284 (2020) 1–7. | MR | Zbl | DOI
[11] and , On the metric dimension of a graph. Ars Combin. 2 (1976) 191–195. | MR | Zbl
[12] , and , Domination in Graphs. Marcel Dekker Inc, New York, NY (1998). | Zbl | MR
[13] , and , Domination in Graphs: Advanced Topics. Marcel Dekker Inc, New York, NY (1998). | MR | Zbl
[14] , and , Dominating sets, packings, and the maximum degree. Discrete Math. 311 (2011) 2031–2036. | MR | Zbl | DOI
[15] and , The metric dimension of the lexicographic product of graphs. Discrete Math. 312 (2012) 3349–3356. | MR | Zbl | DOI
[16] and , On the number of 2-packings in a connected graph. Discrete Math. 312 (2012) 3444–3450. | MR | Zbl | DOI
[17] , , and , On the mixed metric dimension of graphs. Appl. Math. Comput. 314 (2017) 429–438. | MR | Zbl
[18] , and , Uniquely identifying the edges of a graph: the edge metric dimension. Discrete Appl. Math. 251 (2018) 204–220. | MR | Zbl | DOI
[19] , and , Graphs that are simultaneously efficient open domination and efficient closed domination graphs. Discrete Appl. Math. 217 (2017) 613–621. | MR | Zbl | DOI
[20] , , , and , Graphs with the edge metric dimension smaller than the metric dimension. Appl. Math. Comput. 401 (2021) 126076. | MR | Zbl
[21] , and , A note on the metric and edge metric dimensions of 2-connected graphs. Discrete Appl. Math., in press. DOI: (2021). | DOI | MR | Zbl
[22] , and , Edge metric dimension of some generalized Petersen graphs. Results Math. 74 (2019) 182. | MR | Zbl | DOI
[23] and , Metric dimension related parameters in graphs: A survey on combinatorial, computational and applied results. Preprint (2021). | arXiv
[24] and , Relations between packing and covering numbers of a tree. Pacific J. Math. 61 (1975) 225–233. | MR | Zbl | DOI
[25] , , and , On the packing numbers in graphs. Australas. J. Combin. 71 (2018) 468–475. | MR | Zbl
[26] and , Edge metric dimension of some graph operations. Bull. Malays. Math. Sci. Soc. 43 (2020) 2465–2477. | MR | Zbl | DOI
[27] and , Packing parameters in graphs. Discuss. Math. Graph Theory 35 (2015) 5–6. | MR | Zbl | DOI
[28] , Leaves of trees. Congressus Numerantium 14 (1975) 549–559. | MR | Zbl
[29] , and , Getting the lay of the land in discrete space: A survey of metric dimension and its applications. Preprint (2021). | arXiv | MR | Zbl
[30] , On the edge dimension of a graph. Discrete Math. 341 (2018) 2083–2088. | MR | Zbl | DOI
Cité par Sources :
