{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,21]],"date-time":"2026-01-21T05:58:36Z","timestamp":1768975116355,"version":"3.49.0"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2022,5,26]],"date-time":"2022-05-26T00:00:00Z","timestamp":1653523200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,5,26]],"date-time":"2022-05-26T00:00:00Z","timestamp":1653523200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2022,6]]},"DOI":"10.1007\/s00373-022-02498-8","type":"journal-article","created":{"date-parts":[[2022,5,26]],"date-time":"2022-05-26T08:02:54Z","timestamp":1653552174000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["The Scattering Number of Strictly Chordal Graphs: Linear Time Determination"],"prefix":"10.1007","volume":"38","author":[{"given":"Lilian","family":"Markenzon","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3431-7730","authenticated-orcid":false,"given":"Christina F. E. M.","family":"Waga","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,5,26]]},"reference":[{"key":"2498_CR1","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/0012-365X(73)90138-6","volume":"5","author":"V Chv\u00e1tal","year":"1973","unstructured":"Chv\u00e1tal, V.: Tough graphs and Hamiltonian circuits. Discrete Math. 5, 215\u2013228 (1973)","journal-title":"Discrete Math."},{"key":"2498_CR2","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1016\/0095-8956(73)90038-5","volume":"15","author":"DR Woodall","year":"1973","unstructured":"Woodall, D.R.: The binding number of a graph and its Anderson number. J. Combin. Theory Ser. B 15, 225\u2013255 (1973)","journal-title":"J. Combin. Theory Ser. B"},{"key":"2498_CR3","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1016\/0095-8956(78)90013-8","volume":"24","author":"HA Jung","year":"1978","unstructured":"Jung, H.A.: On a class of posets and the corresponding comparability graphs. J. Combin. Theory Ser. B 24, 125\u2013133 (1978)","journal-title":"J. Combin. Theory Ser. B"},{"key":"2498_CR4","first-page":"12","volume":"1","author":"CA Barefoot","year":"1987","unstructured":"Barefoot, C.A., Entringer, R., Swart, H.C.: Vulnerability in graphs - A comparative survey. J. Combin. Math. Combin. Comput. 1, 12\u201322 (1987)","journal-title":"J. Combin. Math. Combin. Comput."},{"key":"2498_CR5","unstructured":"Cozzens, M.B., Moazzami, D., Stueckle, S.: The tenacity of a graph. In: Alavi, Y., Schwenk, A. (eds.) Graph Theory, Combinatorics and Algorithms, Proceedings of 7th International Conference on the Theory and Applications of Graphs, pp. 1111\u20131122. Wiley, New York (1995)"},{"issue":"7","key":"2498_CR6","doi-asserted-by":"publisher","first-page":"793","DOI":"10.1080\/00207160412331336062","volume":"82","author":"Y Li","year":"2005","unstructured":"Li, Y., Zhang, S., Li, X.: Rupture degree of graphs. Int. J. Comput. Math. 82(7), 793\u2013803 (2005)","journal-title":"Int. J. Comput. Math."},{"key":"2498_CR7","first-page":"153","volume":"2","author":"R Sundareswaran","year":"2012","unstructured":"Sundareswaran, R., Swaminathan, V.: Domination integrity in trees. Bull. Int. Math. Virtual Inst. 2, 153\u2013161 (2012)","journal-title":"Bull. Int. Math. Virtual Inst."},{"key":"2498_CR8","first-page":"33","volume":"96","author":"FW Li","year":"2015","unstructured":"Li, F.W.: On isolated rupture degree of graphs. Util. Math. 96, 33\u201347 (2015)","journal-title":"Util. Math."},{"issue":"15","key":"2498_CR9","doi-asserted-by":"publisher","first-page":"287","DOI":"10.14311\/NNW.2015.25.015","volume":"3","author":"F Li","year":"2015","unstructured":"Li, F.: Isolated rupture degree of trees and gear graphs. Neural Netw. World 3(15), 287\u2013300 (2015)","journal-title":"Neural Netw. World"},{"issue":"3","key":"2498_CR10","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1080\/00207160410001661690","volume":"81","author":"S Zhang","year":"2004","unstructured":"Zhang, S., Peng, S.: Relationships between scattering number and other vulnerability parameters. Int. J. Comput. Math. 81(3), 291\u2013298 (2004)","journal-title":"Int. J. Comput. Math."},{"issue":"1","key":"2498_CR11","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00373-006-0649-0","volume":"22","author":"D Bauer","year":"2006","unstructured":"Bauer, D., Broersma, H., Schmeichel, E.: Toughness in graphs - a survey. Graphs Combin. 22(1), 1\u201335 (2006)","journal-title":"Graphs Combin."},{"key":"2498_CR12","unstructured":"Kratsch, D., Klots, T., M\u00fcller, H.: Computing the toughness and the scattering number for interval and other graphs. INRIA, Rapport de recherche 2237, pp. 1\u201322 (1994)"},{"key":"2498_CR13","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/0166-218X(90)90001-S","volume":"28","author":"D Bauer","year":"1990","unstructured":"Bauer, D., Hakimi, S.L., Schmeichel, E.: Recognizing tough graphs is NP-hard. Discrete Appl. Math. 28, 191\u2013195 (1990)","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"2498_CR14","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1080\/00207160211919","volume":"79","author":"S Zhang","year":"2002","unstructured":"Zhang, S., Li, X., Han, X.: Computing the scattering number of graphs. Int. J. Comput. Math. 79(2), 179\u2013187 (2002)","journal-title":"Int. J. Comput. Math."},{"key":"2498_CR15","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1016\/S0166-218X(96)00133-3","volume":"77","author":"D Kratsch","year":"1997","unstructured":"Kratsch, D., Klots, T., M\u00fcller, H.: Measuring the vulnerability for classes of intersection graphs. Discrete Appl. Math. 77, 259\u2013270 (1997)","journal-title":"Discrete Appl. Math."},{"key":"2498_CR16","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/0012-365X(95)00359-5","volume":"170","author":"JS Deogun","year":"1997","unstructured":"Deogun, J.S., Kratsch, C.D., Steiner, G.: 1-Tough cocomparability graphs are Hamiltonian. Discrete Math. 170, 99\u2013106 (1997)","journal-title":"Discrete Math."},{"key":"2498_CR17","unstructured":"Broersma, H.: How tough is toughness?, Bull. Eur. Assoc. Theor. Comput. Sci. EATCS 117 (2015)"},{"issue":"2","key":"2498_CR18","doi-asserted-by":"publisher","first-page":"725","DOI":"10.1111\/itor.12319","volume":"26","author":"L Markenzon","year":"2019","unstructured":"Markenzon, L., Waga, C.F.E.M.: Toughness and Hamiltonicity of strictly chordal graphs. Int. Trans. Oper. Res. 26(2), 725\u2013731 (2019)","journal-title":"Int. Trans. Oper. Res."},{"issue":"4","key":"2498_CR19","doi-asserted-by":"publisher","first-page":"282","DOI":"10.1002\/jgt.21832","volume":"79","author":"H Broersma","year":"2015","unstructured":"Broersma, H., Fiala, F., Golovach, P.A., Kaiser, T., Paulusma, P., Proskurowski, P.: Linear-time algorithms for scattering number and Hamilton-connectivity of interval graphs. J. Graph Theory 79(4), 282\u2013299 (2015)","journal-title":"J. Graph Theory"},{"key":"2498_CR20","first-page":"1","volume":"1","author":"E Aslan","year":"2011","unstructured":"Aslan, E., Kirlangic, A.: Computing the scattering number and the toughness for gear graphs. Bull. Int. Math. Virtual Inst. 1, 1\u201311 (2011)","journal-title":"Bull. Int. Math. Virtual Inst."},{"key":"2498_CR21","first-page":"53","volume":"4","author":"E Aslan","year":"2014","unstructured":"Aslan, E.: A measure of graphs vulnerability: edge scattering number. Bull. Soc. Math. Banja Luka 4, 53\u201360 (2014)","journal-title":"Bull. Soc. Math. Banja Luka"},{"issue":"CTAC2020","key":"2498_CR22","doi-asserted-by":"publisher","first-page":"C72","DOI":"10.21914\/anziamj.v62.15912","volume":"62","author":"M Jurkiewicz","year":"2021","unstructured":"Jurkiewicz, M.: Bounds on isolated scattering number. ANZIAM J. 62(CTAC2020), C72\u2013C83 (2021)","journal-title":"ANZIAM J."},{"issue":"E","key":"2498_CR23","doi-asserted-by":"publisher","first-page":"E81","DOI":"10.21914\/anziamj.v58i0.10993","volume":"58","author":"F Li","year":"2017","unstructured":"Li, F., Ye, Q., Sun, Y.: The isolated scattering number can be computed in polynomial time for interval graphs. ANZIAM J. 58(E), E81\u2013E97 (2017)","journal-title":"ANZIAM J."},{"key":"2498_CR24","doi-asserted-by":"publisher","first-page":"118","DOI":"10.1016\/j.dam.2019.01.004","volume":"264","author":"F Li","year":"2019","unstructured":"Li, F., Zhang, X., Broersma, H.: A polynomial algorithm for weighted scattering number in interval graphs. Discrete Appl. Math. 264, 118\u2013124 (2019)","journal-title":"Discrete Appl. Math."},{"key":"2498_CR25","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/S0166-218X(01)00330-4","volume":"124","author":"MC Golumbic","year":"2002","unstructured":"Golumbic, M.C., Peled, U.N.: Block duplicate graphs and a hierarchy of chordal graphs. Discrete Appl. Math. 124, 67\u201371 (2002)","journal-title":"Discrete Appl. Math."},{"key":"2498_CR26","unstructured":"Kennedy, W.: Strictly chordal graphs and phylogenetic roots. Master Thesis, University of Alberta (2005)"},{"key":"2498_CR27","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1016\/j.dam.2009.09.008","volume":"158","author":"A Brandst\u00e4dt","year":"2010","unstructured":"Brandst\u00e4dt, A., Wagner, P.: Characterising $$(k,\\ell )$$-leaf powers. Discrete Appl. Math. 158, 110\u2013122 (2010)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"2498_CR28","doi-asserted-by":"publisher","first-page":"1","DOI":"10.4153\/CMB-1963-001-x","volume":"6","author":"F Harary","year":"1963","unstructured":"Harary, F.: A characterization of block graphs. Can. Math. Bull. 6(1), 1\u20136 (1963)","journal-title":"Can. Math. Bull."},{"key":"2498_CR29","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/0166-218X(93)90227-F","volume":"44","author":"JRS Blair","year":"1993","unstructured":"Blair, J.R.S.: The efficiency of AC graphs. Discrete Appl. Math. 44, 119\u2013138 (1993)","journal-title":"Discrete Appl. Math."},{"key":"2498_CR30","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/j.ipl.2006.01.004","volume":"98","author":"A Brandst\u00e4dt","year":"2006","unstructured":"Brandst\u00e4dt, A., Le, V.B.: Structure and linear time recognition of 3-leaf powers. Inform. Process. Lett. 98, 133\u2013138 (2006)","journal-title":"Inform. Process. Lett."},{"key":"2498_CR31","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/978-3-540-30551-4_35","volume":"3341","author":"M Dom","year":"2004","unstructured":"Dom, M., Guo, J., H\u00fcffner, F., Niedermeier, R.: Error compensation in leaf root problems. Lecture Notes Comput. Sci. 3341, 389\u2013401 (2004)","journal-title":"Lecture Notes Comput. Sci."},{"key":"2498_CR32","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/j.endm.2016.03.024","volume":"52","author":"L Markenzon","year":"2016","unstructured":"Markenzon, L., Waga, C.F.E.M.: Strictly interval graphs: characterization and linear time recognition. Electron. Notes Discrete Math. 52, 181\u2013188 (2016)","journal-title":"Electron. Notes Discrete Math."},{"key":"2498_CR33","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1016\/j.laa.2016.12.007","volume":"517","author":"E Estrada","year":"2017","unstructured":"Estrada, E., Benzi, M.: Core-satellite graphs: clustering, assortativity and spectral properties. Linear Algebra Appl. 517, 30\u201352 (2017)","journal-title":"Linear Algebra Appl."},{"key":"2498_CR34","first-page":"1","volume-title":"Graph Theory and Sparse Matrix Computation. IMA 56","author":"JRS Blair","year":"1993","unstructured":"Blair, J.R.S., Peyton, B.: An introduction to chordal graphs and clique trees. In: George, A., Gilbert, J.R., Liu, J.W.H. (eds.) Graph Theory and Sparse Matrix Computation. IMA 56, pp. 1\u201329. Springer, New York (1993)"},{"key":"2498_CR35","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"MC Golumbic","year":"2004","unstructured":"Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs, 2nd edn. Academic Press, New York (2004)","edition":"2"},{"key":"2498_CR36","volume-title":"Topics in Algorithmic Graph Theory","year":"2021","unstructured":"Beineke, L.W., Golumbic, M.C., Wilson, R.J. (eds.): Topics in Algorithmic Graph Theory. Cambridge University Press, New York (2021)"},{"key":"2498_CR37","doi-asserted-by":"publisher","first-page":"683","DOI":"10.1111\/j.1475-3995.2009.00751.x","volume":"17","author":"L Markenzon","year":"2010","unstructured":"Markenzon, L., Pereira, P.R.C.: One-phase algorithm for the determination of minimal vertex separators of chordal graphs. Int. Trans. Oper. Res. 17, 683\u2013690 (2010)","journal-title":"Int. Trans. Oper. Res."},{"key":"2498_CR38","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/j.dam.2014.03.024","volume":"196","author":"L Markenzon","year":"2015","unstructured":"Markenzon, L., Waga, C.F.E.M.: New results on ptolemaic graphs. Discrete Appl. Math. 196, 135\u2013140 (2015)","journal-title":"Discrete Appl. Math."},{"key":"2498_CR39","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1016\/j.dam.2018.05.058","volume":"272","author":"L Markenzon","year":"2020","unstructured":"Markenzon, L.: Non-inclusion and other subclasses of chordal graphs. Discrete Appl. Math. 272, 43\u201347 (2020)","journal-title":"Discrete Appl. Math."},{"key":"2498_CR40","doi-asserted-by":"publisher","DOI":"10.21236\/AD0705364","volume-title":"Graph Theory","author":"F Harary","year":"1969","unstructured":"Harary, F.: Graph Theory. Addison-Wesley, Reading, MA (1969)"}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-022-02498-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00373-022-02498-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-022-02498-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,6,9]],"date-time":"2022-06-09T22:46:59Z","timestamp":1654814819000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00373-022-02498-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,5,26]]},"references-count":40,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,6]]}},"alternative-id":["2498"],"URL":"https:\/\/doi.org\/10.1007\/s00373-022-02498-8","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"value":"0911-0119","type":"print"},{"value":"1435-5914","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,5,26]]},"assertion":[{"value":"7 July 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 April 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 April 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 May 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"Not applicable.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}},{"value":"Not applicable.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Code availability"}}],"article-number":"102"}}