{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,4]],"date-time":"2025-12-04T14:31:19Z","timestamp":1764858679049},"reference-count":15,"publisher":"Cambridge University Press (CUP)","issue":"5","license":[{"start":{"date-parts":[[2013,7,11]],"date-time":"2013-07-11T00:00:00Z","timestamp":1373500800000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2013,9]]},"abstract":"<jats:p>Let<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548313000254_inline1\"\/><jats:tex-math>$\\mathcal{H}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>be a set of connected graphs. A graph<jats:italic>G<\/jats:italic>is said to be<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548313000254_inline1\"\/><jats:tex-math>$\\mathcal{H}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-free if<jats:italic>G<\/jats:italic>does not contain any element of<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548313000254_inline1\"\/><jats:tex-math>$\\mathcal{H}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>as an induced subgraph. Let<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548313000254_inline2\"\/><jats:tex-math>$\\mathcal{F}_{k}(\\mathcal{H})$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>be the set of<jats:italic>k<\/jats:italic>-connected<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548313000254_inline1\"\/><jats:tex-math>$\\mathcal{H}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>-free graphs. When we study the relationship between forbidden subgraphs and a certain graph property, we often allow a finite exceptional set of graphs. But if the symmetric difference of<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548313000254_inline3\"\/><jats:tex-math>$\\mathcal{F}_{k}(\\mathcal{H}_{1})$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>and<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548313000254_inline4\"\/><jats:tex-math>$\\mathcal{F}_{k}(\\mathcal{H}_{2})$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>is finite and we allow a finite number of exceptions, no graph property can distinguish them. Motivated by this observation, we study when we obtain a finite symmetric difference. In this paper, our main aim is the following. If<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548313000254_inline5\"\/><jats:tex-math>$|\\mathcal{H}|\\leq 3$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>and the symmetric difference of<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548313000254_inline6\"\/><jats:tex-math>$\\mathcal{F}_{1}(\\{H\\})$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>and<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548313000254_inline7\"\/><jats:tex-math>$\\mathcal{F}_{1}(\\mathcal{H})$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>is finite, then either<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548313000254_inline8\"\/><jats:tex-math>$H\\in \\mathcal{H}$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>or<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548313000254_inline9\"\/><jats:tex-math>$|\\mathcal{H}|=3$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>and<jats:italic>H<\/jats:italic>=<jats:italic>C<\/jats:italic><jats:sup>3<\/jats:sup>. Furthermore, we prove that if the symmetric difference of<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548313000254_inline10\"\/><jats:tex-math>$\\mathcal{F}_{k}(\\{H_{1}\\})$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>and<jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"gif\" xlink:type=\"simple\" xlink:href=\"S0963548313000254_inline11\"\/><jats:tex-math>$\\mathcal{F}_{k}(\\{H_{2}\\})$<\/jats:tex-math><\/jats:alternatives><\/jats:inline-formula>is finite, then<jats:italic>H<\/jats:italic><jats:sub>1<\/jats:sub>=<jats:italic>H<\/jats:italic><jats:sub>2<\/jats:sub>.<\/jats:p>","DOI":"10.1017\/s0963548313000254","type":"journal-article","created":{"date-parts":[[2013,7,11]],"date-time":"2013-07-11T12:10:45Z","timestamp":1373544645000},"page":"733-748","source":"Crossref","is-referenced-by-count":2,"title":["Forbidden Subgraphs Generating Almost the Same Sets"],"prefix":"10.1017","volume":"22","author":[{"given":"SHINYA","family":"FUJITA","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"MICHITAKA","family":"FURUYA","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"KENTA","family":"OZEKI","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2013,7,11]]},"reference":[{"key":"S0963548313000254_ref14","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-003-0540-1"},{"key":"S0963548313000254_ref7","first-page":"297","volume-title":"The Theory and Applications of Graphs","author":"Duffus","year":"1981"},{"key":"S0963548313000254_ref4","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.10034"},{"key":"S0963548313000254_ref8","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(96)00147-1"},{"key":"S0963548313000254_ref2","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20270"},{"key":"S0963548313000254_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2011.07.022"},{"key":"S0963548313000254_ref5","volume-title":"Graphs and Digraphs","author":"Chartrand","year":"2005"},{"key":"S0963548313000254_ref15","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2005.11.010"},{"key":"S0963548313000254_ref6","volume-title":"Inequalities concerning dominating sets in graphs","author":"Cockayne","year":"1985"},{"key":"S0963548313000254_ref10","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548311000514"},{"key":"S0963548313000254_ref3","unstructured":"Bedrossian P. (1991) Forbidden subgraphs and minimum degree conditions for Hamiltonicity. PhD thesis, University of Memphis."},{"key":"S0963548313000254_ref1","doi-asserted-by":"crossref","first-page":"250","DOI":"10.1002\/jgt.20454","article-title":"Forbidden subgraphs and the existence of 2-factor.","volume":"64","author":"Aldred","year":"2010","journal-title":"J. Graph Theory"},{"key":"S0963548313000254_ref11","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-011-2655-y"},{"key":"S0963548313000254_ref9","first-page":"13","article-title":"Forbidden subgraphs and pancyclicity.","volume":"109","author":"Faudree","year":"1995","journal-title":"Congress Numer."},{"key":"S0963548313000254_ref13","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2005.08.002"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548313000254","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,14]],"date-time":"2024-05-14T11:04:23Z","timestamp":1715684663000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548313000254\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,7,11]]},"references-count":15,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2013,9]]}},"alternative-id":["S0963548313000254"],"URL":"https:\/\/doi.org\/10.1017\/s0963548313000254","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,7,11]]}}}