{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,16]],"date-time":"2026-01-16T08:52:23Z","timestamp":1768553543029,"version":"3.49.0"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2019,10,25]],"date-time":"2019-10-25T00:00:00Z","timestamp":1571961600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2019,10,25]],"date-time":"2019-10-25T00:00:00Z","timestamp":1571961600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["2015\/17\/B\/ST6\/01887"],"award-info":[{"award-number":["2015\/17\/B\/ST6\/01887"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2020,1]]},"abstract":"Abstract<\/jats:title>\nA dominating set of a graph G<\/jats:italic> is a set $$D\\subseteq V_G$$<\/jats:tex-math>D<\/mml:mi>\u2286<\/mml:mo>V<\/mml:mi>G<\/mml:mi><\/mml:msub><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula> such that every vertex in $$V_G-D$$<\/jats:tex-math>V<\/mml:mi>G<\/mml:mi><\/mml:msub>-<\/mml:mo>D<\/mml:mi><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula> is adjacent to at least one vertex in D<\/jats:italic>, and the domination number $$\\gamma (G)$$<\/jats:tex-math>\u03b3<\/mml:mi>(<\/mml:mo>G<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula> of G<\/jats:italic> is the minimum cardinality of a dominating set of G<\/jats:italic>. A set $$C\\subseteq V_G$$<\/jats:tex-math>C<\/mml:mi>\u2286<\/mml:mo>V<\/mml:mi>G<\/mml:mi><\/mml:msub><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula> is a covering set of G<\/jats:italic> if every edge of G<\/jats:italic> has at least one vertex in C<\/jats:italic>. The covering number $$\\beta (G)$$<\/jats:tex-math>\u03b2<\/mml:mi>(<\/mml:mo>G<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula> of G<\/jats:italic> is the minimum cardinality of a covering set of G<\/jats:italic>. The set of connected graphs\u00a0G<\/jats:italic> for which $$\\gamma (G)=\\beta (G)$$<\/jats:tex-math>\u03b3<\/mml:mi>(<\/mml:mo>G<\/mml:mi>)<\/mml:mo>=<\/mml:mo>\u03b2<\/mml:mi>(<\/mml:mo>G<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula> is denoted by $${\\mathcal {C}}_{\\gamma =\\beta }$$<\/jats:tex-math>C<\/mml:mi>\u03b3<\/mml:mi>=<\/mml:mo>\u03b2<\/mml:mi><\/mml:mrow><\/mml:msub><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, whereas $${\\mathcal {B}}$$<\/jats:tex-math>B<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula> denotes the set of all connected bipartite graphs in which the domination number is equal to the cardinality of the smaller partite set. In this paper, we provide alternative characterizations of graphs belonging to $${\\mathcal {C}}_{\\gamma =\\beta }$$<\/jats:tex-math>C<\/mml:mi>\u03b3<\/mml:mi>=<\/mml:mo>\u03b2<\/mml:mi><\/mml:mrow><\/mml:msub><\/mml:math><\/jats:alternatives><\/jats:inline-formula> and $${\\mathcal {B}}$$<\/jats:tex-math>B<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Next, we present a quadratic time algorithm for recognizing bipartite graphs belonging to $${\\mathcal {B}}$$<\/jats:tex-math>B<\/mml:mi><\/mml:math><\/jats:alternatives><\/jats:inline-formula>, and, as a side result, we conclude that the algorithm of Arumugam et al.\u00a0(Discrete Appl Math 161:1859\u20131867, 2013) allows to recognize all the graphs belonging to the set $${\\mathcal {C}}_{\\gamma =\\beta }$$<\/jats:tex-math>C<\/mml:mi>\u03b3<\/mml:mi>=<\/mml:mo>\u03b2<\/mml:mi><\/mml:mrow><\/mml:msub><\/mml:math><\/jats:alternatives><\/jats:inline-formula> in quadratic time either. Finally, we consider the related problem of patrolling grids with mobile guards, and show that it can be solved in $$O(n \\log n + m)$$<\/jats:tex-math>O<\/mml:mi>(<\/mml:mo>n<\/mml:mi>log<\/mml:mo>n<\/mml:mi>+<\/mml:mo>m<\/mml:mi>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula> time, where n<\/jats:italic> is the number of line segments of the input grid and m<\/jats:italic> is the number of its intersection points.<\/jats:p>","DOI":"10.1007\/s10878-019-00454-6","type":"journal-article","created":{"date-parts":[[2019,10,25]],"date-time":"2019-10-25T23:52:37Z","timestamp":1572047557000},"page":"55-71","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Graphs with equal domination and covering numbers"],"prefix":"10.1007","volume":"39","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4998-9844","authenticated-orcid":false,"given":"Andrzej","family":"Lingas","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2768-7861","authenticated-orcid":false,"given":"Mateusz","family":"Miotk","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8069-7850","authenticated-orcid":false,"given":"Jerzy","family":"Topp","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6378-7742","authenticated-orcid":false,"given":"Pawe\u0142","family":"\u017byli\u0144ski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,10,25]]},"reference":[{"key":"454_CR1","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/j.dam.2016.03.004","volume":"208","author":"JD Alvarado","year":"2016","unstructured":"Alvarado JD, Dantas S, Rautenbach D (2016) Strong equality of Roman and weak Roman domination in trees. Discrete Appl Math 208:19\u201326","journal-title":"Discrete Appl Math"},{"key":"454_CR2","doi-asserted-by":"publisher","first-page":"1859","DOI":"10.1016\/j.dam.2013.02.009","volume":"161","author":"S Arumugam","year":"2013","unstructured":"Arumugam S, Jose BK, Bujt\u00e1s C, Tuza Z (2013) Equality of domination and transversal numbers in hypergraphs. Discrete Appl Math 161:1859\u20131867","journal-title":"Discrete Appl Math"},{"key":"454_CR3","doi-asserted-by":"crossref","unstructured":"Balaban IJ (1995) An optimal algorithm for finding segments intersections. In: Proceedings of 11 annual ACM symposium on computational geometry. ACM, New York, pp 211\u2013219","DOI":"10.1145\/220279.220302"},{"issue":"3","key":"454_CR4","first-page":"139","volume":"15","author":"P Bose","year":"2013","unstructured":"Bose P, Cardinal J, Collette S, Hurtado F, Korman M, Langerman S, Taslakian P (2013) Coloring and guarding arrangements. Discrete Math Theor Comput Sci 15(3):139\u2013154","journal-title":"Discrete Math Theor Comput Sci"},{"issue":"8","key":"454_CR5","doi-asserted-by":"publisher","first-page":"1653","DOI":"10.1080\/00207160.2013.775423","volume":"90","author":"VE Brimkov","year":"2013","unstructured":"Brimkov VE (2013) Approximability issues of guarding a set of segments. Int J Comput Math 90(8):1653\u20131667","journal-title":"Int J Comput Math"},{"key":"454_CR6","doi-asserted-by":"crossref","DOI":"10.1201\/b19731","volume-title":"Graphs and digraphs","author":"G Chartrand","year":"2015","unstructured":"Chartrand G, Lesniak L, Zhang P (2015) Graphs and digraphs. Chapman and Hall\/CRC, Boca Raton"},{"issue":"3","key":"454_CR7","doi-asserted-by":"publisher","first-page":"661","DOI":"10.7151\/dmgt.1880","volume":"36","author":"M Dettlaff","year":"2016","unstructured":"Dettlaff M, Lema\u0144ska M, Semani\u0161in G, Zuazua R (2016) Some variations of perfect graphs. Discuss Math Graph Theory 36(3):661\u2013668","journal-title":"Discuss Math Graph Theory"},{"key":"454_CR8","doi-asserted-by":"crossref","unstructured":"Dumitrescu A, Mitchell JBS, \u017byli\u0144ski P (2014) The minimum guarding tree problem. Discrete Math Algorithms Appl 6(1), #1450011","DOI":"10.1142\/S1793830914500116"},{"issue":"2","key":"454_CR9","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1007\/s00224-016-9744-7","volume":"62","author":"SP Fekete","year":"2018","unstructured":"Fekete SP, Huang K, Mitchell JSB, Parekh O, Phillips CA (2018) Geometric hitting set for segments of few orientations. Theory Comput Syst 62(2):268\u2013303","journal-title":"Theory Comput Syst"},{"issue":"4","key":"454_CR10","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1007\/BF01848079","volume":"16","author":"JF Fink","year":"1985","unstructured":"Fink JF, Jacobson MS, Kinch LF, Roberts J (1985) On graphs having domination number half their order. Period Math Hung 16(4):287\u2013293","journal-title":"Period Math Hung"},{"key":"454_CR11","first-page":"133","volume":"2","author":"T Gallai","year":"1959","unstructured":"Gallai T (1959) \u00dcber extreme Punkt- und Kantenmengen. Ann Univ Sci Budapest E\u00f6tv\u00f6s Sec Math 2:133\u2013138","journal-title":"Ann Univ Sci Budapest E\u00f6tv\u00f6s Sec Math"},{"issue":"120","key":"454_CR12","doi-asserted-by":"crossref","first-page":"221","DOI":"10.21136\/CMJ.1995.128526","volume":"45","author":"B Hartnell","year":"1995","unstructured":"Hartnell B, Rall DF (1995) A characterization of graphs in which some minimum dominating set covers all the edges. Czechoslov Math J 45(120):221\u2013230","journal-title":"Czechoslov Math J"},{"key":"454_CR13","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/S0012-365X(03)00185-7","volume":"272","author":"TW Haynes","year":"2003","unstructured":"Haynes TW, Henning MA (2003) Changing and unchanging domination: a classification. Discrete Math 272:65\u201379","journal-title":"Discrete Math"},{"issue":"3","key":"454_CR14","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1016\/j.dam.2016.09.035","volume":"217","author":"MA Henning","year":"2017","unstructured":"Henning MA, Klostermeyer WF (2017) Italian domination in trees. Discrete Appl Math 217(3):557\u2013564","journal-title":"Discrete Appl Math"},{"issue":"4","key":"454_CR15","doi-asserted-by":"publisher","first-page":"531","DOI":"10.2989\/16073606.2015.1096860","volume":"39","author":"MA Henning","year":"2016","unstructured":"Henning MA, Marcon SA (2016) A constructive characterization of trees with equal total domination and disjunctive domination numbers. Quaest Math 39(4):531\u2013543","journal-title":"Quaest Math"},{"key":"454_CR16","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/j.comgeo.2004.07.002","volume":"30","author":"MJ Katz","year":"2005","unstructured":"Katz MJ, Mitchell JSB, Nir Y (2005) Orthogonal segment stabbing. Comput Geom 30:197\u2013205","journal-title":"Comput Geom"},{"key":"454_CR17","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/j.ipl.2017.09.002","volume":"129","author":"M Korman","year":"2017","unstructured":"Korman M, Poon S-H, Roeloffzen M (2017) Line segment covering of cells in arrangements. Inf Process Lett 129:25\u201330","journal-title":"Inf Process Lett"},{"key":"454_CR18","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1007\/BFb0092276","volume":"885","author":"R Laskar","year":"1981","unstructured":"Laskar R, Walikar HB (1981) On domination related concepts in graph theory. Lect Notes Math 885:308\u2013320","journal-title":"Lect Notes Math"},{"issue":"5","key":"454_CR19","doi-asserted-by":"publisher","first-page":"1169","DOI":"10.1007\/s00373-019-02068-5","volume":"35","author":"M Miotk","year":"2019","unstructured":"Miotk M, Topp J, \u017byli\u0144ski P (2019) Bipartization of graphs. Graphs Combin 35(5):1169\u20131177","journal-title":"Graphs Combin"},{"issue":"2","key":"454_CR20","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0020-0190(86)90050-5","volume":"23","author":"S Ntafos","year":"1986","unstructured":"Ntafos S (1986) On gallery watchman in grids. Inf Process Lett 23(2):99\u2013102","journal-title":"Inf Process Lett"},{"key":"454_CR21","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1002\/jgt.3190060104","volume":"6","author":"C Payan","year":"1982","unstructured":"Payan C, Xuong NH (1982) Domination-balanced graphs. J Graph Theory 6:23\u201332","journal-title":"J Graph Theory"},{"issue":"1","key":"454_CR22","doi-asserted-by":"publisher","first-page":"1","DOI":"10.5614\/ejgta.2017.5.1.1","volume":"5","author":"NJ Rad","year":"2017","unstructured":"Rad NJ (2017) A note on the edge Roman domination in trees. Electron J Graph Theory Appl 5(1):1\u20136","journal-title":"Electron J Graph Theory Appl"},{"issue":"1\u20133","key":"454_CR23","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/S0012-365X(98)00103-4","volume":"191","author":"B Randerath","year":"1998","unstructured":"Randerath B, Volkmann L (1998) Characterization of graphs with equal domination and covering number. Discrete Math 191(1\u20133):159\u2013169","journal-title":"Discrete Math"},{"key":"454_CR24","doi-asserted-by":"publisher","first-page":"5015","DOI":"10.1016\/j.disc.2007.08.088","volume":"308","author":"V Samodivkin","year":"2008","unstructured":"Samodivkin V (2008) Changing and unchanging of the domination number of a graph. Discrete Math 308:5015\u20135025","journal-title":"Discrete Math"},{"key":"454_CR25","first-page":"403","volume":"54","author":"E Sampathkumar","year":"1992","unstructured":"Sampathkumar E, Neeralagi PS (1992) Domination and neighbourhood critical, fixed, free and totally free points. Sankhy\u0101 54:403\u2013407","journal-title":"Sankhy\u0101"},{"key":"454_CR26","doi-asserted-by":"publisher","first-page":"51","DOI":"10.1016\/j.ipl.2017.11.011","volume":"131","author":"X Tan","year":"2018","unstructured":"Tan X, Jiang B (2018) An improved algorithm for computing a shortest watchman route for lines. Inf Process Lett 131:51\u201354","journal-title":"Inf Process Lett"},{"key":"454_CR27","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1016\/0166-218X(94)00073-9","volume":"63","author":"J Topp","year":"1995","unstructured":"Topp J, Vestergaard PD (1995) Well irredundant graphs. Discrete Appl Math 63:267\u2013276","journal-title":"Discrete Appl Math"},{"issue":"1\u20132","key":"454_CR28","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/0166-218X(94)90110-4","volume":"51","author":"L Volkmann","year":"1994","unstructured":"Volkmann L (1994) On graphs with equal domination and covering numbers. Discrete Appl Math 51(1\u20132):211\u2013217","journal-title":"Discrete Appl Math"},{"key":"454_CR29","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-7091-9449-2","volume-title":"Fundamente der Graphentheorie","author":"L Volkmann","year":"1996","unstructured":"Volkmann L (1996) Fundamente der Graphentheorie. Springer, Wien"},{"issue":"3","key":"454_CR30","first-page":"803","volume":"35","author":"Y Wu","year":"2012","unstructured":"Wu Y, Yu Q (2012) A characterization of graphs with equal domination number and vertex cover number. Bull Malay Math Sci Soc 35(3):803\u2013806","journal-title":"Bull Malay Math Sci Soc"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-019-00454-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-019-00454-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-019-00454-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,23]],"date-time":"2020-10-23T23:20:27Z","timestamp":1603495227000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-019-00454-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,10,25]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["454"],"URL":"https:\/\/doi.org\/10.1007\/s10878-019-00454-6","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,10,25]]},"assertion":[{"value":"25 October 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Compliance with ethical standards"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}