{"entities":{"Q528989":{"pageid":530756,"ns":120,"title":"Item:Q528989","lastrevid":62515992,"modified":"2026-04-11T06:36:48Z","type":"item","id":"Q528989","labels":{"en":{"language":"en","value":"Forbidden pairs with a common graph generating almost the same sets"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6719983"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528989$17BEE111-3352-4E75-98E3-A1CC16F7DC33","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c8c1c19a9ffb07f3a8ee5ea7c5248d4ba5f9ba12","datavalue":{"value":{"text":"Forbidden pairs with a common graph generating almost the same sets","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q528989$7893546A-00C9-4C1C-ADC7-851F36D09B9A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3bb51ea0e9ac2d0525850afb20dc5525a394ce15","datavalue":{"value":"1361.05084","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q528989$BF003678-0AF5-4D78-8D32-96C61F1DAF0D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4219df69c070052a1dacfbb5d143e62a898b6adf","datavalue":{"value":{"entity-type":"item","numeric-id":322264,"id":"Q322264"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528989$8940C466-77D8-4E89-9207-0FEB9AEDDE83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"218a609c99b77e3be2923e505e606bbb0fdd2db9","datavalue":{"value":{"entity-type":"item","numeric-id":383733,"id":"Q383733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528989$844B26A4-F86F-4CF5-ABDD-62EFDD8CA827","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2fea587b0b8abc947c30ceac0aa37e4e6b46ed6e","datavalue":{"value":{"entity-type":"item","numeric-id":343720,"id":"Q343720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528989$4E78A5A0-2E33-45D1-803C-42D37F904F2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d0801179a53573306bd74ebc9894c77285cd2dfc","datavalue":{"value":{"entity-type":"item","numeric-id":528988,"id":"Q528988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528989$D803B28F-3CF4-4DD5-9064-F147EF633284","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528989$2EA7D634-0047-44CB-8F93-160527AB65DC","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"46a30028c10f94c4944c801c86f2de5dd37da0f3","datavalue":{"value":{"time":"+2017-05-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q528989$E1490968-3ABC-4856-8B00-B695693E3714","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d2c5de9dc3fefe0b486f6a9cf49600b4db45ab47","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i2p13","type":"string"},"datatype":"url"},"type":"statement","id":"Q528989$264ABE36-53BC-476B-BED5-8B65262D5E94","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"180fc19cb9970a56bcdba976f7ebc2c5923095a7","datavalue":{"value":"Summary: Let \\(\\mathcal{H}\\) be a family of connected graphs. A graph \\(G\\) is said to be \\(\\mathcal{H}\\)-free if \\(G\\) does not contain any members of \\(\\mathcal{H}\\) as an induced subgraph. Let \\(\\mathcal{F}(\\mathcal{H})\\) be the family of connected \\(\\mathcal{H}\\)-free graphs. In this context, the members of \\(\\mathcal{H}\\) are called forbidden subgraphs.{  }In this paper, we focus on two pairs of forbidden subgraphs containing a common graph, and compare the classes of graphs satisfying each of the two forbidden subgraph conditions. Our main result is the following: Let \\(H_{1}\\), \\(H_{2}\\), \\(H_{3}\\) be connected graphs of order at least three, and suppose that \\(H_{1}\\) is twin-less. If the symmetric difference of \\(\\mathcal{F}(\\{H_{1},H_{2}\\})\\) and \\(\\mathcal{F}(\\{H_{1},H_{3}\\})\\) is finite and the tuple \\((H_{1};H_{2},H_{3})\\) is non-trivial in a sense, then \\(H_{2}\\) and \\(H_{3}\\) are obtained from the same vertex-transitive graph by successively replacing a vertex with a clique and joining the neighbors of the original vertex and the clique. Furthermore, we refine a result in [\\textit{S. Fujita}, Comb. Probab. Comput. 22, No. 5, 733--748 (2013; Zbl 1282.05167)] concerning forbidden pairs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q528989$1DCE6A94-28B4-4FD9-88B2-5E4397CD3BCD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2e742a171e2cc4a4f154f55124e2a34e0da3eb3e","datavalue":{"value":"05C60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q528989$7A891212-C8FF-4784-8D3B-B34D261732C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"74e7832a915a62c417a3bf8c026eff5989fd94d3","datavalue":{"value":"05C25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q528989$C670C0CE-4CEA-4BF1-9A10-AED5D56F46F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q528989$275E7149-EBBD-4FEE-835B-F6383BE003F7","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b3e26b8207c1bc37f83bd6c8f8fec66cef1b4379","datavalue":{"value":"6719983","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q528989$82270A8D-C360-4468-95AA-EAA70DE83658","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c1db4e3cd8c6237e3b25098b483a3ff821c3b321","datavalue":{"value":"forbidden subgraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q528989$DD17D14A-4A1D-44D7-A6CF-E9647168DE1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"28137d1c234bbe4af4fcf1d16257321ccdb8b772","datavalue":{"value":"star-free graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q528989$E443647E-08EC-4330-A6F2-93F8A008BA33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"05a77d68c909d7f46d16b5b1671423ea6800ac82","datavalue":{"value":"vertex-transitive graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q528989$62EDF282-D50F-4445-B999-E37BF51D307C","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528989$4784A262-0E18-48CF-AE35-9B884ADA78F7","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"d62e967816953cecad41268e715794a55d56323d","datavalue":{"value":{"entity-type":"item","numeric-id":3577833,"id":"Q3577833"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528989$613F359D-7E74-4FE1-9901-5A52254E67A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2a305482ce08ddf23fda29be6c489473ce73971c","datavalue":{"value":{"entity-type":"item","numeric-id":3918148,"id":"Q3918148"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528989$72CDD98C-AA09-4409-AB87-AEA67FF1B446","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1fcb9d125fa60a766d6a8330d086d9b2f47c0254","datavalue":{"value":{"entity-type":"item","numeric-id":1356695,"id":"Q1356695"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528989$2FCC59A4-74C6-4E0D-8119-D668B6A325AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"072e3bfe7ab4b00d00c8edecc86703e8254664dd","datavalue":{"value":{"entity-type":"item","numeric-id":1367026,"id":"Q1367026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528989$C0610A25-0E12-4F58-97BE-ACAD8C648A48","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6bfa8f59cf80cbd148b0d3b1142bd013009e49dd","datavalue":{"value":{"entity-type":"item","numeric-id":2428638,"id":"Q2428638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528989$8473A757-B424-44B8-AE0E-E8AB33A9F122","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b72586c617de888a2673c3f42e8069bb3c02a28a","datavalue":{"value":{"entity-type":"item","numeric-id":5397729,"id":"Q5397729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q528989$0132A4CA-9DC3-40C7-8EE9-129CF2D0E6BF","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"54d594fc080673bfa0d92f6dbce06b8df87817dd","datavalue":{"value":"bafkreigqqkxxjhqxvhwy4lkdzsup33yoqmxresq6mabvjextyahzzr7h7u","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q528989$D6594A34-202E-427C-9E79-E09EAA0CD92C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7d7bde72bd1f6d2874a9eff7a211efc2b0cb8ab6","datavalue":{"value":{"entity-type":"item","numeric-id":5397729,"id":"Q5397729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"187b8226bd428a11285dc4fde774a01e070c29c3","datavalue":{"value":{"amount":"+0.8553996086120605","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q528989$86BE4053-2773-41E1-A64A-CAAE16954653","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d755017ca8a9967ad5fab98106071f2d0bf32eef","datavalue":{"value":{"entity-type":"item","numeric-id":2342611,"id":"Q2342611"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7bda74c344a5419a61a5d5e131d33f2d44c0780f","datavalue":{"value":{"amount":"+0.7766793370246887","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q528989$6979FAA7-C772-4441-B4DA-ED86A9A52B36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7b3a70a57aa6034f2a9db93a51a4dbae7189553c","datavalue":{"value":{"entity-type":"item","numeric-id":1741581,"id":"Q1741581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"289754ac0632963a258a1a855aa21780b685f6e2","datavalue":{"value":{"amount":"+0.7642586827278137","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q528989$AA490C1D-1B0D-4501-8648-9CC9E35F5EB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9bf00685be9871e6e21d25f0670e4f9ffe2d95e1","datavalue":{"value":{"entity-type":"item","numeric-id":383734,"id":"Q383734"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ae65ffb664b3add66aa05772c411478fd093ead8","datavalue":{"value":{"amount":"+0.7624155282974243","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q528989$B47B74B7-FB5A-4606-8D0B-5940CCCC7948","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"29d507e465f586fa5f4b0c6bbe0a4bd883bd3cab","datavalue":{"value":{"entity-type":"item","numeric-id":409360,"id":"Q409360"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2b96d5f1b9245bac114a545fd36dbbb67183dbf4","datavalue":{"value":{"amount":"+0.7617620825767517","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q528989$4FC3FE0A-915E-4C79-AD7C-13BF2272C028","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Forbidden pairs with a common graph generating almost the same sets","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Forbidden_pairs_with_a_common_graph_generating_almost_the_same_sets"}}}}}