{"entities":{"Q1209724":{"pageid":1220473,"ns":120,"title":"Item:Q1209724","lastrevid":66308577,"modified":"2026-04-12T09:06:10Z","type":"item","id":"Q1209724","labels":{"en":{"language":"en","value":"Principal common divisors of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 168330"}},"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":"Q1209724$2333FF87-D861-482B-9F58-61D0BB994124","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"876b8b5c42a04eb28c8e1d250a3ee5f08efb9d41","datavalue":{"value":{"text":"Principal common divisors of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1209724$55CCCADF-F63B-4795-BED7-CF68BC32328C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0028e0b733d5cb3f556a2fb2d4817a7f28b44958","datavalue":{"value":"0781.05038","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209724$8B0CD3D9-25C4-4EE3-916D-D36758184329","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8e9da64877759bbc88a07be9f6dec74cbbc48ac2","datavalue":{"value":{"entity-type":"item","numeric-id":230773,"id":"Q230773"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209724$64633254-FBB4-4134-8F8D-CFBE3DC44767","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"67a3b32ce23d643b75c3ac5e86ed1ffe82868638","datavalue":{"value":{"entity-type":"item","numeric-id":186199,"id":"Q186199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209724$6900A735-7D8C-438E-B388-7E576DC72642","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1ef3efb47b5163e35efff4dde79a3bbdd3dc566b","datavalue":{"value":{"entity-type":"item","numeric-id":186200,"id":"Q186200"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209724$871E8922-A077-4DAE-922B-8A2FA7918348","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1ed7e5820f64aa71f4063f736e36c33cba77ee93","datavalue":{"value":{"entity-type":"item","numeric-id":801938,"id":"Q801938"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209724$ABACB4C1-A0B6-426D-83B8-D2722D921838","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ad20fa2baf1da520f7602890e3c8541de25a96e2","datavalue":{"value":{"entity-type":"item","numeric-id":233442,"id":"Q233442"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209724$C128B57A-CE35-45C2-8F9D-F879C3A27ADB","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b113bc4ac7ed430093230b872c083cde59919509","datavalue":{"value":{"entity-type":"item","numeric-id":166287,"id":"Q166287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209724$6500EF76-0442-46D1-BBFF-7F93538DDEEC","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1772b6c81a5108c06854e0de4518fb90e5a6ebdc","datavalue":{"value":{"time":"+1993-05-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":"Q1209724$81BB94E1-2832-496E-84DC-59308B870FA9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6ea415e2afa55fb2516d2e4cf042e489115a233f","datavalue":{"value":"If a graph \\(G\\) is \\(H\\)-decomposable, then \\(H\\) is said to divide \\(G\\). If \\(H \\neq G\\), then \\(H\\) properly divides \\(G\\). A graph \\(G\\) is a principal common divisor if there exist graphs \\(G_ 1\\) and \\(G_ 2\\) such that \\(G\\) properly divides \\(G_ 1\\) and \\(G_ 2\\) and if \\(H\\) is any graph that divides both \\(G_ 1\\) and \\(G_ 2\\) then \\(H\\) divides \\(G\\). The authors determine several classes of graphs that are principal common divisors. In particular it is shown that (1) for \\(n\\geq 4\\), the \\(n\\)-cycle \\(C_ n\\) is a principal common divisor, (2) for \\(n\\geq 2\\), the path \\(P_ n\\) is a principal common divisor and (3) for \\(n\\geq 3\\), \\(K(2,n)\\) is a principal common divisor. It is noted that \\(K(3,3)\\) is a principal common divisor but that it is not known which complete bipartite graphs \\(K(m,n)\\) where \\(m,n \\geq 3\\) and \\(m+n>6\\) are principal common divisors. A connected graph \\(G\\) of order \\(p\\) and size \\(q\\) is called primal if \\(q\\) is prime and \\(K_ p\\) contains at least two edge-disjoint copies of \\(G\\). It is shown that every primal graph is a principal common divisor. Moreover, it is shown that every tree of prime size is a principal common divisor. A graph \\(F\\) is said to be a shadow divisor of a graph \\(G\\) if \\(F\\) does not divide \\(G\\), but if \\(G\\) divides \\(H\\) and \\(H \\neq G\\), then \\(F\\) divides \\(H\\). It is shown that no graph having a shadow divisor is a principal common divisor. This result is used to show that no complete graph \\(K_ n\\), \\(n \\geq 3\\), is a principal common divisor.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1209724$CAE02C3D-C446-4035-B033-9E9347F863A8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209724$AED0D694-4A63-4313-B88C-9B426611B316","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6519097bce227c17fdc4ccd32ca5ae91d3403238","datavalue":{"value":"168330","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209724$1AAE4B7D-56CD-43C5-ACE7-E4496E587411","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2f020b91995f7fbf1f8603f8422ff917d84ff65c","datavalue":{"value":"\\(H\\)-decomposable","type":"string"},"datatype":"string"},"type":"statement","id":"Q1209724$243BE6DA-A277-48F8-BC2B-A4AD6CBEF4A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b249402f7abd2f8620e7761d51ac66d832685be3","datavalue":{"value":"principal common divisor","type":"string"},"datatype":"string"},"type":"statement","id":"Q1209724$0CAC0B1E-4B3D-4D53-9585-ACFD0B12476F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"08ae8cc92787291ae3823cb877779c25d7b1d775","datavalue":{"value":"primal graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1209724$F6949CBA-37BF-404F-ADD8-B0C50F57B66B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"65fa91493e28a85553704a98bcdb7ed5940aed67","datavalue":{"value":"shadow divisor","type":"string"},"datatype":"string"},"type":"statement","id":"Q1209724$AE66EDB9-3314-4351-A450-FC23926C662F","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7f532b639e1e3b8bde608d59d2d7e23b01bb3c75","datavalue":{"value":{"entity-type":"item","numeric-id":233441,"id":"Q233441"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1209724$EE149823-0A42-4F68-8C7C-9EB30294E0DB","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":"Q1209724$008D1FDD-4069-4FC0-92CB-B729D2F16776","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3b06ee18ec36ad7f75e93a8a80d7732baa504ea5","datavalue":{"value":"https://doi.org/10.1006/eujc.1993.1012","type":"string"},"datatype":"url"},"type":"statement","id":"Q1209724$FC05A39D-7EBF-4CBE-A271-6F498E7A8451","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"8b6ff9171945b69f221918676a4f558352eb8c3a","datavalue":{"value":"W2052667300","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209724$5C2E0F35-9107-4AF1-9765-975B813F74C8","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"b26d129d5f33e1d55b4d9a9fdfae274f05595b5c","datavalue":{"value":"Q106064566","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209724$C363F724-3EAE-4D6F-992B-78C1F0A2F464","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"51f1997d813f124ba8845fe663b410a45b90410a","datavalue":{"value":"10.1006/EUJC.1993.1012","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1209724$8E05E74D-3A2F-411B-AD62-C3367E4A446E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8707ce8131b59022ae1df1babca4e79af119f4be","datavalue":{"value":{"entity-type":"item","numeric-id":4697616,"id":"Q4697616"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"05715de7a6a69a68d82ee05f98420d67aba5a1da","datavalue":{"value":{"amount":"+0.8661477565765381","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":"Q1209724$1B7A3886-1F20-47F0-BCA7-13A58CCA477B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fda4e620b7f5eb13e819e8518f838dcc9583d581","datavalue":{"value":{"entity-type":"item","numeric-id":3804745,"id":"Q3804745"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"919f116f55b249a613e6f50e0bf049611fd14d09","datavalue":{"value":{"amount":"+0.8613004088401794","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":"Q1209724$FB9EDF27-E66A-4C73-9E7C-79A80FCCB093","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fbf4a8a691c8fe0fb355b40abcbbb7382834cc42","datavalue":{"value":{"entity-type":"item","numeric-id":1321642,"id":"Q1321642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"82a48fbfc0418383c741ec725d476ac82db30a80","datavalue":{"value":{"amount":"+0.8272676467895508","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":"Q1209724$28E77DEE-0B67-48F3-84C5-E5880D1A632A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2778a50ea4fa253f2228f7a06df514cf57aee4f0","datavalue":{"value":{"entity-type":"item","numeric-id":4329065,"id":"Q4329065"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1a1a40fe80c9451755a0f22ee72f67234d430560","datavalue":{"value":{"amount":"+0.8223785161972046","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":"Q1209724$4D2C612C-DBA8-4982-86D0-866DC0D44A6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ed8c26480550d726a566b9892a4ba6c72231d025","datavalue":{"value":{"entity-type":"item","numeric-id":4487461,"id":"Q4487461"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2900955e4e2b011c5e6e8758cbb9182ae34fc39a","datavalue":{"value":{"amount":"+0.8121821284294128","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":"Q1209724$7FE3B21F-F0EE-4046-8537-0035ED540506","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Principal common divisors of graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Principal_common_divisors_of_graphs"}}}}}