{"entities":{"Q1896346":{"pageid":1907088,"ns":120,"title":"Item:Q1896346","lastrevid":69218142,"modified":"2026-04-13T05:33:15Z","type":"item","id":"Q1896346","labels":{"en":{"language":"en","value":"Minimum proper interval graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 790751"}},"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":"Q1896346$29129FD0-DF1E-4CFA-B294-DA6E5F43B3F5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"3f205fd90c2ecd52518a3c690c59fb4317855c68","datavalue":{"value":{"text":"Minimum proper interval graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1896346$37100D99-B6FA-41A9-97DD-E2631F2358EA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7c1ac73069ed79834844b449454f9684794685b9","datavalue":{"value":"0828.05053","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1896346$EC094F9F-D86D-4A4D-9244-19241C07904F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"6514e8189360825c52eea83a036a1465589d4e89","datavalue":{"value":"10.1016/0012-365X(95)00007-J","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1896346$56677BEA-679E-4BF9-9DB4-4A5E43992DA3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cc45e6b9322bed7360e4aac2a42f8c73614b44f3","datavalue":{"value":{"entity-type":"item","numeric-id":1787138,"id":"Q1787138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1896346$96953FAE-C7E1-434F-B968-2276E5121C97","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1896346$65FBF252-6269-4A01-B59B-88CB97D93DC6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"771c3d65e511c1c23ff132299f8716909a176f01","datavalue":{"value":{"time":"+1995-12-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":"Q1896346$FA4D8D26-50FD-41F7-A516-433A878C52B3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4808c0d7a1b6b57f1d9a7fb3b0cab400d322dce1","datavalue":{"value":"A graph \\(G= (V, E)\\) is a proper interval graph, if we can associate to each vertex \\(v\\) in interval \\(I_v\\) on the real line, such that no such interval is a subset of another such interval, and for all distinct vertices \\(v\\), \\(w\\) we have \\((v, w)\\in V\\), if and only if \\(I_v\\) and \\(I_w\\) intersect. The number of cliques of a graph \\(G\\) is denoted by \\(c(G)\\). The clique graph of a graph \\(G\\), denoted by \\(K(G)\\), has as vertices the cliques of \\(G\\), vertices representing cliques are made adjacent when the cliques intersect. In this paper, it first is shown that for every proper interval graph \\(G= (V, E)\\) we have \\(|V|\\geq 2c(G)- c(K(G))\\). A proper interval graph \\(G= (V, E)\\) is said to be minimum, whenever \\(|V|= 2c(G)- c(K(G))\\). The main result of this paper is that the mapping \\(K\\) (mapping graphs to their clique graphs), when restricted to minimum proper interval graphs, is a bijection (up to isomorphism) onto the class of proper interval graphs, i.e., the clique graph of a minimum proper interval graph is a proper interval graph, and every proper interval graph is the clique graph of a minimum proper interval graph, which is unique up to isomorphism. A class of graphs \\(\\Pi\\) is clique-closed, if \\(\\{K(G)\\mid G\\in \\Pi\\}= \\Pi\\). The authors give a simple characterization of the greatest clique-closed class, contained in \\(\\Pi\\). They finally show how to enumerate the minimum proper interval graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1896346$FA544275-7C65-40FB-B426-0F1D4DCF8FD3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1896346$ACE75FF1-F639-4E44-AB18-6E9C341C4252","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1de0493fc6f7fe4361a54e7c2f5546e4ec52adf0","datavalue":{"value":"05C30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1896346$1B592E03-F46C-4E29-B512-B52A52FECD19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1896346$4D3B7CE1-7FEB-43FD-BC07-F2CE13E11C05","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"2bbb1063a5c9c23c1f6e33296dc9d4a7869c7b64","datavalue":{"value":"790751","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1896346$41354A6B-9A5B-4FF4-8FE5-C840D009019B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"816681eea21269f3ad56375e4f8d7d873b144eb6","datavalue":{"value":"enumeration","type":"string"},"datatype":"string"},"type":"statement","id":"Q1896346$9DBF7BD9-45BA-44F2-A542-FE2EF00002AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"993e57f960ae28ae2ddd18dd9f0aaab8b9406577","datavalue":{"value":"proper interval graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1896346$258C390F-D3AD-407D-AC75-BE867BB193C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e81fc0b274ca6568194209cb25b533d8b15c5470","datavalue":{"value":"interval","type":"string"},"datatype":"string"},"type":"statement","id":"Q1896346$1B2AC77F-4D69-4FB2-82D9-67C6DA34B7C6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7c7d07dfb3f5d6307c15a3861a142fe9ee876723","datavalue":{"value":"number of cliques","type":"string"},"datatype":"string"},"type":"statement","id":"Q1896346$B18DFC7D-AD30-4E4D-8847-40117C02C598","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"508b26b90b28bf80655ce1dc914f7360e3a34054","datavalue":{"value":"clique graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1896346$ECC81081-7DA2-420B-A71F-5B6AF0B4FC02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c89639778a113cbe54a2efcba7f98ccd79f62275","datavalue":{"value":"characterization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1896346$95F46A06-CC22-4526-9D3A-10B0409B6DA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6c34b3577461e44b6cd7df04344306569ebb2abd","datavalue":{"value":"greatest clique-closed class","type":"string"},"datatype":"string"},"type":"statement","id":"Q1896346$F5237EB8-34B7-4C08-8029-8180667640CF","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"eea1ea35de576c62b8101835521aa928ecd629a1","datavalue":{"value":{"entity-type":"item","numeric-id":242851,"id":"Q242851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1896346$6419BAEC-F197-45A7-A666-92EB233114E8","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":"Q1896346$72653095-6B1B-4A0E-968F-64087C955332","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"751bb518407806a0775e238de3cb997abdfa1f23","datavalue":{"value":{"entity-type":"item","numeric-id":1324287,"id":"Q1324287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1896346$5A238BBB-A061-4991-ABB6-EEF4A7A6982B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"efbb5720a2095b9213fc8585d416a45576fcd724","datavalue":{"value":{"entity-type":"item","numeric-id":798677,"id":"Q798677"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1896346$0B961EE1-3EE8-4BA6-ADC8-027B12D16DA8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c9fd408bf23da3cc5f0a56cdc5f97ea8055e752a","datavalue":{"value":{"entity-type":"item","numeric-id":1149451,"id":"Q1149451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1896346$76A6E824-AABC-4133-908E-D15F56152347","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"024e946190d47a486577eea73186e5fb946fc7ff","datavalue":{"value":{"entity-type":"item","numeric-id":2542398,"id":"Q2542398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1896346$BF6DA4F1-9C08-4222-BAC5-BA7D24061D59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"748916b0bd02314d267ee1fd63d0d643e49c30f6","datavalue":{"value":{"entity-type":"item","numeric-id":2533745,"id":"Q2533745"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1896346$9081E417-B04E-485D-92FD-12D2C72A5E4B","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f38faae5daec986e28abb2f55258b075f91dbd1e","datavalue":{"value":{"entity-type":"item","numeric-id":2937311,"id":"Q2937311"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"384caa8b067b8261b8825c5953a24120726edd8f","datavalue":{"value":{"amount":"+0.7999805808067322","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":"Q1896346$146253A6-9D61-462D-BCBB-8CB7519FCB54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"95644cf9c2564b1878a6e4b99590e0768e8bebce","datavalue":{"value":{"entity-type":"item","numeric-id":4865528,"id":"Q4865528"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ffd7ccd22d4624f9faec525a42cc456ca3b1a380","datavalue":{"value":{"amount":"+0.7637397646903992","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":"Q1896346$D8A90A31-D9D8-48A2-BD06-D017906255A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2bdf0ca50a57f2ae036755a04a40fa1a4278241c","datavalue":{"value":{"entity-type":"item","numeric-id":3615962,"id":"Q3615962"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ffd7ccd22d4624f9faec525a42cc456ca3b1a380","datavalue":{"value":{"amount":"+0.7637397646903992","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":"Q1896346$28FA6738-5018-470C-8ACA-9B72EAC43FC9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a5f9762fe9ffd92fb59d9dc7aef57d465e1bf30a","datavalue":{"value":{"entity-type":"item","numeric-id":963366,"id":"Q963366"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4cb77de2cb86a11cde94a6aee8e80051d7dd333b","datavalue":{"value":{"amount":"+0.7587916254997253","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":"Q1896346$AB412F58-12F5-4BF9-8E51-50DBD3C1411C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dcce67a3017645c7343d29f8b4ce3ca9afd34d83","datavalue":{"value":{"entity-type":"item","numeric-id":3522959,"id":"Q3522959"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"242104eec0475662a230ce3f57f8b8bfd2284185","datavalue":{"value":{"amount":"+0.7577815651893616","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":"Q1896346$D8946C0A-4342-49E1-BB9F-DEF8BAF0584E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Minimum proper interval graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Minimum_proper_interval_graphs"}}}}}