Mostrar el registro sencillo del ítem

dc.contributor.authorBozovic, Dragana
dc.contributor.authorKelenc, Aleksander
dc.contributor.authorPeterin, Iztok
dc.contributor.authorGonzález Yero, Ismael 
dc.contributor.otherMatemáticases_ES
dc.date.accessioned2022-04-21T07:24:14Z
dc.date.available2022-04-21T07:24:14Z
dc.date.issued2022
dc.identifier.issn0399-0559
dc.identifier.issn2804-7303
dc.identifier.urihttp://hdl.handle.net/10498/26570
dc.description.abstractLet 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 is an element of 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 subset of 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.es_ES
dc.description.sponsorshipDragana Bozovic, Aleksander Kelenc and Iztok Peterin are partially supported by the Slovenian Research Agency by the project No. J1-1693 and J1-9109. Ismael G. Yero has been partially supported by the Spanish Ministry of Science and Innovation through the grant PID2019-105824GB-I00.es_ES
dc.formatapplication/pdfes_ES
dc.language.isoenges_ES
dc.publisherEDP SCIENCES S Aes_ES
dc.rightsAtribución 4.0 Internacional*
dc.rights.urihttp://creativecommons.org/licenses/by/4.0/*
dc.sourceRAIRO - Operations Research, Vol. 56, Núm. 1, pp. 199-211es_ES
dc.subjectincidence dimensiones_ES
dc.subjectincidence generatores_ES
dc.subject2-packinges_ES
dc.titleIncidence dimension and 2-packing number in graphses_ES
dc.typejournal articlees_ES
dc.rights.accessRightsopen accesses_ES
dc.identifier.doi10.1051/ro/2022001
dc.relation.projectIDinfo:eu-repo/grantAgreement/AEI/Plan Estatal de Investigación Científica y Técnica y de Innovación 2017-2020/PID2019-105824GB-I00/ES/OPTIMIZACION MATEMATICA Y COMBINATORIA EN REDES/es_ES


Ficheros en el ítem

Este ítem aparece en la(s) siguiente(s) colección(ones)

Mostrar el registro sencillo del ítem

Atribución 4.0 Internacional
Esta obra está bajo una Licencia Creative Commons Atribución 4.0 Internacional