{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T00:36:51Z","timestamp":1787359011047,"version":"build-2736575974"},"reference-count":23,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"DOI":"10.13039\/501100003141","name":"Consejo Nacional de Ciencia y Tecnolog\u00eda","doi-asserted-by":"publisher","award":["A1-S-8397"],"award-info":[{"award-number":["A1-S-8397"]}],"id":[{"id":"10.13039\/501100003141","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>We unify two popular graph classes, strongly chordal graphs and chordal bigraphs, by introducing an umbrella class that contains both classes and maintains their essential properties. This is done by allowing loops at vertices. Considering loops often has little impact on a class of graphs; it however makes a big difference in this case. We call the new class \\itstrongly chordal graphs with possible loops. When all vertices have loops, we recover the usual strongly chordal graphs; when all vertices are loopless, we obtain the usual chordal bigraphs. Moreover, there is a surprizing wealth of graphs in the new class that have loops at some vertices and not at others. These graphs also admit the elegant algorithms previously only applied in the extreme two cases. Formulated in the language of adjacency matrices, we study the class of symmetric 0, 1 matrices that admit a simultaneous row and column permutation avoiding the $\\Gamma$ matrix $[ \\begin{smallmatrix} 1 \\ 1 \\\\ 1 \\ 0 \\end{smallmatrix}]$. We give ordering characterizations, matrix characterizations, and forbidden subgraph characterizations of the new class, and illustrate its usefulness by solving the minimum domination problem in this general context. This implies solutions of both the minimum dominating set in strongly chordal graphs and the minimum total dominating set in chordal bigraphs.<\/jats:p>","DOI":"10.1137\/20m1316056","type":"journal-article","created":{"date-parts":[[2021,3,11]],"date-time":"2021-03-11T10:19:02Z","timestamp":1615457942000},"page":"362-375","source":"Crossref","is-referenced-by-count":1,"title":["Strong Chordality of Graphs with Possible Loops"],"prefix":"10.1137","volume":"35","author":[{"given":"Pavol","family":"Hell","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5867-3801","authenticated-orcid":true,"given":"C\u00e9sar","family":"Hern\u00e1ndez-Cruz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0786-2271","authenticated-orcid":true,"given":"Jing","family":"Huang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jephian C.-H.","family":"Lin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,3,11]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(84)90028-2"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1137\/0605034"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(90)90147-P"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(99)00149-3"},{"key":"atypb5","unstructured":"M. Farber,\n                      Applications of LP duality to problems involving independence and domination\n                      , Ph.D. Thesis, Rutgers University, 1982."},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(83)90154-1"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(84)90061-1"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2011.04.016"},{"key":"atypb9","doi-asserted-by":"crossref","unstructured":"M. C. Golumbic,\n                      Algorithmic Graph Theory and Perfect Graphs\n                      , Academic Press, New York, 1980.","DOI":"10.1016\/B978-0-12-289260-8.50010-8"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190020209"},{"key":"atypb11","unstructured":"P. L. Hammer, F. Maffray, and M. Preissmann,\n                      A characterization of chordal bipartite graphs\n                      , RUTCOR Research Report, Rutgers University, New Brunswick, NJ, RRR (1989), pp. 16-89."},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1137\/0202018"},{"key":"atypb13","unstructured":"P. Hell, C. Hern\u00e1ndez-Cruz, J. Huang, and J. C. H. Lin,\n                      Strongly chordal digraphs and $\\Gamma$-free matrices\n                      , preprint,arXiv:1909.03597,https:\/\/arxiv.org\/abs\/1909.03597."},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20006"},{"key":"atypb16","unstructured":"P. Hell, J. Huang, R. M. McConnell, and A. Rafiey,\n                      Interval-like graphs and digraphs\n                      , preprint,arXiv:1804.05258,https:\/\/arxiv.org\/abs\/1804.05258."},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1137\/0606070"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2006.01.001"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)00054-H"},{"key":"atypb20","unstructured":"L. Lov\u00e1sz,\n                      Combinatorial Problems and Exercises\n                      , North Holland, Amsterdam, 1979."},{"key":"atypb21","unstructured":"A. Lubiw,\n                      $\\Gamma$-free matrices\n                      , Mater's thesis, University of Waterloo, 1982."},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1137\/0216057"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.06.019"},{"key":"atypb24","doi-asserted-by":"crossref","unstructured":"A. M. Shresta, S. Tayu, and S. Ueno,\n                      On two-directional orthogonal ray graphs\n                      , Proceedings of 2010 IEEE International Symposium on Circuits and Systems, pp. 1807-1810.","DOI":"10.1109\/ISCAS.2010.5537709"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/20M1316056","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:19:24Z","timestamp":1787321964000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/20M1316056"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/20M1316056"],"URL":"https:\/\/doi.org\/10.1137\/20m1316056","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}