{"entities":{"Q1370176":{"pageid":1380916,"ns":120,"title":"Item:Q1370176","lastrevid":68753067,"modified":"2026-04-13T01:50:10Z","type":"item","id":"Q1370176","labels":{"en":{"language":"en","value":"Tree-decompositions of graphs. I"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1077947"}},"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":"Q1370176$2922C20E-4271-4F80-B29A-FA46DB3DF381","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"560766a3d9b81d2936d4b59807dce7fa3d4656b3","datavalue":{"value":{"text":"Tree-decompositions of graphs. I","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1370176$2CE0D15D-5E2B-4C94-817B-FC59B5DA13B3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"02ea0f9c55843539d88470a5adad8191de572586","datavalue":{"value":"0881.05106","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1370176$61D8E5A7-F881-438A-9D31-605F4C3B9311","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"aee7a06e5596eed91ca3448910c52624a33d93a5","datavalue":{"value":"10.1007/BF02882459","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1370176$9256AE0A-3CAE-4A75-A5AC-AAEAECF61ECA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1b1faf963eb37846086170f34d7b8dd26e2b2373","datavalue":{"value":{"entity-type":"item","numeric-id":339460,"id":"Q339460"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1370176$0E1C79A0-6F41-4B2F-A17E-4DD20E1267CE","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"45e1edb64efeee080173451c87c3f0c1d8534742","datavalue":{"value":{"entity-type":"item","numeric-id":174829,"id":"Q174829"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1370176$A50ADBF4-B125-4275-AA9C-46E3CDD2CFFD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"24fb4fe71a2595983b723d9da5040cfe01165fe6","datavalue":{"value":{"time":"+1998-02-16T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1370176$C7DE048F-0C3B-495D-873C-83BD08596E5D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6ef8a80f010a2e660ac33c24012fc8fc3846c826","datavalue":{"value":"The author proves the following two theorems:   Theorem 1. Let \\(G\\) be a connected graph with order \\(n\\geq 3\\) and size \\(2n-4\\) and \\(u\\) and \\(v\\) be two given vertices of \\(G\\) with \\(uv\\in E(G)\\). Then \\(G\\) has an \\(\\{n,n-2\\}\\)-tree-decomposition with \\(u\\) and \\(v\\) as the two singular vertices if and only if the number of edges \\(\\varepsilon(H)\\leq 2(|H|-1)-|H\\cap\\{u,v\\}|\\) for any induced subgraph \\(H\\) of \\(G\\) with order at least 3.   Theorem 2. Let \\(G\\) be a connected graph with order \\(n\\geq 3\\) and size \\(2n-4\\) and \\(u\\) and \\(v\\) be two given vertices of \\(G\\). Then \\(G\\) has an \\(\\{n-1,n-1\\}\\)-tree-decomposition with \\(u\\) and \\(v\\) as the two singular vertices if and only if \\(uv\\notin E(G)\\) and the number of edges \\(\\varepsilon(H)\\leq 2(|H|- 1)-|H\\cap\\{u,v\\}|\\) for any induced subgraph \\(H\\) of \\(G\\) with order at least 3.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1370176$E0A05F24-22FA-49D4-8DC3-309349C8F654","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1370176$E8629BF6-CDC5-426A-8CE6-5589ED0A4ABC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1370176$74C74381-306B-4022-A297-DF6C59B604BF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"68a3c025474834fc5e0c63b7d38c801aa0e344f9","datavalue":{"value":"1077947","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1370176$69C9F283-4F40-4D1E-9E5A-22DC2E311085","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a0073252dacd10c817f83ebbc24da5c2405f50f","datavalue":{"value":"tree-decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1370176$7155323C-FBAF-4110-A2C6-675863544D08","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1b064239038ee1a771c75dcf49f01efada6cdd6a","datavalue":{"value":"connected graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1370176$4D86D40E-E367-4E78-B0CD-C0C1093BD36E","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":"Q1370176$8AC3FC5A-8186-45B6-8321-99C36DF30D59","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e217ed7d0bce36931112f7f944f8ac1312fdff5","datavalue":{"value":{"entity-type":"item","numeric-id":4285595,"id":"Q4285595"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1370176$7EA0A1FA-D3FA-4BCD-B419-0ACC7D477E61","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"64ce004441f871e5d92d9a95b4a578266e4a39b5","datavalue":{"value":"https://doi.org/10.1007/bf02882459","type":"string"},"datatype":"url"},"type":"statement","id":"Q1370176$73285E4D-CE39-4FE5-8F59-BAD283DB7FB3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"0ee3d03d8448180f31f5ad8fa9526402a4df4000","datavalue":{"value":"W2025457122","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1370176$B7C45612-565B-4380-86A2-A49037C1DFCE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4dd1218516986efb797b2e3b02b5af5f2a88dc8c","datavalue":{"value":{"entity-type":"item","numeric-id":1387426,"id":"Q1387426"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c9259e0f7bae0a3121e1d525acaeb4d7e21bba7f","datavalue":{"value":{"amount":"+0.8838103413581848","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":"Q1370176$7F981B25-569C-478C-9ACB-080ACAA82536","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"36719aa5f010b4eed3a5d3faf6db02eff6bdf956","datavalue":{"value":{"entity-type":"item","numeric-id":5955927,"id":"Q5955927"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"61a0bfe07c0261bf8972571688db17772b306b2e","datavalue":{"value":{"amount":"+0.8470149636268616","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":"Q1370176$2DB2E617-735E-4500-B0F3-EAC74C9880B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0f03b4ddf5909c806625e5d616f94358fab87036","datavalue":{"value":{"entity-type":"item","numeric-id":2721877,"id":"Q2721877"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f5fb0fa06bd429417bd94b6be453f89717e6b3cb","datavalue":{"value":{"amount":"+0.8153936862945557","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":"Q1370176$71197268-8EB8-4C3C-8135-D47994DD1445","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6b2ca15800703407f6e50986b988c5ba5fbd8bb0","datavalue":{"value":{"entity-type":"item","numeric-id":3835473,"id":"Q3835473"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6f76070f7a35535696b94337df9528e2dd9432ad","datavalue":{"value":{"amount":"+0.8092013597488403","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":"Q1370176$C960D316-3B73-4F71-BF9B-36D6B70CBC95","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Tree-decompositions of graphs. I","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Tree-decompositions_of_graphs._I"}}}}}