{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T13:27:57Z","timestamp":1740144477773,"version":"3.37.3"},"reference-count":22,"publisher":"EDP Sciences","issue":"4","license":[{"start":{"date-parts":[[2024,9,2]],"date-time":"2024-09-02T00:00:00Z","timestamp":1725235200000},"content-version":"vor","delay-in-days":63,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100020897","name":"Universidad Nacional de General Sarmiento","doi-asserted-by":"publisher","award":["PIP 2022-2024 GI - 11220210100392CO"],"award-info":[{"award-number":["PIP 2022-2024 GI - 11220210100392CO"]}],"id":[{"id":"10.13039\/100020897","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002923","name":"CONICET","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100002923","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2023,9,13]]},"published-print":{"date-parts":[[2024,7]]},"abstract":"<jats:p>A graph is called split if its vertex set can be partitioned into a stable set and a clique. In this article, we studied two variants of split graphs. A graph <jats:italic>G<\/jats:italic> is polar if its vertex set can be partitioned into two sets <jats:italic>A<\/jats:italic> and <jats:italic>B<\/jats:italic> such that <jats:italic>G<\/jats:italic>[<jats:italic>A<\/jats:italic>] is a complete multipartite graph and <jats:italic>G<\/jats:italic>[<jats:italic>B<\/jats:italic>] is a disjoint union of complete graphs. A 2-unipolar graph is a polar graph <jats:italic>G<\/jats:italic> such that <jats:italic>G<\/jats:italic>[<jats:italic>A<\/jats:italic>] is a clique and <jats:italic>G<\/jats:italic>[<jats:italic>B<\/jats:italic>] is the disjoint union of complete graphs with at most two vertices. We present a minimal forbidden induced subgraph characterization for 2-unipolar graphs. In addition, we show that they can be represented as an intersection of substars of special cacti. Let <jats:italic>G<\/jats:italic> be a graph class, the <jats:italic>G<\/jats:italic><jats:italic>-width<\/jats:italic> of a graph <jats:italic>G<\/jats:italic> is the minimum positive integer <jats:italic>k<\/jats:italic> such that there exist <jats:italic>k<\/jats:italic> independent sets <jats:italic>N<\/jats:italic><jats:sub>1<\/jats:sub>, \u2026 , <jats:italic>N<\/jats:italic><jats:italic><jats:sub>k<\/jats:sub><\/jats:italic> such that a set <jats:italic>F<\/jats:italic> of nonedges of <jats:italic>G<\/jats:italic>, whose endpoints belong to some <jats:italic>N<\/jats:italic><jats:italic><jats:sub>i<\/jats:sub><\/jats:italic> with <jats:italic>i<\/jats:italic> = 1, \u2026 , <jats:italic>k<\/jats:italic>, can be added so that the resulting graph <jats:italic>G<\/jats:italic><jats:italic><jats:sup>\u2032<\/jats:sup><\/jats:italic> belongs to <jats:italic>G<\/jats:italic>. We say that a graph <jats:italic>G<\/jats:italic> is <jats:italic>k<\/jats:italic>-probe-<jats:italic>G<\/jats:italic> if it has <jats:italic>G<\/jats:italic>-width at most <jats:italic>k<\/jats:italic> and when <jats:italic>G<\/jats:italic> is the class of split graphs it is denominated <jats:italic>k<\/jats:italic>-probe-split. We prove that deciding, given a graph <jats:italic>G<\/jats:italic> and a positive integer <jats:italic>k<\/jats:italic>, whether <jats:italic>G<\/jats:italic> is a <jats:italic>h<\/jats:italic>-probe-split graph for some <jats:italic>h<\/jats:italic> \u2264 <jats:italic>k<\/jats:italic> is NP-complete. Besides, a characterization by minimal forbidden induced subgraphs for 2-probe-split cographs is presented.<\/jats:p>","DOI":"10.1051\/ro\/2023149","type":"journal-article","created":{"date-parts":[[2023,9,15]],"date-time":"2023-09-15T08:17:22Z","timestamp":1694765842000},"page":"3597-3606","source":"Crossref","is-referenced-by-count":0,"title":["On two variants of split graphs: 2-unipolar graph and <i>k<\/i>-probe-split graph"],"prefix":"10.1051","volume":"58","author":[{"given":"Luciano N.","family":"Grippo","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6954-4992","authenticated-orcid":false,"given":"Ver\u00f3nica A.","family":"Moyano","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2024,9,2]]},"reference":[{"key":"R1","first-page":"21","volume":"79","author":"Cerioli","year":"2006","journal-title":"ARS Combin."},{"key":"R2","doi-asserted-by":"crossref","unstructured":"Chang M.-S., Hung L.-J., Kloks T. and Peng S.-L., Block-graph width, in Theory and Applications of Models of Computation, 6th Annual Conference, TAMC, Changsha, China, May 18\u201322, 2009. Proceedings (2009) 150\u2013157.","DOI":"10.1007\/978-3-642-02017-9_18"},{"key":"R3","doi-asserted-by":"crossref","first-page":"2496","DOI":"10.1016\/j.tcs.2010.10.041","volume":"412","author":"Chang","year":"2011","journal-title":"Theor. Comput. Sci."},{"key":"R4","doi-asserted-by":"crossref","first-page":"111","DOI":"10.1016\/j.dam.2018.11.028","volume":"281","author":"Contreras-Mendoza","year":"2020","journal-title":"Discrete Appl. Math."},{"key":"R5","doi-asserted-by":"crossref","first-page":"163","DOI":"10.1016\/0166-218X(81)90013-5","volume":"3","author":"Corneil","year":"1981","journal-title":"Discrete Appl. Math."},{"key":"R6","doi-asserted-by":"crossref","first-page":"2469","DOI":"10.1016\/j.dam.2008.01.026","volume":"156","author":"Ekim","year":"2008","journal-title":"Discrete Appl. Math."},{"key":"R7","doi-asserted-by":"crossref","first-page":"1652","DOI":"10.1016\/j.dam.2007.08.025","volume":"156","author":"Ekim","year":"2008","journal-title":"Discrete Appl. Math."},{"key":"R8","doi-asserted-by":"crossref","first-page":"158","DOI":"10.1016\/j.dam.2014.01.020","volume":"171","author":"Ekim","year":"2014","journal-title":"Discrete Appl. Math."},{"key":"R9","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1016\/j.dam.2013.08.011","volume":"162","author":"Eschen","year":"2014","journal-title":"Discrete Appl. Math."},{"key":"R10","unstructured":"Foldes S. and Hammer P.L., Split graphs, in Proceedings of the Eighth Southeastern Conference on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1977), Congressus Numerantium, No. XIX (1977) 311\u2013315."},{"key":"R11","doi-asserted-by":"crossref","first-page":"105","DOI":"10.1016\/0012-365X(78)90178-4","volume":"24","author":"Golumbic","year":"1978","journal-title":"Discrete Math."},{"key":"R12","doi-asserted-by":"crossref","unstructured":"Golumbic M.C., Algorithmic Graph Theory and Perfect Graphs. Vol. 57 of Annals of Discrete Mathematics, 2nd edition. Elsevier Science B.V., Amsterdam (2004).","DOI":"10.1016\/S0167-5060(04)80051-7"},{"key":"R13","doi-asserted-by":"crossref","first-page":"275","DOI":"10.1007\/BF02579333","volume":"1","author":"Hammer","year":"1981","journal-title":"Combinatorica"},{"key":"R14","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1016\/j.dam.2018.01.007","volume":"261","author":"Hell","year":"2019","journal-title":"Discrete Appl. Math."},{"key":"R15","doi-asserted-by":"crossref","unstructured":"Le V.B. and de Ridder H.N., Probe split graphs. Discrete Math. Theor. Comput. Sci. 9 (2007). DOI: 10.46298\/dmtcs.401.","DOI":"10.46298\/dmtcs.401"},{"key":"R16","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.tcs.2014.01.032","volume":"528","author":"Le","year":"2014","journal-title":"Theor. Comput. Sci."},{"key":"R17","doi-asserted-by":"crossref","unstructured":"Le V.B. and Peng S.-L., On the complete width and edge clique cover problems, in Computing and Combinatorics, edited by Xu D., Du D. and Du D.. Springer International Publishing, Cham (2015) 537\u2013547.","DOI":"10.1007\/978-3-319-21398-9_42"},{"key":"R18","doi-asserted-by":"crossref","first-page":"532","DOI":"10.1007\/s10878-016-0106-9","volume":"36","author":"Le","year":"2018","journal-title":"J. Comb. Optim."},{"key":"R19","doi-asserted-by":"crossref","first-page":"406","DOI":"10.1016\/1385-7258(77)90055-5","volume":"80","author":"Orlin","year":"1977","journal-title":"Indagationes Mathematicae (Proceedings)"},{"key":"R20","unstructured":"Szwarcfiter J.L. and Maffray F., On two generalizations of split graphs, in Plenary Presentation at ProNEx Workshop on Combinatorics, Algorithms, and Applications, Ubatuba, Brazil, September 2003 (2003)."},{"key":"R21","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1007\/BF01072106","volume":"21","author":"Tyshkevich","year":"1985","journal-title":"Cybernet. Systems Anal."},{"key":"R22","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1016\/0166-218X(96)00094-7","volume":"69","author":"Yan","year":"1996","journal-title":"Discrete Appl. Math."}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2023149\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,2]],"date-time":"2024-09-02T08:09:07Z","timestamp":1725264547000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2023149"}},"subtitle":[],"editor":[{"given":"M.B.","family":"Campelo Neto","sequence":"first","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]},{"given":"S.","family":"Klein","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]},{"given":"I.","family":"Loiseau","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]},{"given":"Y.","family":"Wakabayashi","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]},{"given":"A.","family":"Weintraub","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]},{"given":"V.","family":"dos Santos","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]},{"given":"T.","family":"Liebling","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]},{"given":"R.","family":"Mahjoub","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]},{"given":"N.","family":"Maculan","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2024,7]]},"references-count":22,"journal-issue":{"issue":"4"},"alternative-id":["ro220759"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2023149","relation":{},"ISSN":["0399-0559","2804-7303"],"issn-type":[{"type":"print","value":"0399-0559"},{"type":"electronic","value":"2804-7303"}],"subject":[],"published":{"date-parts":[[2024,7]]}}}