{"entities":{"Q1349072":{"pageid":1359811,"ns":120,"title":"Item:Q1349072","lastrevid":47914579,"modified":"2026-01-03T01:58:21Z","type":"item","id":"Q1349072","labels":{"en":{"language":"en","value":"The direct expansion of graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1743008"}},"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":"Q1349072$8304E836-AC14-499C-BBD1-4E06B07388DF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6cb2fce67c25204d3044203b712063b1feab658b","datavalue":{"value":{"text":"The direct expansion of graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1349072$1B62F086-D113-4891-8178-D8CB9CA4B95D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"aa1ff6e0e57d054db5ac93a62034544ccec20d1f","datavalue":{"value":"0990.05088","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1349072$433DC353-2EA5-4907-8D9F-0B76B9794054","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"dd67a3846128e4e90b891f0c90deee1832c9b464","datavalue":{"value":"10.1016/S0012-365X(01)00066-8","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1349072$BD71CC5B-0753-4331-B92B-4BF54885A611","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"abbcdf7f349ec1c893eaf2145312e7a0ff37fb4d","datavalue":{"value":{"entity-type":"item","numeric-id":195154,"id":"Q195154"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1349072$609394CE-84A6-45F7-BF14-B668E4516B14","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":"Q1349072$33A135D8-CCA3-4956-BC81-8991B55DFC17","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"cda08edf6e14c28a948f9b78f5bc4351bb49e6b0","datavalue":{"value":{"time":"+2002-05-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1349072$E737E02E-EE62-4D77-881E-9E5894A2FEC4","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a06d1469565dad4e9d28ffdf45b64eef12ede8a9","datavalue":{"value":"Expansion procedures introduced by \\textit{H. M. Mulder} [The expansion procedure for graphs, in: Contemporary methods in graph theory. In honour of Prof. Dr. K. Wagner, 459-477 (1990; Zbl 0744.05064)] proved to be useful in recognition of median, quasi-median and partial Hamming graphs.   Here the author focuses on connectivity properties of one particular such procedure, the direct expansion. Given a covering of a graph \\(G\\) by two induced subgraphs \\(G_1\\) and \\(G_2\\) with intersection \\(G_0\\) (no edges linking \\(V(G_1)-V (G_0)\\) with \\(V(G_2)-V(G_0)\\)), the direct expansion \\(G'\\) of \\(G\\) (relative to this covering) is obtained by replacing \\(G_0\\) by the direct product \\(G_0\\times K_2\\), leaving \\(G_1-G_0\\) and \\(G_2-G_0\\) unchanged, and edges linking \\(V(G_1)-V (G_0)\\) (resp. \\(V(G_2)-V(G_0)\\)) with \\(V(G_0)\\) in \\(G\\) correspond to edges linking \\(V(G_1)-V(G_0)\\) with \\(V(G_0)\\times \\{ 1\\}\\) (resp. \\(V(G_2)-V(G_0)\\) with \\(V(G_0) \\times \\{ 2\\})\\) in \\(G'\\).    The questions addressed in the paper are the following ones: (1) when is a direct expansion a connected graph and (2) what is the length \\(\\text{del} (G)\\) of the longer sequence of iterative direct expansions on a given graph \\(G\\) which produce a disconnected graph only in the last step (a measure of robustness with respect to direct expansion). In both questions, trivial direct expansions, i.e. \\(G_2=K_1\\), are excluded since they always produce disconnected graphs.   A characterization of coverings whose direct expansion give rise to a connected graph is given in terms of parity of cycles or expanding walks in each of the two copies of \\(G_0\\) in the expanded graph. As a result, it is shown that trees are the only connected graphs such that direct expansions are always disconnected, and there is a characterization of graphs such that all nontrivial direct expansions are connected.   In particular, graphs with del\\((G)=0\\) are nonconnected graphs and trees are the ones with del\\((G)=1\\). Characterization of graphs with del\\((G)=2\\) is given and it is proved that graphs containing \\(K_4\\) have del\\((G)=\\infty \\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1349072$1E5CCFC4-FF6F-41B9-BC6C-D235711ACD81","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"f86ae92a12b6f2005686f105ca0c7b4e742c8977","datavalue":{"value":{"entity-type":"item","numeric-id":189772,"id":"Q189772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1349072$EA1C2F0D-892D-4E59-84D8-B9CB08452EBD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1349072$2E93AF87-50C3-43DB-A528-12CE8D7180AF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0894e1b88fd34259b16019c7ad2f746a7f01c44d","datavalue":{"value":"1743008","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1349072$B2A9663E-6DA8-4A38-AEAC-BC02DD1294F8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c0b2daaf7ac864516e7b1b0451bfe3e1040a3880","datavalue":{"value":"direct product","type":"string"},"datatype":"string"},"type":"statement","id":"Q1349072$10B400CF-400B-4AAB-A260-24C3AD478B9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a56e5793ea33870a204239ad40fe7f02bf24fac2","datavalue":{"value":"expansion","type":"string"},"datatype":"string"},"type":"statement","id":"Q1349072$00BD54CE-3F8C-4AFB-BD81-42DCE9B57458","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eba61a8abead030333429495c832d733d94064bd","datavalue":{"value":"connectivity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1349072$15228E5D-8FF3-466A-8D60-D9D98F07A60A","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":"Q1349072$CB79C5A8-B2BB-493D-A5D6-758DCBBE3AAC","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b6c205f4cec7ae92e120309dbd77e77e9436a866","datavalue":{"value":"https://doi.org/10.1016/s0012-365x(01)00066-8","type":"string"},"datatype":"url"},"type":"statement","id":"Q1349072$81E6EC03-37FC-442C-9582-F880A862578D","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"4fc1efe1116d73780cbe9dd56cba55b8261f4b35","datavalue":{"value":"W1996265432","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1349072$20F235DD-A8D0-4BC3-B590-356C0D2EB882","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ce6b21ff80bcf48d35474042b98e872531ea767f","datavalue":{"value":{"entity-type":"item","numeric-id":3972522,"id":"Q3972522"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"02672a8cf7df33f1a1f5cd08c20da5b936c32f62","datavalue":{"value":{"amount":"+0.8433193564414978","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":"Q1349072$E6131946-3E31-46C1-8C8C-EA28E81DC5CE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ad1351c444f0097034121ff7fdc5f4d1591d239a","datavalue":{"value":{"entity-type":"item","numeric-id":4032985,"id":"Q4032985"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c403c624bc16166f51d949c350c95f815a047e11","datavalue":{"value":{"amount":"+0.8344371914863586","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":"Q1349072$A0892EC8-5326-4DD9-A62B-A9F644860B95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a68ec8b98caf9c4c771cf783d749c304595f75e0","datavalue":{"value":{"entity-type":"item","numeric-id":5939915,"id":"Q5939915"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"efbe868166e49144b4a8c78011bb4a80a958671b","datavalue":{"value":{"amount":"+0.7730172276496887","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":"Q1349072$97CE1310-A69E-47CF-8B15-FCD08D97B021","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2fa30b3349bd6a056b32f49b2023500b435ea615","datavalue":{"value":{"entity-type":"item","numeric-id":3517157,"id":"Q3517157"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"efbe868166e49144b4a8c78011bb4a80a958671b","datavalue":{"value":{"amount":"+0.7730172276496887","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":"Q1349072$1942BFF2-74EE-4EDD-A888-A5BA72E56A72","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1cf844e08caa7a1ea6b580292684717bfc36344c","datavalue":{"value":{"entity-type":"item","numeric-id":4865631,"id":"Q4865631"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dc3f5a2e067c93160e38638064b44ec699958245","datavalue":{"value":{"amount":"+0.7704459428787231","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":"Q1349072$65C97AD3-7E9F-4F5D-834E-17BD25A83A2C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1349072","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1349072"}}}}}