{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,20]],"date-time":"2026-02-20T19:10:54Z","timestamp":1771614654765,"version":"3.50.1"},"reference-count":30,"publisher":"EDP Sciences","issue":"1","license":[{"start":{"date-parts":[[2022,2,7]],"date-time":"2022-02-07T00:00:00Z","timestamp":1644192000000},"content-version":"vor","delay-in-days":37,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2020,1,3]]},"published-print":{"date-parts":[[2022,1]]},"abstract":"<jats:p>Let <jats:italic>G<\/jats:italic> = (<jats:italic>V<\/jats:italic>, <jats:italic>E<\/jats:italic>) be a graph. A set of vertices <jats:italic>A<\/jats:italic> is an incidence generator for <jats:italic>G<\/jats:italic> if for any two distinct edges <jats:italic>e<\/jats:italic>, <jats:italic>f<\/jats:italic> \u2208 <jats:italic>E<\/jats:italic>(<jats:italic>G<\/jats:italic>) there exists a vertex from <jats:italic>A<\/jats:italic> which is an endpoint of either <jats:italic>e<\/jats:italic> or <jats:italic>f<\/jats:italic>. The smallest cardinality of an incidence generator for <jats:italic>G<\/jats:italic> is called the incidence dimension and is denoted by dim<jats:sub><jats:italic>I<\/jats:italic><\/jats:sub>(<jats:italic>G<\/jats:italic>). A set of vertices <jats:italic>P<\/jats:italic> \u2286 <jats:italic>V<\/jats:italic>(<jats:italic>G<\/jats:italic>) is a 2-packing of <jats:italic>G<\/jats:italic> if the distance in <jats:italic>G<\/jats:italic> between any pair of distinct vertices from <jats:italic>P<\/jats:italic> is larger than two. The largest cardinality of a 2-packing of <jats:italic>G<\/jats:italic> is the packing number of <jats:italic>G<\/jats:italic> and is denoted by <jats:italic>\u03c1<\/jats:italic>(<jats:italic>G<\/jats:italic>). In this article, the incidence dimension is introduced and studied. The given results show a close relationship between dim<jats:sub><jats:italic>I<\/jats:italic><\/jats:sub>(<jats:italic>G<\/jats:italic>) and <jats:italic>\u03c1<\/jats:italic>(<jats:italic>G<\/jats:italic>). We first note that the complement of any 2-packing in graph <jats:italic>G<\/jats:italic> is an incidence generator for <jats:italic>G<\/jats:italic>, and further show that either dim<jats:sub><jats:italic>I<\/jats:italic><\/jats:sub>(<jats:italic>G<\/jats:italic>) = |<jats:italic>V<\/jats:italic>(<jats:italic>G<\/jats:italic>)-|\u03c1(<jats:italic>G<\/jats:italic>) or dim<jats:sub><jats:italic>I<\/jats:italic><\/jats:sub>(<jats:italic>G<\/jats:italic>) = |<jats:italic>V<\/jats:italic>(<jats:italic>G<\/jats:italic>)-|\u03c1(<jats:italic>G<\/jats:italic>) - 1 for any graph <jats:italic>G<\/jats:italic>. In addition, we present some bounds for dim<jats:sub><jats:italic>I<\/jats:italic><\/jats:sub>(<jats:italic>G<\/jats:italic>) and prove that the problem of determining the incidence dimension of a graph is NP-hard.<\/jats:p>","DOI":"10.1051\/ro\/2022001","type":"journal-article","created":{"date-parts":[[2022,1,4]],"date-time":"2022-01-04T19:48:01Z","timestamp":1641325681000},"page":"199-211","source":"Crossref","is-referenced-by-count":5,"title":["Incidence dimension and 2-packing number in graphs"],"prefix":"10.1051","volume":"56","author":[{"given":"Dragana","family":"Bo\u017eovi\u0107","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aleksander","family":"Kelenc","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Iztok","family":"Peterin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ismael G.","family":"Yero","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2022,2,7]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1016\/0095-8956(73)90042-7","volume":"15","author":"Biggs","year":"1973","journal-title":"J. Combin. Theory Ser. B"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"Bo\u017eovi\u0107 D. and Peterin I., Graphs with unique maximum packing of closed neighborhoods. Discuss. Math. Graph Theory, in press. (2021). DOI: 10.7151\/dmgt.2304.","DOI":"10.7151\/dmgt.2304"},{"key":"R3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.tcs.2014.11.014","volume":"579","author":"Dobson","year":"2015","journal-title":"Theor. Comput. Sci."},{"key":"R4","first-page":"489","volume":"101","author":"Dutton","year":"2011","journal-title":"Ars Combin."},{"key":"R5","doi-asserted-by":"crossref","first-page":"102","DOI":"10.2298\/AADM151109022E","volume":"10","author":"Estrada-Moreno","year":"2016","journal-title":"Appl. Anal. Discrete Math."},{"key":"R6","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1016\/j.dam.2017.11.019","volume":"236","author":"Fernau","year":"2018","journal-title":"Discrete Appl. Math."},{"key":"R7","doi-asserted-by":"crossref","first-page":"146","DOI":"10.1016\/j.dam.2014.11.017","volume":"184","author":"Gagarin","year":"2015","journal-title":"Discrete Appl. Math."},{"key":"R8","doi-asserted-by":"crossref","first-page":"1357","DOI":"10.1016\/j.dam.2009.04.014","volume":"158","author":"Gallant","year":"2010","journal-title":"Discrete Appl. Math."},{"key":"R9","unstructured":"Garey M.R. and Johnson D.S., Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York, USA (1979)."},{"key":"R10","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.dam.2020.03.001","volume":"284","author":"Geneson","year":"2020","journal-title":"Discrete Appl. Math."},{"key":"R11","first-page":"191","volume":"2","author":"Harary","year":"1976","journal-title":"Ars Combin."},{"key":"R12","doi-asserted-by":"crossref","unstructured":"Haynes T.W., Hedetniemi S.T. and Slater P.J., Domination in Graphs. Marcel Dekker Inc, New York, NY (1998).","DOI":"10.1002\/(SICI)1097-0037(199810)32:3<199::AID-NET4>3.0.CO;2-F"},{"key":"R13","unstructured":"Haynes T.W., Hedetniemi S.T. and Slater P.J., Domination in Graphs: Advanced Topics. Marcel Dekker Inc, New York, NY (1998)."},{"key":"R14","doi-asserted-by":"crossref","first-page":"2031","DOI":"10.1016\/j.disc.2011.04.030","volume":"311","author":"Henning","year":"2011","journal-title":"Discrete Math."},{"key":"R15","doi-asserted-by":"crossref","first-page":"3349","DOI":"10.1016\/j.disc.2012.07.025","volume":"312","author":"Jannesari","year":"2012","journal-title":"Discrete Math."},{"key":"R16","doi-asserted-by":"crossref","first-page":"3444","DOI":"10.1016\/j.disc.2012.02.005","volume":"312","author":"Junosza-Szaniawski","year":"2012","journal-title":"Discrete Math."},{"key":"R17","first-page":"429","volume":"314","author":"Kelenc","year":"2017","journal-title":"Appl. Math. Comput."},{"key":"R18","doi-asserted-by":"crossref","first-page":"204","DOI":"10.1016\/j.dam.2018.05.052","volume":"251","author":"Kelenc","year":"2018","journal-title":"Discrete Appl. Math."},{"key":"R19","doi-asserted-by":"crossref","first-page":"613","DOI":"10.1016\/j.dam.2016.09.027","volume":"217","author":"Klav\u017ear","year":"2017","journal-title":"Discrete Appl. Math."},{"key":"R20","first-page":"126076","volume":"401","author":"Knor","year":"2021","journal-title":"Appl. Math. Comput."},{"key":"R21","doi-asserted-by":"crossref","unstructured":"Knor M., \u0160krekovski R. and Yero I.G., A note on the metric and edge metric dimensions of 2-connected graphs. Discrete Appl. Math., in press. DOI: 10.1016\/j.dam.2021.02.020 (2021).","DOI":"10.1016\/j.dam.2021.02.020"},{"key":"R22","doi-asserted-by":"crossref","first-page":"182","DOI":"10.1007\/s00025-019-1105-9","volume":"74","author":"Kratica","year":"2019","journal-title":"Results Math."},{"key":"R23","unstructured":"Kuziak D. and Yero I.G., Metric dimension related parameters in graphs: A survey on combinatorial, computational and applied results. Preprint arXiv:2107.04877 (2021)."},{"key":"R24","doi-asserted-by":"crossref","first-page":"225","DOI":"10.2140\/pjm.1975.61.225","volume":"61","author":"Meir","year":"1975","journal-title":"Pacific J. Math."},{"key":"R25","first-page":"468","volume":"71","author":"Mojdeh","year":"2018","journal-title":"Australas. J. Combin."},{"key":"R26","doi-asserted-by":"crossref","first-page":"2465","DOI":"10.1007\/s40840-019-00816-7","volume":"43","author":"Peterin","year":"2020","journal-title":"Bull. Malays. Math. Sci. Soc."},{"key":"R27","doi-asserted-by":"crossref","first-page":"5","DOI":"10.7151\/dmgt.1775","volume":"35","author":"Sahul Hamid","year":"2015","journal-title":"Discuss. Math. Graph Theory"},{"key":"R28","first-page":"549","volume":"14","author":"Slater","year":"1975","journal-title":"Congressus Numerantium"},{"key":"R29","unstructured":"Tillquist R.C., Frongillo R.M. and Lladser M.E., Getting the lay of the land in discrete space: A survey of metric dimension and its applications. Preprint arXiv:2104.07201 (2021)."},{"key":"R30","doi-asserted-by":"crossref","first-page":"2083","DOI":"10.1016\/j.disc.2018.04.010","volume":"341","author":"Zubrilina","year":"2018","journal-title":"Discrete Math."}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2022001\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,7]],"date-time":"2022-02-07T09:17:24Z","timestamp":1644225444000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2022001"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1]]},"references-count":30,"journal-issue":{"issue":"1"},"alternative-id":["ro190152"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2022001","relation":{},"ISSN":["0399-0559","2804-7303"],"issn-type":[{"value":"0399-0559","type":"print"},{"value":"2804-7303","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1]]}}}