{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:47:42Z","timestamp":1759063662032},"reference-count":24,"publisher":"World Scientific Pub Co Pte Ltd","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2015,12]]},"abstract":"<jats:p>The concept of the [Formula: see text]-rainbow index of a network comes from the communication of information between agencies of government, which was introduced by Chartrand et al. in 2010. As a natural counterpart of the [Formula: see text]-rainbow index, the concept of [Formula: see text]-vertex-rainbow index was also introduced. For a graph [Formula: see text] and a set [Formula: see text] of at least two vertices, an [Formula: see text]-Steiner tree or a Steiner tree connecting [Formula: see text] (or simply, an [Formula: see text]-tree) is such a subgraph [Formula: see text] of [Formula: see text] that is a tree with [Formula: see text]. For [Formula: see text] and [Formula: see text], an [Formula: see text]-Steiner tree [Formula: see text] is said to be a vertex-rainbow [Formula: see text]-tree if the vertices of [Formula: see text] have distinct colors. For a fixed integer [Formula: see text] with [Formula: see text], the vertex-coloring [Formula: see text] of [Formula: see text] is called a [Formula: see text]-vertex-rainbow coloring if for every [Formula: see text]-subset [Formula: see text] of [Formula: see text] there exists a vertex-rainbow [Formula: see text]-tree. In this case, [Formula: see text] is called vertex-rainbow [Formula: see text]-tree-connected. The minimum number of colors that are needed in a [Formula: see text]-vertex-rainbow coloring of [Formula: see text] is called the [Formula: see text]-vertex-rainbow index of [Formula: see text], denoted by [Formula: see text]. In this paper, we study the complexity of determining the [Formula: see text]-vertex-rainbow index of a graph and prove that computing [Formula: see text] is [Formula: see text]-Hard. Moreover, we show that it is [Formula: see text]-Complete to decide whether [Formula: see text]. We also prove that the following problem is [Formula: see text]-Complete: Given a vertex-colored graph [Formula: see text], check whether the given coloring makes [Formula: see text] vertex-rainbow [Formula: see text]-tree-connected.<\/jats:p>","DOI":"10.1142\/s1793830915500470","type":"journal-article","created":{"date-parts":[[2015,9,15]],"date-time":"2015-09-15T05:49:14Z","timestamp":1442296154000},"page":"1550047","source":"Crossref","is-referenced-by-count":2,"title":["The complexity of determining the vertex-rainbow index of graphs"],"prefix":"10.1142","volume":"07","author":[{"given":"Yaping","family":"Mao","sequence":"first","affiliation":[{"name":"Department of Mathematics, Qinghai Normal University, Xining, Qinghai 810008, P. R. China"},{"name":"Center for Combinatorics and LPMC-TJKLC, Nankai University, Tianjin 300071, P. R. China"}]},{"given":"Yongtang","family":"Shi","sequence":"additional","affiliation":[{"name":"Department of Mathematics, Qinghai Normal University, Xining, Qinghai 810008, P. R. China"},{"name":"Center for Combinatorics and LPMC-TJKLC, Nankai University, Tianjin 300071, P. R. China"}]}],"member":"219","published-online":{"date-parts":[[2016,1,4]]},"reference":[{"key":"S1793830915500470BIB001","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-84628-970-5"},{"key":"S1793830915500470BIB002","doi-asserted-by":"crossref","first-page":"220","DOI":"10.1002\/net.21513","volume":"62","author":"Cai Q.","year":"2013","journal-title":"Networks"},{"key":"S1793830915500470BIB003","doi-asserted-by":"crossref","first-page":"R57","DOI":"10.37236\/781","volume":"15","author":"Caro Y.","year":"2008","journal-title":"Electron. J. Combin."},{"key":"S1793830915500470BIB005","doi-asserted-by":"crossref","first-page":"85","DOI":"10.21136\/MB.2008.133947","volume":"133","author":"Chartrand G.","year":"2008","journal-title":"Math. Bohem."},{"key":"S1793830915500470BIB006","first-page":"360","volume":"55","author":"Chartrand G.","year":"2010","journal-title":"Networks"},{"key":"S1793830915500470BIB007","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2013.02.012"},{"key":"S1793830915500470BIB008","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2011.04.032"},{"key":"S1793830915500470BIB009","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-0255-1","volume-title":"Steiner Trees in Industry","author":"Cheng X.","year":"2001"},{"key":"S1793830915500470BIB010","doi-asserted-by":"publisher","DOI":"10.1142\/9789812791450"},{"key":"S1793830915500470BIB011","first-page":"24","volume-title":"Graduating Engineer & Computer Careers","author":"Ericksen A.","year":"2007"},{"key":"S1793830915500470BIB012","doi-asserted-by":"publisher","DOI":"10.1007\/s40840-014-0077-x"},{"issue":"3","key":"S1793830915500470BIB013","first-page":"51","volume":"16","author":"Huang X.","year":"2014","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"S1793830915500470BIB014","doi-asserted-by":"publisher","DOI":"10.1016\/j.amc.2014.05.066"},{"issue":"3","key":"S1793830915500470BIB015","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1002\/jgt.20418","volume":"63","author":"Krivelevich M.","year":"2009","journal-title":"J. Graph Theory"},{"key":"S1793830915500470BIB016","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-013-1309-9"},{"key":"S1793830915500470BIB017","doi-asserted-by":"publisher","DOI":"10.1016\/j.amc.2015.02.015"},{"key":"S1793830915500470BIB018","first-page":"213","volume":"93","author":"Li X.","year":"2014","journal-title":"Utilitas Math."},{"key":"S1793830915500470BIB019","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-012-1204-9"},{"key":"S1793830915500470BIB020","doi-asserted-by":"publisher","DOI":"10.7151\/dmgt.1664"},{"key":"S1793830915500470BIB021","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-012-1243-2"},{"key":"S1793830915500470BIB022","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4614-3119-0"},{"issue":"3","key":"S1793830915500470BIB023","first-page":"306","volume":"60","author":"Li X.","year":"2014","journal-title":"Australas. J. Comb."},{"key":"S1793830915500470BIB025","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2015.05.012"},{"key":"S1793830915500470BIB026","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-08377-3_12"}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830915500470","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,11]],"date-time":"2024-06-11T03:57:53Z","timestamp":1718078273000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830915500470"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,12]]},"references-count":24,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2016,1,4]]},"published-print":{"date-parts":[[2015,12]]}},"alternative-id":["10.1142\/S1793830915500470"],"URL":"https:\/\/doi.org\/10.1142\/s1793830915500470","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,12]]}}}