{"entities":{"Q1174141":{"pageid":1184890,"ns":120,"title":"Item:Q1174141","lastrevid":66756378,"modified":"2026-04-12T12:39:43Z","type":"item","id":"Q1174141","labels":{"en":{"language":"en","value":"Maximum number of edges in connected graphs with a given domination number"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 8154"}},"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":"Q1174141$DBF15FED-318D-4CFC-967A-5ACC7F0689DE","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"82fe2d86cc87148b7b7437289d1f9e805574a25f","datavalue":{"value":{"text":"Maximum number of edges in connected graphs with a given domination number","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1174141$629988A3-6222-491B-B822-7933936AF630","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"4aea0075a33e19dca4026181e3647303a0de3207","datavalue":{"value":"0739.05050","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1174141$DA2E859E-9CE5-48BB-B796-983A1CE9384C","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"5988ed366e1399bb46827ab8eaf6f7b950916f96","datavalue":{"value":"10.1016/0012-365X(91)90071-9","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1174141$CE72D104-9A82-40A9-B680-6F9344D2A981","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"b09bb5809f22b0c7500a2ef34c355902663eb05e","datavalue":{"value":{"entity-type":"item","numeric-id":241138,"id":"Q241138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174141$A22CD17B-3B95-4579-9EA7-C0D2ECB595E7","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":"Q1174141$386678F5-74D4-450C-B080-1B389313C2FF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d3f790682a6be4cc1f3210e15eebe1d6cc5ffbc2","datavalue":{"value":{"time":"+1992-06-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1174141$152D85C3-131E-4762-84E5-02F67C9BF96F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"776b24cf170ac54fd027c5b5b46321fa754bbf71","datavalue":{"value":"A dominating set in a graph is a subset \\(U\\) of its vertices such that each vertex not in \\(U\\) has a neighbour in \\(U\\). The domination number is the minimum size of a dominating set. The paper under review shows that a graph with \\(n\\) vertices, domination number \\(d\\) (where \\(3\\leq d\\leq n/2)\\) and no isolated vertices has at most \\(n-d+1\\choose 2\\) edges. The graphs for which this bound is tight are also characterized. The proof is based on work of \\textit{Y. Usami} [``Minimum number of edges in graphs that are both \\(P_ 2\\)- and \\(P_ i\\)-connected'', Discrete Math. 44, 195-199 (1983; Zbl 0503.05038)].   The corresponding bound and related characterization for graphs with isolated vertices is due to Vizing.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1174141$78B6A043-9A33-4A29-802C-9BCBEA62C291","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1174141$473A05C8-0B22-4012-8E0C-092642FA3B65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e35cfda1c439de499de525a8a9009114d934bb37","datavalue":{"value":"05C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1174141$6B60B92F-F4AB-462A-8934-629D336F7C53","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"02dc15e062cc3066c3320cc15919af0dc73a42e1","datavalue":{"value":"8154","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1174141$FB304A3E-4379-45C1-B382-A6644D62DB42","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":"Q1174141$B854E7C3-6232-4D95-978A-8471A5658367","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"682d6c7552197299d8caef727039a36b74670a49","datavalue":{"value":{"entity-type":"item","numeric-id":585222,"id":"Q585222"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174141$0A2D3451-4B33-4D68-9137-8D4D88A01898","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"09b06ada4a02303c79d7ffc00581d47956a243d6","datavalue":{"value":{"entity-type":"item","numeric-id":4099676,"id":"Q4099676"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174141$25467220-8728-4B2E-9DF4-02F8CA769615","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b56aa07beffcf5cd4668ceb40b044197d8e5f8b9","datavalue":{"value":{"entity-type":"item","numeric-id":4163261,"id":"Q4163261"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174141$CD234588-ADE1-4C8B-9540-E9D14930D120","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f88392e2d96e6b20b42940bf56c1735eaf4e5420","datavalue":{"value":{"entity-type":"item","numeric-id":3291034,"id":"Q3291034"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174141$738D9026-56CB-4DFB-9E88-5467D38F491E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee4cac13ed2587d1edaf32d5c0bd2d1e04e46a93","datavalue":{"value":{"entity-type":"item","numeric-id":5917319,"id":"Q5917319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174141$2DF77255-EC7D-4869-97A0-266CF2594BF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7fa653f42fc9e487f8be8727f1586b156b5dd1f1","datavalue":{"value":{"entity-type":"item","numeric-id":1173099,"id":"Q1173099"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174141$0A847779-63C8-4D11-9EE1-48D1E1C7AAD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a40cbd364246837cca1f46b9b232da08f2ebb898","datavalue":{"value":{"entity-type":"item","numeric-id":5509541,"id":"Q5509541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1174141$BFFB47B5-0A01-4D29-A61B-A2A3371B6A06","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"447cf340b2cd6ade3a18c2da2a23badf4eb60c5a","datavalue":{"value":"https://doi.org/10.1016/0012-365x(91)90071-9","type":"string"},"datatype":"url"},"type":"statement","id":"Q1174141$7F54743C-D9B1-41D2-99EA-2724560B579F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"69401e07303700d5442e1cd24e5bd6d3a4782bae","datavalue":{"value":"W2069267595","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1174141$57BAE38B-3529-4DDD-BEDF-CAF91ED695F5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2193cdd7a600af2865ef1d1a2177235f7056697a","datavalue":{"value":{"entity-type":"item","numeric-id":1972141,"id":"Q1972141"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"490dee96918ee7768ce8bce0b4c09d6e12577cea","datavalue":{"value":{"amount":"+0.8645553588867188","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":"Q1174141$6527D7FD-36F2-48B2-B138-6867157C8BDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bce4d4a5d2d05f564effeb803d08d51751688ae7","datavalue":{"value":{"entity-type":"item","numeric-id":1893172,"id":"Q1893172"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0e79468bb299e8005d9f48d18ab9b53221b2e710","datavalue":{"value":{"amount":"+0.8628777265548706","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":"Q1174141$D0013039-A4A2-416C-847C-11FF060938A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cfbad91d2d039ab9a9ee5fe4ff2b13b9954310e1","datavalue":{"value":{"entity-type":"item","numeric-id":4871064,"id":"Q4871064"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"902c869e76d507f6c8386026179e14326a13c03f","datavalue":{"value":{"amount":"+0.8271673321723938","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":"Q1174141$E070EE2C-5D27-4E1E-ACD8-9BFA24C68C41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2d3686b760e6c0e53c28e8b5570e3fa8d0970222","datavalue":{"value":{"entity-type":"item","numeric-id":1827789,"id":"Q1827789"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e6cc196d2486a698cbba5efa4bf33fd8b496d14d","datavalue":{"value":{"amount":"+0.799126923084259","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":"Q1174141$3A8BBE3F-BAA6-4787-BB31-EFA033B35038","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Maximum number of edges in connected graphs with a given domination number","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Maximum_number_of_edges_in_connected_graphs_with_a_given_domination_number"}}}}}