{"entities":{"Q1972141":{"pageid":1982883,"ns":120,"title":"Item:Q1972141","lastrevid":47470780,"modified":"2026-01-01T20:15:06Z","type":"item","id":"Q1972141","labels":{"en":{"language":"en","value":"On the number of edges in graphs with a given connected domination number"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1423741"}},"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":"Q1972141$95CABA02-610F-4B7F-B27D-08723AAF06B2","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5ec819a7c7c8c0212a20364e30ea149c1a916005","datavalue":{"value":{"text":"On the number of edges in graphs with a given connected domination number","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1972141$F6431F6C-0371-443E-9DC5-D486CCA7EA19","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"944aa02e693f8e71e94ff44978a1d0c0065412db","datavalue":{"value":"0945.05046","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1972141$942A278E-9CFC-4EE6-A947-4B0AC7C5044A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"36026a987f083b7fd8a50fd5f710ab85adfc3f79","datavalue":{"value":"10.1016/S0012-365X(99)00143-0","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1972141$6EFC506B-20FA-4DE1-B814-24AAEFA64891","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":"Q1972141$4DF99B78-6628-4392-A09C-A8347D59657B","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":"Q1972141$D4D2E4D9-B8B1-41AD-9381-8180FC716B03","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a21e07de487f67db9a06dfe5a09ead0ebef66850","datavalue":{"value":{"time":"+2000-09-27T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1972141$3D63AFD2-EEDB-4E62-BA52-321C569C435C","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b9c36edd6065e0294a04e71efbcacc1f31596471","datavalue":{"value":"The paper is devoted to the problem of finding the maximum number of edges in a graph with given connected domination number. A connected dominating set \\(V\\) of a graph \\(G\\) is a set of vertices that is dominating and the graph induced by \\(V\\) is connected. The connected domination number of \\(G\\) is the size of its smallest connected dominating set. The main result of the paper is a characterization of graphs with given connected domination number. It is proved that for a connected graph \\(G\\) with \\(n\\) vertices and connected domination number \\(d\\) the number of edges in \\(G\\) is at most \\(\\binom{n-d+1} {2}+(d-1)\\). Moreover extremal graphs achieving this bound are characterized.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1972141$39F349FE-5705-4F94-8C8A-C5ED73DED2C3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1972141$504D6970-0531-422B-A002-B6CAE2F72038","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1972141$BF9952C2-39DA-4241-8507-2F04964E73E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1972141$EFF7E7C0-B595-4F9B-9466-7779147DFADC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4f0c08b3748f05d7c9a4dbb26906ba25cd5c1aa2","datavalue":{"value":"1423741","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1972141$456A835B-E37D-4DAB-B771-5F13E0D1BC5B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"210f6e878bc06e635be406e25541c4c590749f5e","datavalue":{"value":"dominating set","type":"string"},"datatype":"string"},"type":"statement","id":"Q1972141$E27C6645-55FE-40F7-9F35-2526C09A99D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3267d14ab3c644208190b057ee58cacbeb7fa5c7","datavalue":{"value":"domination number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1972141$7F8AD9C0-7245-495F-972F-C1A9E1EAAA8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"924979e39df53c43e61bddb3e36d2617afacd37b","datavalue":{"value":"connected domination number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1972141$372937E7-1CD4-4A8E-BE2B-BFD47F11A3A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c89639778a113cbe54a2efcba7f98ccd79f62275","datavalue":{"value":"characterization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1972141$64599191-F213-4516-BA2E-2AF6E4FD8C62","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9bdefd4725d91bba1e0d0861018fdd0e81ad28b3","datavalue":{"value":"extremal graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1972141$C7A9E669-E3AA-4052-9470-DC6D78167609","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"15fb7789dd0d1691819f44cebdb975938d5b89dc","datavalue":{"value":{"entity-type":"item","numeric-id":967347,"id":"Q967347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1972141$F0494289-E6BA-488A-8D91-35F6FD5DA477","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":"Q1972141$89D407B0-E888-45DD-B0B7-5E3E5DB232CE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e5c62d999f3f81474b0f5d7b8729a08969ebd14c","datavalue":{"value":"https://doi.org/10.1016/s0012-365x(99)00143-0","type":"string"},"datatype":"url"},"type":"statement","id":"Q1972141$785DD4E6-F06B-4D78-8233-3F30D1CD0D2A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e8476ebad369bfac271932f9a4c2003ebb3313bf","datavalue":{"value":"W2012003157","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1972141$1F7EFFC1-D99F-4538-BB62-87948AEEDA7F","rank":"normal"}],"P1643":[{"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":"ee745f13ed4abc837dbe08b48b129c9e5e3c077d","datavalue":{"value":{"amount":"+0.874191164970398","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":"Q1972141$D114A2FE-FABB-40AF-9499-A6666114770C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6c71694f0d4da7add6ec4f60d4810515e656b453","datavalue":{"value":{"entity-type":"item","numeric-id":1174141,"id":"Q1174141"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"90512b8194a0a8d9f7158efdcdd5eba6ce292690","datavalue":{"value":{"amount":"+0.8678848147392273","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":"Q1972141$36AAC6A2-B621-4C78-8FC0-1EAFDA5B38FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c17c046a878314229bec538c0b79564483009fdf","datavalue":{"value":{"entity-type":"item","numeric-id":5322234,"id":"Q5322234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d217ae806383df1fdf5d8ee4fd65593c0d00d0bd","datavalue":{"value":{"amount":"+0.8672130107879639","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":"Q1972141$E469E2E2-F2C2-4C9C-B32B-999DEB73622A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6ccb4ade69124c3f8182e2c98b4f14d3c6cef8c2","datavalue":{"value":{"entity-type":"item","numeric-id":3340900,"id":"Q3340900"},"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":"Q1972141$86B41A02-2905-4BF2-ADFD-92FC549F43FB","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":"b4f94ff231391dd115ebd00a681bd6d3f4752015","datavalue":{"value":{"amount":"+0.8529541492462158","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":"Q1972141$0A37597D-81D8-44B7-A0F6-0AAB974E19C4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1972141","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1972141"}}}}}