| Naslov: | Incidence dimension and 2-packing number in graphs |
|---|
| Avtorji: | ID Božović, Dragana (Avtor)
ID Kelenc, Aleksander (Avtor)
ID Peterin, Iztok (Avtor)
ID Yero, Ismael G. (Avtor) |
|---|
| Datoteke: |  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
|
|---|
| Jezik: | Angleški jezik |
|---|
| Vrsta gradiva: | Znanstveno delo |
|---|
| Tipologija: | 1.01 - Izvirni znanstveni članek |
|---|
| Organizacija: | FERI - Fakulteta za elektrotehniko, računalništvo in informatiko
|
|---|
| Opis: | 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. |
|---|
| Ključne besede: | incidence dimension, incidence generator, 2-packing |
|---|
| Status publikacije: | Objavljeno |
|---|
| Verzija publikacije: | Objavljena publikacija |
|---|
| Datum objave: | 01.01.2022 |
|---|
| Leto izida: | 2022 |
|---|
| Št. strani: | str. 199-211 |
|---|
| Številčenje: | Letn. 56, št. 1 |
|---|
| PID: | 20.500.12556/DKUM-85102  |
|---|
| UDK: | 519.17 |
|---|
| COBISS.SI-ID: | 96612611 |
|---|
| DOI: | 10.1051/ro/2022001 |
|---|
| ISSN pri članku: | 0399-0559 |
|---|
| Datum objave v DKUM: | 18.08.2023 |
|---|
| Število ogledov: | 454 |
|---|
| Število prenosov: | 61 |
|---|
| Metapodatki: |    |
|---|
| Področja: | Ostalo
|
|---|
|
:
|
Kopiraj citat |
|---|
| | | | Skupna ocena: | (0 glasov) |
|---|
| Vaša ocena: | Ocenjevanje je dovoljeno samo prijavljenim uporabnikom. |
|---|
| Objavi na: |  |
|---|
Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše
podrobnosti ali sproži prenos. |
