{"entities":{"Q2198396":{"pageid":2209139,"ns":120,"title":"Item:Q2198396","lastrevid":82593629,"modified":"2026-05-06T21:16:50Z","type":"item","id":"Q2198396","labels":{"en":{"language":"en","value":"Vertex-edge domination in cubic graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7245957"}},"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":"Q2198396$FB627240-B1D6-4006-AA18-04151FC01283","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b929b61b08d8447dcf2f01e2a267c8155d6416fc","datavalue":{"value":{"text":"Vertex-edge domination in cubic graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2198396$294984E6-C362-4849-BA2A-1DCEE911E1FA","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"a454043183c86c7c6a96d65ce50438d313a1ef8d","datavalue":{"value":"1447.05164","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2198396$3BEE8C96-B46B-43D7-94D2-198A19EB3341","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ca01a4a359db517d0f07a68cebf216f21a216a03","datavalue":{"value":{"entity-type":"item","numeric-id":2198395,"id":"Q2198395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2198396$18CB31B9-6D68-49A4-8295-5BF270C28284","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d221c2533b1e1d53fbe7fc300d9711cfabbfd439","datavalue":{"value":{"entity-type":"item","numeric-id":819179,"id":"Q819179"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2198396$1FBC7B3E-D7A5-438E-AA8F-09088EED3AF4","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":"Q2198396$85780812-1B2B-46FF-90AC-E007B62398DF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"14a2bae8a6c91ebe59b7dcfd879b8f74b6b05d76","datavalue":{"value":{"time":"+2020-09-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2198396$946A359B-8DA4-4DE1-93A2-1C1C351F93DA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2ebeb3cb09cff4c34bab351e5abfb92e72437a5e","datavalue":{"value":"Let \\( G = (V, E)\\) be a connected graph. A vertex \\(u \\in V\\) is said to \\(ve\\)-dominate an edge \\(xy \\in E\\) if (1) \\(u = x\\) or \\(u = y\\), or (2) \\(ux\\) or \\(uy\\) is an edge in \\(G\\). A set \\(D \\subseteq V\\) is said to be a \\(ve\\)-dominating set of \\(G \\) if, for every edge \\(e \\in E\\), there exists a vertex \\(u \\in D\\) such that \\(u\\) \\(ve\\)-dominates \\(e\\). The vertex-edge domination number of \\(G\\), denoted by \\(\\gamma_{ve}(G)\\), is the minimum cardinality of a vertex-edge dominating set of \\(G\\), whereas the \\(\\gamma_{ve}\\) ratio \\(\\rho_{ve}(G)\\) is defined as \\(\\rho_{ve}(G) = \\gamma_{ve}(G)/|V|\\). The main result of this paper is the following theorem: If \\(G\\) is a connected cubic graph of order greater than six, then \\(\\rho_{ve}(G) \\leq \\frac{10}{31}\\), thus affirmatively answering the open question posed by \\textit{W. F. Klostermeyer}, \\textit{M.-E. Messinger} and \\textit{A. Yeo} [``Dominating vertex covers: the vertex-edge domination problem'', Discuss. Math. Graph Theory (to appear)]. On the other hand, the authors present an infinite family of cubic graphs whose \\(\\gamma_{ve}\\) ratio is equal to \\(\\frac{2}{7}\\) and propose the conjecture that asserts that for any cubic graph \\(G\\) of order \\(n > 10\\), we have \\(\\rho_{ve}(G) \\leq 2/7\\).  Finally, they show that the problem of determining the minimum \\(\\gamma_{ve}\\)-dominating set is NP-hard even in cubic planar graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2198396$2325EDCA-D2AE-478F-A284-76DEF744D55B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2198396$35298BEA-28AF-440B-90CA-F77E2D12AE7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"36d142e7ea03446b1d7deb9627eedb9f0297f86a","datavalue":{"value":"90C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2198396$7EB7E6F9-C5E2-4842-86A6-CA782D7BC9B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2198396$2BC47377-F0DC-43E7-8A76-F07478AC2213","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b2a595795653f3612b9d0ecd3a28c6648a876892","datavalue":{"value":"7245957","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2198396$650304F0-D1BA-42FB-86B5-812D77BAA066","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8181ab4201f05ca2942b778d800c0abf078ecd9c","datavalue":{"value":"vertex-edge domination","type":"string"},"datatype":"string"},"type":"statement","id":"Q2198396$40A13D17-AE4C-4428-B15A-659C708E9AAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e01f33e43354d516b8d6e654c1ded76a55047726","datavalue":{"value":"cubic graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2198396$A869EB19-64CA-4A28-AEA1-C9A9C3CF25E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e249ba6e5b3904c8883287728fdf3dc6af0ca4b0","datavalue":{"value":"discharging method","type":"string"},"datatype":"string"},"type":"statement","id":"Q2198396$C6CEAA12-F05A-4896-AE8A-BE3900EA1E8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a08efa1a08a750d06fca0196004a17a02a35c592","datavalue":{"value":"linear programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q2198396$2D82E68D-5845-4A22-AC29-502AFE7551C7","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"af6f91027425e6a3e182e3068da26575ef8e093e","datavalue":{"value":{"entity-type":"item","numeric-id":190560,"id":"Q190560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2198396$D33EE039-3592-4BFB-BFA2-D4B2822B0330","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":"Q2198396$57DB39B7-AD43-47C8-A6A9-9E7562136871","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"cf3d346a96b2e2763f52c34a7421980ec4013f37","datavalue":{"value":"https://doi.org/10.1016/j.disc.2020.112075","type":"string"},"datatype":"url"},"type":"statement","id":"Q2198396$A3C38ADB-DDEE-4DA7-BF9D-C43AF335F3D8","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"d601b17ebd2f704aed3a065130b957448f4c8cd8","datavalue":{"value":"W3046755290","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2198396$8FF5EBF3-0464-44D6-8B78-42F5DD10B938","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"5e1ac8848060c1dd457eddf94285a2be85aa1fb6","datavalue":{"value":{"entity-type":"item","numeric-id":5028563,"id":"Q5028563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2198396$9F8BE07F-4CBA-445D-BA8D-B634A0540D37","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f347e55d3fa3055019b90e6506b2ace0e55d5242","datavalue":{"value":{"entity-type":"item","numeric-id":5890654,"id":"Q5890654"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2198396$11FE28A0-CE8D-42B0-8BFC-A66D713D687F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3e094d95264a1123369a24875b3e4cd95b2d51bc","datavalue":{"value":{"entity-type":"item","numeric-id":2374155,"id":"Q2374155"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2198396$1C7E5B11-B398-456A-B046-F1B9934D6410","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f132e7d44c01d1150b7b2b55d6150334b7e394fa","datavalue":{"value":{"entity-type":"item","numeric-id":1751226,"id":"Q1751226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2198396$1585A9FC-509D-4451-852C-D313AEDA9513","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2173c1bdbb6877c399f54439e0d90f8083098a32","datavalue":{"value":{"entity-type":"item","numeric-id":2911155,"id":"Q2911155"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2198396$EEF344EB-EA35-4FE3-B2F9-AE043C74306B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6db8bab2b6b4db51137d491f1da9280274410f7a","datavalue":{"value":{"entity-type":"item","numeric-id":3745303,"id":"Q3745303"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2198396$3C20A4AB-B687-41F2-83BA-23236B18B14F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3ecac98bcfd5b0d06ddeb059fceb4e293cd8c17c","datavalue":{"value":{"entity-type":"item","numeric-id":1815329,"id":"Q1815329"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2198396$1931EB4A-9071-489F-9F5F-020698DBE161","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2198396$C7D08AE2-7172-4129-A5BC-D0209389BF9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d1416759272452f4ab56cbfb11878c98f6de8dcd","datavalue":{"value":{"entity-type":"item","numeric-id":5375889,"id":"Q5375889"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2198396$FDCE2E4A-509B-49D1-A5EE-716EAB70D52A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4406b1c597d6e383b35a97ad3352bf8994d9b1d6","datavalue":{"value":{"entity-type":"item","numeric-id":5896105,"id":"Q5896105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2198396$BB6B6BFC-7FA7-49FC-B964-A9E77AD6459E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7ae06ace3264ebdef666fd198a2d1441400a748e","datavalue":{"value":{"entity-type":"item","numeric-id":4087195,"id":"Q4087195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2198396$50780E38-534C-4F43-9B2D-F4A015021EB9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aa5f3be695a5cafe3863e880bf175864b278902d","datavalue":{"value":{"entity-type":"item","numeric-id":2214311,"id":"Q2214311"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2198396$99F250C5-5B21-451F-B899-CE29F38D9F8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b72031c87880fd9e80d387b770418cadd65a0cb1","datavalue":{"value":{"entity-type":"item","numeric-id":5370818,"id":"Q5370818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2198396$DED3CB85-0CD4-4616-9106-540AA895EAA1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"453fe5dfd80810b7888fc7d2d9f26c23d8fe3957","datavalue":{"value":{"entity-type":"item","numeric-id":4582808,"id":"Q4582808"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2198396$516100DC-EA48-4E80-B2CE-7E1579165C1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bfa741a5e98ed2fab8127cf960507657abd39efb","datavalue":{"value":{"entity-type":"item","numeric-id":2450268,"id":"Q2450268"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2198396$F2D0AB93-873A-4748-9047-C0E3CB5B7989","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b1a2257c06c04bdb376f024ccfcadeceda72ca9","datavalue":{"value":{"entity-type":"item","numeric-id":3059032,"id":"Q3059032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2198396$B1F45174-1668-429D-B8E9-7195677AFBA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e0f51b2d9c5d5e420898ae0470aedfc8082a1e1d","datavalue":{"value":{"entity-type":"item","numeric-id":2180173,"id":"Q2180173"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2198396$EF3D02A8-DBEA-4919-AC83-C2B10D79CF89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"82afc41d8df1a0aa680504efdf81102475719492","datavalue":{"value":{"entity-type":"item","numeric-id":3466051,"id":"Q3466051"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2198396$21450B87-48DC-4E88-9AF6-9C2B47EAF99D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"70b37eec13539e2aee44e8b9d659721e94f01882","datavalue":{"value":{"entity-type":"item","numeric-id":5236167,"id":"Q5236167"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2198396$C6A4ADDF-A1F4-4323-8B2F-E03879CC7440","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b5136c8f74226fc91e6d02c556e863a259321ea","datavalue":{"value":{"entity-type":"item","numeric-id":5919557,"id":"Q5919557"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2198396$88F51577-FDBB-4E0F-B919-60ABC8E791A9","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7e01bb8a774c404e37fd94a0b0d733623f1317fb","datavalue":{"value":"10.1016/J.DISC.2020.112075","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2198396$DD4ABC46-2E02-400F-9FEE-8DABE7130235","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"30ac0fb5e81bdde4b436908794d8b670ea4d69d8","datavalue":{"value":{"entity-type":"item","numeric-id":2214311,"id":"Q2214311"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a94f8cc8234c846a37ac2a751c742a20d4605da6","datavalue":{"value":{"amount":"+0.8608171939849854","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":"Q2198396$A185DADB-9BFB-4530-BD08-91230EE67D71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"488a2b3b7860dd7cd450a96e3b5d156fb96ce4fe","datavalue":{"value":{"entity-type":"item","numeric-id":2454559,"id":"Q2454559"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2abcad476232176dfb62163917db00896dd25c02","datavalue":{"value":{"amount":"+0.8543130159378052","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":"Q2198396$11AF103D-E275-4658-85E9-346A6B9B5612","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"294765bfdfd48e47ef80aabc019db65695c36a8a","datavalue":{"value":{"entity-type":"item","numeric-id":5919557,"id":"Q5919557"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"31ffcdb1ec240fefc3265deb68ce369bda55fd19","datavalue":{"value":{"amount":"+0.8541098833084106","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":"Q2198396$7968BB18-6A5D-4249-B0AD-FD3CB48CBAA6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c3aedd6d1d11f1a7ba447596d9b4d26247540093","datavalue":{"value":{"entity-type":"item","numeric-id":385388,"id":"Q385388"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eb1b5c9c7be17c0aa44a021f8633c27caebc6d85","datavalue":{"value":{"amount":"+0.8083598017692566","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":"Q2198396$C0FB6B0B-E37F-4245-BC19-DE80A4AF7927","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a58fb6101d1ab9163c463da09f9805ab36a4a8c2","datavalue":{"value":{"entity-type":"item","numeric-id":1010698,"id":"Q1010698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"49a398bc1b1aaacdba8c9c1a808d4cb0af3e8241","datavalue":{"value":{"amount":"+0.8052487373352051","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":"Q2198396$7899A38C-D0E4-4F41-8207-B72A054C0669","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Vertex-edge domination in cubic graphs","badges":[]}}}}}