| | SLO | ENG | Piškotki in zasebnost

Večja pisava | Manjša pisava
Prva stran > Izpis gradiva

Izpis gradiva Pomoč

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:URL https://www.rairo-ro.org/articles/ro/abs/2022/01/ro190152/ro190152.html
 
.pdf 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∈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 dimI(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 dimI(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 dimI(G)=|V(G)|−ρ(G) or dimI(G)=|V(G)−|ρ(G)−1 for any graph G. In addition, we present some bounds for dimI(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 Novo okno
UDK:519.17
COBISS.SI-ID:96612611 Novo okno
DOI:10.1051/ro/2022001 Novo okno
ISSN pri članku:0399-0559
Datum objave v DKUM:18.08.2023
Število ogledov:317
Število prenosov:41
Metapodatki:XML DC-XML DC-RDF
Področja:Ostalo
:
BOŽOVIĆ, Dragana, KELENC, Aleksander, PETERIN, Iztok in YERO, Ismael G., 2022, Incidence dimension and 2-packing number in graphs. RAIRO-Operations Research [na spletu]. 2022. Vol. 56, no. 1, p. 199–211. [Dostopano 18 april 2025]. DOI 10.1051/ro/2022001. Pridobljeno s: https://dk.um.si/IzpisGradiva.php?lang=slv&id=85102
Kopiraj citat
  
Skupna ocena:
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
(0 glasov)
Vaša ocena:Ocenjevanje je dovoljeno samo prijavljenim uporabnikom.
Objavi na:Bookmark and Share


Postavite miškin kazalec na naslov za izpis povzetka. Klik na naslov izpiše podrobnosti ali sproži prenos.

Gradivo je del revije

Naslov:RAIRO-Operations Research
Skrajšan naslov:RAIRO Oper. Res.
Založnik:EDP Sciences
ISSN:0399-0559
COBISS.SI-ID:26238976 Novo okno

Gradivo je financirano iz projekta

Financer:ARRS - Agencija za raziskovalno dejavnost Republike Slovenije
Številka projekta:J1-1693
Naslov:Sodobni in novi metrični koncepti v teoriji grafov
Financer:ARRS - Agencija za raziskovalno dejavnost Republike Slovenije
Številka projekta:J1-9109
Naslov:Sodobne invariante grafov
Financer:Drugi - Drug financer ali več financerjev
Številka projekta:PID2019-105824GB-I00

Licence

Licenca:CC BY 4.0, Creative Commons Priznanje avtorstva 4.0 Mednarodna
Povezava:http://creativecommons.org/licenses/by/4.0/deed.sl
Opis:To je standardna licenca Creative Commons, ki daje uporabnikom največ možnosti za nadaljnjo uporabo dela, pri čemer morajo navesti avtorja.

Sekundarni jezik

Jezik:Slovenski jezik
Naslov:Incidenčna dimenzija in 2-pakirno število grafov
Opis:Naj bo G=(V,E) graf. Množica vozlišč A je incidenčni generator grafa G, če za poljubni različni vozlišči e,f∈E(G) obstaja vozlišče iz A, ki je incidenčno z ali e ali f. Najmanjšemu kardinalnemu številu incidenčnega generatorja grafa G račemo incidenčna dimenzija, kar označmo z dimI(G). Množica vozlišč P⊆V(G) je 2-pakiranje grafa G, če je razdalja med poljubnima vozliščema iz P vsaj tri. Največja kardinalnost 2-pakiranja grafa G je pakirno število grafa G, ki ga označimo z ρ(G). V tem delu vpeljemo incidenčno dimenzijo. Predstavljeni rezultati pokažejo tesno prepletenost med dimI(G) in ρ(G). Najprej opazimo, da je komplement vsakega 2-pakiranja grafa G hkrati tudi incidenčni generator grafa G, Nadalje pokažemo, da velja ali dimI(G)=|V(G)|−ρ(G) ali dimI(G)=|V(G)−|ρ(G)−1 ua vsak graf G. Dodatno predstavimo več mej za dimI(G) in dokažemo, da je določitveni problem incidenčne dimenzije grafa NP-težek.
Ključne besede:incidenčna dimenzija, incidenčni generator, 2-pakiranje


Komentarji

Dodaj komentar

Za komentiranje se morate prijaviti.

Komentarji (0)
0 - 0 / 0
 
Ni komentarjev!

Nazaj
Logotipi partnerjev Univerza v Mariboru Univerza v Ljubljani Univerza na Primorskem Univerza v Novi Gorici