| Title: | Incidence dimension and 2-packing number in graphs |
|---|
| Authors: | ID Božović, Dragana (Author)
ID Kelenc, Aleksander (Author)
ID Peterin, Iztok (Author)
ID Yero, Ismael G. (Author) |
|---|
| Files: |  https://www.rairo-ro.org/articles/ro/abs/2022/01/ro190152/ro190152.html
 Incidence_dimension_and_2-packing-Bozovic-2022.pdf (434,03 KB)
MD5: F5850F22AE513CB83BC52397E8A18D98
|
|---|
| Language: | English |
|---|
| Work type: | Scientific work |
|---|
| Typology: | 1.01 - Original Scientific Article |
|---|
| Organization: | FERI - Faculty of Electrical Engineering and Computer Science
|
|---|
| 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 ▫$\dim_I(G)$▫. A set of vertices ▫$P \subseteq 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. |
|---|
| Keywords: | incidence dimension, incidence generator, 2-packing |
|---|
| Publication status: | Published |
|---|
| Publication version: | Version of Record |
|---|
| Publication date: | 01.01.2022 |
|---|
| Year of publishing: | 2022 |
|---|
| Number of pages: | str. 199-211 |
|---|
| Numbering: | Letn. 56, št. 1 |
|---|
| PID: | 20.500.12556/DKUM-85102  |
|---|
| UDC: | 519.17 |
|---|
| ISSN on article: | 0399-0559 |
|---|
| COBISS.SI-ID: | 96612611 |
|---|
| DOI: | 10.1051/ro/2022001 |
|---|
| Publication date in DKUM: | 18.08.2023 |
|---|
| Views: | 450 |
|---|
| Downloads: | 61 |
|---|
| Metadata: |    |
|---|
| Categories: | Misc.
|
|---|
|
:
|
Copy citation |
|---|
| | | | Average score: | (0 votes) |
|---|
| Your score: | Voting is allowed only for logged in users. |
|---|
| Share: |  |
|---|
Hover the mouse pointer over a document title to show the abstract or click
on the title to get all document metadata. |
