{"entities":{"Q2037578":{"pageid":2048320,"ns":120,"title":"Item:Q2037578","lastrevid":73987212,"modified":"2026-04-14T17:57:39Z","type":"item","id":"Q2037578","labels":{"en":{"language":"en","value":"Tightness of domination inequalities for direct product graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7369634"}},"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":"Q2037578$0C1A34E9-9DE1-4229-A3AE-E332DFABCE8E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"63171a3a69d67afe9d58f7dca9dae7e51df59d1d","datavalue":{"value":{"text":"Tightness of domination inequalities for direct product graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2037578$84B9D1DB-CB5A-4E4D-9802-F86551F6C15F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"71992e7c2d8eba9a64bc80e63a7aa04b56bbe996","datavalue":{"value":"1473.05219","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2037578$643DBD3C-7B6D-404B-BB43-2E7602010E29","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"495926db2f7a1bc1d144f16cc0e8faafd48fc996","datavalue":{"value":{"entity-type":"item","numeric-id":1630892,"id":"Q1630892"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2037578$28B4AD4C-7CE8-4676-8F32-44F13DE5A759","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":"Q2037578$8287CF15-DB25-47FA-9DDF-4CEDC6C7C81E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3a1926b5e5d0313a397a856b5060f2ee4412bba3","datavalue":{"value":{"time":"+2021-07-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2037578$5AACD7D5-C46D-47DE-A5D1-CC3432E6039E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9e1c7391b9d751a50782a2dd0223164cfd9e21ff","datavalue":{"value":"https://arxiv.org/abs/2008.03887","type":"string"},"datatype":"url"},"type":"statement","id":"Q2037578$2857C92B-CB49-49EE-9427-D0EF607A1C31","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8edd37cab8a50c611e68cbb4dc7226268479612f","datavalue":{"value":"Let \\(G = (V (G), E(G))\\) and \\(H = (V (H), E(H))\\) be graphs with no isolated vertices. The direct product (or tensor product) of \\(G\\) and \\(H\\), denoted by \\(G \\times H\\), is the graph on \\(V (G) \\times V (H)\\) where vertices \\((u_G, u_H)\\) and \\((v_G , v_H)\\) are adjacent if and only if \\(\\{u_G, v_G\\} \\in E(G)\\) and \\(\\{u_H , v_H\\} \\in E(H)\\). The Cartesian product of two graphs \\(G\\) and \\(H\\), denoted by \\(G \\square H\\), is the graph on vertex set \\(V (G) \\times V (H)\\) with vertex \\((u_G, u_H)\\) adjacent to \\((v_G , v_H)\\) if and only if either \\(u_G = v_G\\) and \\(\\{u_H , v_H\\}\\in E(H)\\), or \\(\\{u_G, v_G\\}\\in E(G)\\) and \\(u_H = v_H\\).\\\\ The domination number \\(\\gamma (G)\\) is the minimum size of a dominating set in \\(G\\). The paired domination number \\(\\gamma_{pr} (G)\\) of \\(G\\) is the minimum size of a dominating set whose induced subgraph admits a perfect matching. The upper domination number \\(\\Gamma(G)\\) of \\(G\\) is the maximum size of a minimal dominating set in \\(G\\).  In this paper, there are three main results as follows. \\begin{itemize} \\item[1.] For every \\(c > 0\\), there exists a connected graph \\(G\\) of arbitrarily large diameter such that \\(\\gamma (G\\times G) < c\\gamma (G)^2\\).  \\item[2.] For any graphs \\(G\\) and \\(H\\), there exist graphs \\(G^\\prime\\) and \\(H^\\prime\\) containing \\(G\\) and \\(H\\), respectively, as induced subgraphs such that \\(\\gamma_{pr}(G^\\prime\\times H^\\prime) \\ge \\frac{1}{2}\\gamma_{pr}(G^\\prime)\\gamma_{pr}(H^\\prime)\\).  \\item[3.] For  \\(n \\ge 71\\) and let \\(G_n = K_2 \\square K_n\\). Then \\(\\Gamma(G_n \\times Gn) =n^2 = \\Gamma(G_n)^2\\). \\end{itemize}","type":"string"},"datatype":"string"},"type":"statement","id":"Q2037578$EA351339-6A4E-4572-8E04-886EE57E0943","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"17b32c74d6d82a355c662d645083cf6134b85726","datavalue":{"value":{"entity-type":"item","numeric-id":263848,"id":"Q263848"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2037578$E8878A92-2550-4ABA-A0B7-4F68EA22B59B","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2037578$50885D41-1B0D-4AF9-BF53-FCCD06C757B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f54624d6184313158324a5b5a097f6e611a50ba5","datavalue":{"value":"05C76","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2037578$D0FFE586-BA65-4271-805B-A33967D356C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"74e7832a915a62c417a3bf8c026eff5989fd94d3","datavalue":{"value":"05C25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2037578$2C5D3D4B-DCC4-4C61-BE11-870C279B27D1","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c16ed981ce1804a2f6c535b395c3fe9326e4e682","datavalue":{"value":"7369634","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2037578$E3F4EA6E-34D0-4ED2-9AA8-309412B72B22","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a2b8dd46e8b890edd44eac53fddc8691f2fc07b","datavalue":{"value":"graph domination","type":"string"},"datatype":"string"},"type":"statement","id":"Q2037578$B9658435-3AE5-4824-AF57-43E8D3727784","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6ef55a18d71ae581ef91588da40ee03217dce4f6","datavalue":{"value":"paired domination","type":"string"},"datatype":"string"},"type":"statement","id":"Q2037578$5AA31D39-F713-426F-8899-8A49AC5424A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8cca2a6cd7acfc5303193a2642227df684f1e468","datavalue":{"value":"upper domination","type":"string"},"datatype":"string"},"type":"statement","id":"Q2037578$EAC477F7-A96E-4AB3-9090-3B526F3FBF0A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c0b2daaf7ac864516e7b1b0451bfe3e1040a3880","datavalue":{"value":"direct product","type":"string"},"datatype":"string"},"type":"statement","id":"Q2037578$53D175E9-6F04-4BC9-A5ED-65F72883BB40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"674fa4d2255a6b98d54010262df84b8a01adfed5","datavalue":{"value":"rook graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2037578$7B3DE794-ACAD-42FB-B489-10BC6083E00A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"364b9ae0145d813ee836e9a7b1a6258ae6c5ff1c","datavalue":{"value":"unitary Cayley graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2037578$6645A9C3-7FBB-4AD6-8FB9-E794D830BB31","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":"Q2037578$38F96DAA-C6D5-4CB8-A5CD-16C52346CB18","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"6421d0208a629c0f718d2d3ea424354af6437599","datavalue":{"value":"W3172564509","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2037578$84FFF868-4023-40C7-BC7D-9003E42D07BB","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"678082c5492ed7a4340024d6b81707c7f921705a","datavalue":{"value":{"entity-type":"item","numeric-id":2182213,"id":"Q2182213"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2037578$543E5249-5D6B-4923-AFBE-60556407A60B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6cc3d81911db378055a5c3fcf7bd588d49179451","datavalue":{"value":{"entity-type":"item","numeric-id":2571305,"id":"Q2571305"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2037578$989AB70D-4272-4BD5-98DA-982AEA39566E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"097f1c5a45e5b92d5b9229f9de7e454f9a679fef","datavalue":{"value":{"entity-type":"item","numeric-id":3113279,"id":"Q3113279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2037578$9F9899C3-4B5B-41E9-A58B-89964F17C4CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"95341b5cac2ad9ad3d1c121d9329ee849be3192c","datavalue":{"value":{"entity-type":"item","numeric-id":5442178,"id":"Q5442178"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2037578$19EAE906-708D-4D58-B01F-7631025120D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"26ae631d378e6c477aec5e4fbbcb234b0c660111","datavalue":{"value":{"entity-type":"item","numeric-id":879339,"id":"Q879339"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2037578$B020D639-0E53-4924-8E24-AE471BEBCE36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a5b25512a52177e6944c912c4ba74a3647beeee","datavalue":{"value":{"entity-type":"item","numeric-id":1660257,"id":"Q1660257"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2037578$83FEA941-47F8-4E84-9704-287EAB85A261","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d543e0e002ccb8d633dfbf8d6e835be577ec4d3a","datavalue":{"value":{"entity-type":"item","numeric-id":3005852,"id":"Q3005852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2037578$1E5F0817-50E7-4D6B-9F37-D67D6ED48D71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ad5cf18e72a0200cd3dbaf38ed690e1bf93b9d54","datavalue":{"value":{"entity-type":"item","numeric-id":4540077,"id":"Q4540077"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2037578$0800E0D4-B34D-440A-BB11-72D7D1E297A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"53147db84dbd97cf64fd607dd5242d62d26abbad","datavalue":{"value":{"entity-type":"item","numeric-id":1220937,"id":"Q1220937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2037578$4C2133A2-E9A7-43F7-ADEA-A31F56CA4148","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"253fca48b5a30e26738b3892f75e5a7575947b42","datavalue":{"value":{"entity-type":"item","numeric-id":712256,"id":"Q712256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2037578$873E04FC-BDC9-4A84-B3D1-325CCD91B844","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2efdd4ca6e0f14edc8cd51c150ddb2bc9fb23f8f","datavalue":{"value":{"entity-type":"item","numeric-id":2785650,"id":"Q2785650"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2037578$F6EEF80A-2180-41C4-86AE-8086B599B5A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f5099a843bf89b2e74946e0e268f2b72896a2165","datavalue":{"value":{"entity-type":"item","numeric-id":3012457,"id":"Q3012457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2037578$720E8245-CBD8-4701-86BD-9FA52FA32897","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cfdbf5fbb7aae49b978cd3e2c96c21a63c030dc4","datavalue":{"value":{"entity-type":"item","numeric-id":3615809,"id":"Q3615809"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2037578$719A8058-C492-468F-AFA4-6CA7DB469735","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"182fd795ca4aaa073a438602e0f2747fcebf1df0","datavalue":{"value":{"entity-type":"item","numeric-id":2197460,"id":"Q2197460"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2037578$8F2737E9-256F-490B-9292-39C05A58B351","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a100fba0ec62de6bee58d0048b8aad392be6aa66","datavalue":{"value":{"entity-type":"item","numeric-id":5587729,"id":"Q5587729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2037578$4CE8D7EF-D38E-43C1-ABDC-ED444D35D0AA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0fe1e0fa4af58ea47a0d5b2d147138573b10e71c","datavalue":{"value":"10.1016/J.DISC.2021.112495","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2037578$AF66B4F7-7536-4723-BE87-692B970FBB77","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"65be4dda46106c407a02555fa1c64d9c5a7af4a5","datavalue":{"value":{"entity-type":"item","numeric-id":879339,"id":"Q879339"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c228ba215e79dcead8aae4e15bd3347fad806ea1","datavalue":{"value":{"amount":"+0.894528329372406","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":"Q2037578$59AE4B56-6224-4D38-9B82-B05F720433F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1ef5af3b5811d7ea230fa18b546e7af933d63dd4","datavalue":{"value":{"entity-type":"item","numeric-id":712256,"id":"Q712256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"30dcd200d3d51896f8a712d9b7948b5d3dbf833e","datavalue":{"value":{"amount":"+0.8731889724731445","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":"Q2037578$78071B89-AC35-4DC4-B6CB-9280F3C4CF15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"557568fb631c149a1c008878ba9822909d196760","datavalue":{"value":{"entity-type":"item","numeric-id":5444066,"id":"Q5444066"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c68558a58c1aa5162bc4de19b84ee7ab7c0c855b","datavalue":{"value":{"amount":"+0.8521549105644226","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":"Q2037578$7E57369A-DE2F-43A8-8C2B-B90E08C3CC4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"34e73b1d2286fa43a28050296a8bf7d120007324","datavalue":{"value":{"entity-type":"item","numeric-id":1923517,"id":"Q1923517"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a11e56c8815ec6729e1322b34ad0ed08eb99803f","datavalue":{"value":{"amount":"+0.8477336764335632","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":"Q2037578$E41860F6-1B5F-45FF-BB63-32FF015D43B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"72a64c2dded699130208167fcd4d5c2648b887d3","datavalue":{"value":{"entity-type":"item","numeric-id":3012457,"id":"Q3012457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a11e56c8815ec6729e1322b34ad0ed08eb99803f","datavalue":{"value":{"amount":"+0.8477336764335632","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":"Q2037578$E3C3077C-CE40-44C3-9678-88D9C864ADA1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Tightness of domination inequalities for direct product graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Tightness_of_domination_inequalities_for_direct_product_graphs"}}}}}