{"entities":{"Q490315":{"pageid":492082,"ns":120,"title":"Item:Q490315","lastrevid":62228913,"modified":"2026-04-11T04:39:30Z","type":"item","id":"Q490315","labels":{"en":{"language":"en","value":"Spanning \\(k\\)-trees of bipartite graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6389252"}},"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":"Q490315$2A8AF1E6-D285-4D68-B0FF-950569F62113","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5e0b2eedd1fb69f0d881d3515f36646687cbfe96","datavalue":{"value":{"text":"Spanning \\(k\\)-trees of bipartite graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q490315$E68ED2C8-4E5D-4648-B51B-D0FB01A28385","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9928f9109271d5916edae7c50b1f89eaae514da4","datavalue":{"value":"1305.05046","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q490315$5A9AF002-FFA4-41EC-A80B-910147DBAA9D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0b1df5ec0b87d059bcff732d9b389d241c0e4565","datavalue":{"value":{"entity-type":"item","numeric-id":394289,"id":"Q394289"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490315$1B0BD4BA-DE3E-4ADC-9157-0DC3B084BE32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b78f9720ea264c3832962caf90aa89d1a97d8d60","datavalue":{"value":{"entity-type":"item","numeric-id":307915,"id":"Q307915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490315$6A775FF8-32E7-4800-A073-7754305B6057","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"12c34ce50999eac286d9f7758d569d1a0dcfee21","datavalue":{"value":{"entity-type":"item","numeric-id":490314,"id":"Q490314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490315$08617CBF-E773-40F7-A7E2-2A61833071D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ac3eaf725b03bdf267f3a5e53785394319514212","datavalue":{"value":{"entity-type":"item","numeric-id":394290,"id":"Q394290"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490315$D35DB9B1-58E7-49A3-A3E5-5C1D9026203B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e4d6687f01af260f9b3f6f64a1cf5034ac1acdd3","datavalue":{"value":{"entity-type":"item","numeric-id":354451,"id":"Q354451"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490315$B7F65D35-A64C-4984-BB01-E1FCF92873E2","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":"Q490315$40DB2A84-59C8-4B6A-9CB8-048C590281AE","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8bb6c16b18fb3fcb7c20a96f2fcd94ae71f0f929","datavalue":{"value":{"time":"+2015-01-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q490315$661ECD80-1113-4C4C-9777-FCEB7AF33617","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"181ddddaa32e00238741e19d63d57ba59eb7382f","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p13","type":"string"},"datatype":"url"},"type":"statement","id":"Q490315$E7A758C5-4331-4F82-B623-C50C1C0F00A2","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4716ce9a6aa156fc551c7c6a943f88328ee3ae3c","datavalue":{"value":"Summary: A tree is called a \\(k\\)-tree if its maximum degree is at most \\(k\\). We prove the following theorem. Let \\(k \\geq 2\\) be an integer, and \\(G\\) be a connected bipartite graph with bipartition \\((A,B)\\) such that \\(|A| \\leq |B| \\leq (k-1)|A|+1\\). If \\(\\sigma_k(G) \\geq |B|\\), then \\(G\\) has a spanning \\(k\\)-tree, where \\(\\sigma_k(G)\\) denotes the minimum degree sum of \\(k\\) independent vertices of \\(G\\). Moreover, the condition on \\(\\sigma_k(G)\\) is sharp. It was shown by \\textit{S. Win} [Abh. Math. Semin. Univ. Hamb. 43, 263--267 (1975; Zbl 0309.05122)] that if a connected graph \\(H\\) satisfies \\(\\sigma_k(H) \\geq |H|-1\\), then \\(H\\) has a spanning \\(k\\)-tree. Thus our theorem shows that the condition becomes much weaker if the graph is bipartite.","type":"string"},"datatype":"string"},"type":"statement","id":"Q490315$F36A36A2-29AE-4577-8E15-4BF92E08A441","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q490315$CDA80129-7B3A-41F2-B299-FC178B6E2447","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q490315$3CE52FF3-F2E7-4046-BE45-C57CD285F9DC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"88488e6b5b99f5d81b1032ac5cca90ce232c9ab6","datavalue":{"value":"6389252","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q490315$4BCB7548-9710-4366-A845-41BDCCF435C3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"849b7a0d6519fee636943d9bde0b8b557d98cf60","datavalue":{"value":"spanning tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q490315$ABBF3E59-6C13-4F75-B277-A2FC4FFC346E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"782819e011e21f22292fe92b3b32a4882196abfd","datavalue":{"value":"spanning \\(k\\)-tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q490315$5FEF0B7E-767A-491E-AEAC-D3E19E74DA4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3187e84c5efaed03d0bd9515713a70084404d3ee","datavalue":{"value":"bipartite graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q490315$43C3B6B8-3AD0-44E0-8513-814355B323F1","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":"Q490315$4862B7ED-E1C9-49A8-99A6-684F26F6AD08","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"24d08bc2309a916fa5b15e17e5aaa34154a3fe61","datavalue":{"value":{"entity-type":"item","numeric-id":547467,"id":"Q547467"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490315$A029C018-6317-415F-B9E9-ED6FD76818F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"37d15f98286548277f2f64df3f6cd689148c81e8","datavalue":{"value":{"entity-type":"item","numeric-id":5947942,"id":"Q5947942"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490315$1F42AD06-67CA-49F4-BDB4-B82C9ED3CC33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f94de69bd7c61bb3f77e8b25dd552f3d5e062bb9","datavalue":{"value":{"entity-type":"item","numeric-id":855299,"id":"Q855299"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490315$103D823F-9F17-479D-AB94-47E991760606","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"437ebe0c1320329dc48bb92b41d79db15821185e","datavalue":{"value":{"entity-type":"item","numeric-id":2626464,"id":"Q2626464"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490315$C0B0395C-D393-49B6-8C25-AA703BA9CA06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e836b22d53774a03249bcabc4b9cbfe8282ea24e","datavalue":{"value":{"entity-type":"item","numeric-id":1180410,"id":"Q1180410"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490315$1A0CF61A-075F-409E-9C19-CA8BDD37EE5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5e2b1427e629c27b08cdd0e2190d37376022c9d1","datavalue":{"value":{"entity-type":"item","numeric-id":659663,"id":"Q659663"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490315$E0CDBA39-BC9D-46A2-9D47-550F9A14B028","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f03319600f58d68a4061eb2036b5a315d81fa798","datavalue":{"value":{"entity-type":"item","numeric-id":1218870,"id":"Q1218870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q490315$AF60F464-F88B-4F21-ADA2-B02B3475E67B","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"904d1e50478e884cd326a0004d10df53cf2c374f","datavalue":{"value":"bafkreigg45apjg47tmgpfov2mcsdqvnbcba4yugiqyacab6q3mfdn6bdcq","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q490315$44B032F4-5F76-4668-AA8F-B34888B9BC92","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"86d0c61183d1fb80f33abe1cf4aeaaa70f0f6bfc","datavalue":{"value":{"entity-type":"item","numeric-id":394291,"id":"Q394291"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"27a7b2ad320b3ee2eac7bf93ac6dc80e6d178a07","datavalue":{"value":{"amount":"+0.9067198038101196","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":"Q490315$8A7333F6-AEF1-40DC-BB85-5372901A1CB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b5c44e565f7dcae6f0e6fe3756b5c77a842e52ce","datavalue":{"value":{"entity-type":"item","numeric-id":2259579,"id":"Q2259579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"80dfdcf9ff28e6d264461787051897151b70a043","datavalue":{"value":{"amount":"+0.857358992099762","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":"Q490315$45841E74-70C3-43CC-85D1-7221058A6AD5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cd5284f2088d84495fa3c0f8cf47bfa8b938a8c1","datavalue":{"value":{"entity-type":"item","numeric-id":2300534,"id":"Q2300534"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"556bd2030057fb23624014a36a90fb8cdcfe97d9","datavalue":{"value":{"amount":"+0.8444923758506775","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":"Q490315$EA8915DB-D9E9-492C-8975-2DAFDC9BB720","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0157b9dd1e1a1e028ce6ea521846d4d65c3aec8d","datavalue":{"value":{"entity-type":"item","numeric-id":6057654,"id":"Q6057654"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"82d18437fdd8f201c34ebc00dfc92a29d8522db7","datavalue":{"value":{"amount":"+0.840732991695404","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":"Q490315$BB1BA761-6969-4A43-BB37-C7F6754AE994","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b20e61a520a9fcfc3f65137c74af9db613f3be5d","datavalue":{"value":{"entity-type":"item","numeric-id":659713,"id":"Q659713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bd8c1d8a0e0a7cc9a21423156b75ad6599d80710","datavalue":{"value":{"amount":"+0.8393939733505249","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":"Q490315$544F07FC-205E-4C01-B700-31CAAEFBB1A2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Spanning \\(k\\)-trees of bipartite graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Spanning_%5C(k%5C)-trees_of_bipartite_graphs"}}}}}