{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,4]],"date-time":"2022-04-04T01:31:43Z","timestamp":1649035903707},"reference-count":12,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2021,3,13]],"date-time":"2021-03-13T00:00:00Z","timestamp":1615593600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,3,13]],"date-time":"2021-03-13T00:00:00Z","timestamp":1615593600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2021,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A set <jats:italic>S<\/jats:italic> of vertices in a graph <jats:italic>G<\/jats:italic> is a dominating set if every vertex not in <jats:italic>S<\/jats:italic> is ad jacent to a vertex in\u00a0<jats:italic>S<\/jats:italic>. If, in addition, <jats:italic>S<\/jats:italic> is an independent set, then <jats:italic>S<\/jats:italic> is an independent dominating set. The independent domination number <jats:italic>i<\/jats:italic>(<jats:italic>G<\/jats:italic>) of <jats:italic>G<\/jats:italic> is the minimum cardinality of an independent dominating set in <jats:italic>G<\/jats:italic>. The independent domination subdivision number <jats:inline-formula><jats:alternatives><jats:tex-math>$$ \\hbox {sd}_{\\mathrm{i}}(G)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:msub>\n                      <mml:mtext>sd<\/mml:mtext>\n                      <mml:mi>i<\/mml:mi>\n                    <\/mml:msub>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>G<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is the minimum number of edges that must be subdivided (each edge in <jats:italic>G<\/jats:italic> can be subdivided at most once) in order to increase the independent domination number. We show that for every connected graph <jats:italic>G<\/jats:italic> on at least three vertices, the parameter <jats:inline-formula><jats:alternatives><jats:tex-math>$$ \\hbox {sd}_{\\mathrm{i}}(G)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:msub>\n                      <mml:mtext>sd<\/mml:mtext>\n                      <mml:mi>i<\/mml:mi>\n                    <\/mml:msub>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>G<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is well defined and differs significantly from the well-studied domination subdivision number <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathrm{sd_\\gamma }(G)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:msub>\n                      <mml:mi>sd<\/mml:mi>\n                      <mml:mi>\u03b3<\/mml:mi>\n                    <\/mml:msub>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>G<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. For example, if <jats:italic>G<\/jats:italic> is a block graph, then <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathrm{sd_\\gamma }(G) \\le 3$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:msub>\n                      <mml:mi>sd<\/mml:mi>\n                      <mml:mi>\u03b3<\/mml:mi>\n                    <\/mml:msub>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>G<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:mo>\u2264<\/mml:mo>\n                    <mml:mn>3<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, while <jats:inline-formula><jats:alternatives><jats:tex-math>$$ \\hbox {sd}_{\\mathrm{i}}(G)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:msub>\n                      <mml:mtext>sd<\/mml:mtext>\n                      <mml:mi>i<\/mml:mi>\n                    <\/mml:msub>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>G<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> can be arbitrary large. Further we show that there exist connected graph <jats:italic>G<\/jats:italic> with arbitrarily large maximum degree\u00a0<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\Delta (G)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u0394<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>G<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> such that <jats:inline-formula><jats:alternatives><jats:tex-math>$$ \\hbox {sd}_{\\mathrm{i}}(G) \\ge 3 \\Delta (G) - 2$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:msub>\n                      <mml:mtext>sd<\/mml:mtext>\n                      <mml:mi>i<\/mml:mi>\n                    <\/mml:msub>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>G<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:mo>\u2265<\/mml:mo>\n                    <mml:mn>3<\/mml:mn>\n                    <mml:mi>\u0394<\/mml:mi>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>G<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:mo>-<\/mml:mo>\n                    <mml:mn>2<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, in contrast to the known result that <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathrm{sd_\\gamma }(G) \\le 2 \\Delta (G) - 1$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:msub>\n                      <mml:mi>sd<\/mml:mi>\n                      <mml:mi>\u03b3<\/mml:mi>\n                    <\/mml:msub>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>G<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:mo>\u2264<\/mml:mo>\n                    <mml:mn>2<\/mml:mn>\n                    <mml:mi>\u0394<\/mml:mi>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>G<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:mo>-<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> always holds. Among other results, we present a simple characterization of trees <jats:italic>T<\/jats:italic> with <jats:inline-formula><jats:alternatives><jats:tex-math>$$ \\hbox {sd}_{\\mathrm{i}}(T) = 1$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:msub>\n                      <mml:mtext>sd<\/mml:mtext>\n                      <mml:mi>i<\/mml:mi>\n                    <\/mml:msub>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>T<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:mo>=<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>.<\/jats:p>","DOI":"10.1007\/s00373-020-02269-3","type":"journal-article","created":{"date-parts":[[2021,3,13]],"date-time":"2021-03-13T15:02:46Z","timestamp":1615647766000},"page":"691-709","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Independent Domination Subdivision in Graphs"],"prefix":"10.1007","volume":"37","author":[{"given":"Ammar","family":"Babikir","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Magda","family":"Dettlaff","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michael A.","family":"Henning","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Magdalena","family":"Lema\u0144ska","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,3,13]]},"reference":[{"issue":"4","key":"2269_CR1","doi-asserted-by":"publisher","first-page":"622","DOI":"10.1016\/j.disc.2007.12.085","volume":"309","author":"H Aram","year":"2009","unstructured":"Aram, H., Sheikholeslami, S.M., Favaron, O.: Domination subdivision numbers of trees. Discret. Math. 309(4), 622\u2013628 (2009)","journal-title":"Discret. Math."},{"key":"2269_CR2","first-page":"201","volume":"42","author":"S Benecke","year":"2008","unstructured":"Benecke, S., Mynhardt, C.M.: Trees with domination subdivision number one. Aust. J. Combin. 42, 201\u2013209 (2008)","journal-title":"Aust. J. Combin."},{"key":"2269_CR3","volume-title":"Liczba Podzia\u0142owa dla Dominowania w Grafach","author":"M Dettlaff","year":"2015","unstructured":"Dettlaff, M.: Liczba Podzia\u0142owa dla Dominowania w Grafach. Gda\u0144sk University of Technology, Gda\u0144sk (2015)"},{"key":"2269_CR4","first-page":"195","volume":"66","author":"O Favaron","year":"2004","unstructured":"Favaron, O., Haynes, T.W., Hedetniemi, S.T.: Domination subdivision numbers in graphs. Util. Math. 66, 195\u2013209 (2004)","journal-title":"Util. Math."},{"key":"2269_CR5","doi-asserted-by":"publisher","first-page":"309","DOI":"10.1007\/s00373-008-0788-6","volume":"24","author":"O Favaron","year":"2008","unstructured":"Favaron, O., Karami, H., Sheikholeslami, S.M.: Disproof of a conjecture on the subdivision domination number of a graph. Graphs Combin. 24, 309\u2013312 (2008)","journal-title":"Graphs Combin."},{"key":"2269_CR6","doi-asserted-by":"publisher","first-page":"839","DOI":"10.1016\/j.disc.2012.11.031","volume":"313","author":"W Goddard","year":"2013","unstructured":"Goddard, W., Henning, M.A.: Independent domination in graphs: a survey and recent results. Discret. Math. 313, 839\u2013854 (2013)","journal-title":"Discret. Math."},{"issue":"2","key":"2269_CR7","doi-asserted-by":"publisher","first-page":"271","DOI":"10.7151\/dmgt.1126","volume":"20","author":"TW Haynes","year":"2000","unstructured":"Haynes, T.W., Hedetniemi, S.M., Hedetniemi, S.T.: Domination and independence subdivision numbers of graphs. Discuss. Math. Graph Theory 20(2), 271\u2013280 (2000)","journal-title":"Discuss. Math. Graph Theory"},{"issue":"2","key":"2269_CR8","doi-asserted-by":"publisher","first-page":"239","DOI":"10.7151\/dmgt.1147","volume":"21","author":"TW Haynes","year":"2001","unstructured":"Haynes, T.W., Hedetniemi, S.M., Hedetniemi, S.T., Jacobs, D.P., Knisely, J., van der Merwe, L.C.: Domination subdivision numbers. Discuss. Math. Graph Theory 21(2), 239\u2013253 (2001)","journal-title":"Discuss. Math. Graph Theory"},{"key":"2269_CR9","unstructured":"Henning, M.A., Yeo, A.: Total Domination in Graphs (Springer Monographs in Mathematics) 2013. ISBN: 978-1-4614-6524-9 (Print) 978-1-4614-6525-6 (Online)"},{"issue":"6","key":"2269_CR10","first-page":"298","volume":"6","author":"B Sharada","year":"2015","unstructured":"Sharada, B.: Independent domination critical and stable graphs upon edge subdivision. J. Comput. Math. Sci. 6(6), 298\u2013304 (2015)","journal-title":"J. Comput. Math. Sci."},{"issue":"4","key":"2269_CR11","first-page":"289","volume":"80","author":"B Sharada","year":"2010","unstructured":"Sharada, B., Soner, N.D.: A characterization of trees based on independent domination subdivision number. Proc. Natl. Acad. Sci., India, Sect. A 80(4), 289\u2013294 (2010)","journal-title":"Proc. Natl. Acad. Sci., India, Sect. A"},{"key":"2269_CR12","first-page":"233","volume":"46","author":"B Sharada","year":"2010","unstructured":"Sharada, B., Soner, N.D.: On the domination subdivision numbers of trees. Aus. J. Combin. 46, 233\u2013239 (2010)","journal-title":"Aus. J. Combin."}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-020-02269-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00373-020-02269-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-020-02269-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,4,26]],"date-time":"2021-04-26T14:44:29Z","timestamp":1619448269000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00373-020-02269-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3,13]]},"references-count":12,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,5]]}},"alternative-id":["2269"],"URL":"https:\/\/doi.org\/10.1007\/s00373-020-02269-3","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"value":"0911-0119","type":"print"},{"value":"1435-5914","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,3,13]]},"assertion":[{"value":"11 April 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 December 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 December 2020","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 March 2021","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}