{"entities":{"Q596115":{"pageid":597891,"ns":120,"title":"Item:Q596115","lastrevid":42597992,"modified":"2025-07-04T12:12:24Z","type":"item","id":"Q596115","labels":{"en":{"language":"en","value":"Paired-domination in inflated graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2085520"}},"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":"Q596115$9B71183F-8F79-41E3-A550-32F33240FD95","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"33856440cd93f852b8cb2df356642e04b768b5c9","datavalue":{"value":{"text":"Paired-domination in inflated graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q596115$BC97107A-9822-4B3D-AF6E-D3536839E64F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9d6815335bd15c2fbb3965325d66f165d21e6447","datavalue":{"value":"1051.05067","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q596115$A34592A0-2337-4CD6-8803-DB5EB23C120A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"00833b05240e3fa58209c9502ac8802f9d88d0fd","datavalue":{"value":{"entity-type":"item","numeric-id":306107,"id":"Q306107"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q596115$F047170A-8884-414F-8A23-9EA56E9F13CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5f95c438ee40bfcb8b3856d384e35bb1b4a1c9cc","datavalue":{"value":{"entity-type":"item","numeric-id":1598802,"id":"Q1598802"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q596115$BE6F751A-9FD5-4F18-BCD3-26F14DC68874","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c776795cdde5f51b3c300f0b87440aed88df58e1","datavalue":{"value":{"entity-type":"item","numeric-id":162228,"id":"Q162228"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q596115$2024F43F-D134-42A0-94B3-8B74FD3764D3","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q596115$1DA7AEB8-3B38-4243-83F4-FC700FE487F3","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7e0adf53a19cddd0f150137b2408eb7868ef6930","datavalue":{"value":{"time":"+2004-08-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":"Q596115$7B8589E4-D930-4555-8AEC-D2729B009F9C","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"21098d2ac9eddce1970c3ae29cc629bcc8cd55ff","datavalue":{"value":"http://hdl.handle.net/10397/629","type":"string"},"datatype":"url"},"type":"statement","id":"Q596115$7004F00E-8E52-4918-BA8A-D8C10947EBCA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"afc09cd3432ef60e865bed476c20c86cf6d01da0","datavalue":{"value":"The paper studies inflated graphs of graphs. If \\(G\\) is a graph, then the inflated graph \\(G_I\\) of \\(G\\) is defined. It is obtained from \\(G\\) by replacing each vertex \\(x\\) of \\(G\\) by a clique with the number of vertices equal to the degree of \\(x\\) in \\(G\\) and replacing each edge between two vertices by an edge joining vertices of these cliques, edges incident with one vertex being replaced by non-adjacent edges. A paired-dominating set of \\(G\\) is a subset \\(S\\) of the vertex set of \\(G\\) such that each vertex of \\(G\\) is in \\(S\\) or is adjacent to a vertex of \\(S\\) and, moreover, the subgraph of \\(G\\) induced by \\(S\\) contains a perfect matching. The minimum number of vertices of a paired-dominating set in \\(G\\) is the paired-domination number \\(\\gamma_p(G)\\) of \\(G\\). The main result is the inequality \\(n(G)\\leq \\gamma_p(G_I)\\leq 4m(G)/[\\delta(G)+ 1]\\) for each graph \\(G\\) with \\(\\delta(G)\\geq 2\\). Here \\(n(G)\\), \\(m(G)\\), \\(\\delta(G)\\) denote the number of vertices, the number of edges and the minimum degree of a vertex in \\(G\\).   At the end of the paper inflated trees are studied. An algorithm for determining a minimum paired-dominating set in such a graph is described; it works in time \\(O(n)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q596115$A6BA16E4-4A85-47A0-9C1A-DE98F4634A9D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d9b462d071c33d7d83486f9fef57845bb41d7acf","datavalue":{"value":{"entity-type":"item","numeric-id":190573,"id":"Q190573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q596115$D74F8B95-893F-4521-A25B-52501A1201F1","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q596115$CE0BDE93-7E94-4986-8F8B-6ABE2B14332C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q596115$DE214CF3-8FB6-4ABD-82C6-9E1BD60B0E24","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4e2ed7aada778acd8b6ddf8897471ed17b5214d9","datavalue":{"value":"2085520","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q596115$F368374E-DAA2-4FDE-B27E-AA1D5ACB4663","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4909ca70c1dd2f00208440b712080ba1ec47fc96","datavalue":{"value":"paired-domination number","type":"string"},"datatype":"string"},"type":"statement","id":"Q596115$592B14F9-FFA6-4ECD-B47D-DE2F69F603B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f607710e1bcd8426818fbf0effed996082aed3f","datavalue":{"value":"domination","type":"string"},"datatype":"string"},"type":"statement","id":"Q596115$2102AE11-8A4C-4EF2-81B7-D4F9E532CD18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b8fced99f6fbd4567b042a820473ce73dd063c61","datavalue":{"value":"inflated graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q596115$2BB7F30D-A1EF-4C14-83D1-1BD6F11D77DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"19ec132a1ede33f50fb04fa222303f9cda249a50","datavalue":{"value":"perfect matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q596115$0B2B3497-3CCA-459B-A031-2C299822113F","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":"Q596115$B70CB6F4-E4F2-415A-9E0B-D28DE7957BBD","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ac21f9d06e79505e45b792d1ec67990a629b910d","datavalue":{"value":"W2056878164","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q596115$2DF45095-8393-443F-8F29-F106E98274B9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"559dbe579a3334aacf82df2fdcef598c181017c4","datavalue":{"value":{"entity-type":"item","numeric-id":5422499,"id":"Q5422499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q596115$0C59F5D9-ABBB-4627-8F43-E4F6942188A7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8fc2632cdd374b4e2b71df3a4fba2bcd6893811f","datavalue":{"value":{"entity-type":"item","numeric-id":4390624,"id":"Q4390624"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q596115$D98D5708-F96C-4CAA-AAE7-96292DF4CF34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b94b4483ed3f75bb329dcb2c4f92dc4ca1f833bd","datavalue":{"value":{"entity-type":"item","numeric-id":4242972,"id":"Q4242972"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q596115$A04DB3B3-2046-4159-8C67-34ED741882E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"75287fc79776af9bd4813c20e0c0b1acefc88e6c","datavalue":{"value":{"entity-type":"item","numeric-id":5959093,"id":"Q5959093"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q596115$73E9C113-D824-424C-A143-80FAA59D3650","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1d9dbb3c6e6b917e7718ef847f606f238568493","datavalue":{"value":{"entity-type":"item","numeric-id":4222381,"id":"Q4222381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q596115$C74664C8-1E01-48B3-B4C2-81F57A9C979D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d60c9e7ebaed93a14c443423d2ee67e909f62ff4","datavalue":{"value":{"entity-type":"item","numeric-id":4368728,"id":"Q4368728"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q596115$42E6722E-40F5-4DA2-BB9A-7332714ADA89","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"87fee8f2049c238f17f4418049c6ee138d42447c","datavalue":{"value":{"entity-type":"item","numeric-id":3838207,"id":"Q3838207"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q596115$01003E14-ED3B-4ACD-A304-5A8A752FAA08","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":"Q596115$74E431FC-9C9F-4523-8272-198129DB467C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"db8b224c4a6686791e440200ec094a6717f689c8","datavalue":{"value":{"entity-type":"item","numeric-id":1810885,"id":"Q1810885"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q596115$078E8516-5A37-4621-930B-7424E6475D70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f717cdefe7e1167b285fb83cb1af58c2f1f25c2a","datavalue":{"value":{"entity-type":"item","numeric-id":4504894,"id":"Q4504894"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q596115$D6FE9F9B-2A60-457E-9439-4488A1E41BC8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"68e21ad275d08c05fb2ab0abe99d994c4a6a5f98","datavalue":{"value":"10.1016/J.TCS.2004.02.028","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q596115$C54EEFA1-DEE8-4F6F-8E3F-B1CD631BF3EA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9f8d1c1e76eb877f2d46db78877fd94b48e922e6","datavalue":{"value":{"entity-type":"item","numeric-id":4540077,"id":"Q4540077"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d651d4ab86b4f888ce3f6227359b88329f98b278","datavalue":{"value":{"amount":"+0.94372785","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q596115$A49BFA27-F7C2-4F11-98C5-87A419C9039A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d66a2eaa66677a0531f58f1fd31acba5f461a6c8","datavalue":{"value":{"entity-type":"item","numeric-id":3384606,"id":"Q3384606"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8f887eb0d24f2ebea7f9fec2996f3926dc5bf862","datavalue":{"value":{"amount":"+0.94014287","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q596115$7498C4A7-AF25-4B8D-A2A1-E09915640556","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"92873d348199d022093333ea655060fbea166fca","datavalue":{"value":{"entity-type":"item","numeric-id":4390624,"id":"Q4390624"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ec78813c9bceec1d50f3f90301eef6c386147394","datavalue":{"value":{"amount":"+0.93883955","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q596115$583866EF-8B0A-4375-88B7-447D45D4D8BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ce9244395a1ac9d02bb9abfa446a5ab8c2024a1a","datavalue":{"value":{"entity-type":"item","numeric-id":765350,"id":"Q765350"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fdc644727d960311f2290ca0f950eafead0fe586","datavalue":{"value":{"amount":"+0.92609715","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q596115$7F2439FB-C2AC-4803-BB6A-88C977C53A2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e10a9722fe6d01004c857a83ec7c45f590526ee2","datavalue":{"value":{"entity-type":"item","numeric-id":5461697,"id":"Q5461697"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1265c1a96d2c897d7fc25bd062195a95899791f3","datavalue":{"value":{"amount":"+0.9202373","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q596115$2B5257BA-091B-4955-BE6E-E38489EF9286","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fa9d8c9cdc6f10affb7ca6f2b3c5f050cdc04fcb","datavalue":{"value":{"entity-type":"item","numeric-id":2878211,"id":"Q2878211"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f0dc7be63ad401f6f7a359afef7acbe25bb535a3","datavalue":{"value":{"amount":"+0.9162997","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q596115$3467284B-8A94-40F1-A81D-18919D4AF607","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f238eb08bd0668a925b3bc95bbe92d395e7f5573","datavalue":{"value":{"entity-type":"item","numeric-id":5259449,"id":"Q5259449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"70afe2106dcc23a09d7d9ac71120a70947853c59","datavalue":{"value":{"amount":"+0.9137828","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q596115$657E8A50-B2D5-4AA2-A8D2-807A71A3FED9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"80149841bfb51e2ddd1e537100772faeff0c61c5","datavalue":{"value":{"entity-type":"item","numeric-id":5090188,"id":"Q5090188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"23e3fe3d89d889af120d3c9f12ac96478e7d0974","datavalue":{"value":{"amount":"+0.91141933","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q596115$4AFCA755-1EAB-4865-B067-D263C66FF041","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"12f3730ca9fac56a51df0033784b5d7cdd432e49","datavalue":{"value":{"entity-type":"item","numeric-id":2165257,"id":"Q2165257"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7e4f6b39505d6143ed08b3cf448571a0d09f875d","datavalue":{"value":{"amount":"+0.9089067","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q596115$9249B940-3246-4723-B4E1-F6BCCE7770AA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e49e3c360f7629609bbd55577251954f23ad8101","datavalue":{"value":{"entity-type":"item","numeric-id":604650,"id":"Q604650"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"336850019fb078daf7bb31e06b8e424f23abdf3f","datavalue":{"value":{"amount":"+0.9021269","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q596115$E1AFA2D3-87F5-4180-BBFB-3B1D7929C9E4","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:596115","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:596115"}}}}}