{"entities":{"Q1567686":{"pageid":1578426,"ns":120,"title":"Item:Q1567686","lastrevid":72213486,"modified":"2026-04-14T03:22:49Z","type":"item","id":"Q1567686","labels":{"en":{"language":"en","value":"On median graphs and median grid graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1462339"}},"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":"Q1567686$A2127A3D-3635-4A7A-9AA7-19122DC7DE91","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"49f1aeb5371f3b935077e7eae3bb0cb533d7d653","datavalue":{"value":{"text":"On median graphs and median grid graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1567686$3D6FE216-BA97-4255-8F9D-DA88A2103C93","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2f6bdc4a3c9b9ced3f4e3150dbfa43f568a708e7","datavalue":{"value":"0953.05065","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1567686$5A87F2FF-7B37-4BE0-8FFD-107200E3DF8F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"ba20527b38ecca64d137b5ba9aaf5a0a5467675a","datavalue":{"value":"10.1016/S0012-365X(00)00085-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1567686$75A9C610-06D4-432B-85DD-FADEECD21A0E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9ceb1fcf1c75dc367d934ec93f0fd1abaa5c7756","datavalue":{"value":{"entity-type":"item","numeric-id":251101,"id":"Q251101"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1567686$EE79DE98-DD52-4E4D-966B-162341EEC950","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"4e5a7d23e1fff54ee9ed9fd3c409e41120ec5166","datavalue":{"value":{"entity-type":"item","numeric-id":181824,"id":"Q181824"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1567686$DF33263E-99ED-45CB-95DC-C41A063B5692","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":"Q1567686$F1D87208-D12B-4973-840F-1D332A602605","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"4099843518a30c1bf03605cf49370c7e4c9d446d","datavalue":{"value":{"time":"+2000-08-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1567686$EB2C2231-674F-4D58-BCA2-BBA8124B480F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2b276e76dffb2e798922d9fbba19ef7331131714","datavalue":{"value":"Let \\(G= (V,E)\\) be a graph with \\(|V|= n\\) and \\(|E|= m\\). A cycle \\(Q_4\\) of length four is called a square and the distance \\(d(u,v)\\) between vertices \\(u\\) and \\(v\\) of \\(G\\) is the usual shortest path distance. A vertex \\(x\\) is a median of a triple of vertices \\(u\\), \\(v\\) and \\(w\\) if \\(d(u,x)+ d(x,v)= d(u,v)\\), \\(d(v,x)+ d(x,w)= d(v,w)\\) and \\(d(u,x)+ d(x,w)= d(u,w)\\) and a connected graph \\(G\\) is a median graph if every triple of its vertices has a unique median. For a graph \\(G\\), Djokovi\u0107 and Winkler's relation \\(\\Theta\\) is defined on \\(E(G)\\) in the following manner: If \\(e= xy\\in E(G)\\) and \\(f= uv\\in E(G)\\), then \\(e\\Theta f\\) if \\(d(x,u)+ d(y,v)\\neq d(x,v)+ d(y,u)\\). It is known that \\(\\Theta\\) defines an equivalence relation on \\(E(G)\\) of a median graph \\(G\\). The number of these equivalence classes be denoted by \\(k\\).   The authors get the following first result for \\(Q_4\\)-free median graphs \\(G\\): For these graphs the equation \\(2n- m-k+ h= 2\\) holds, where \\(h\\) is the number of subgraphs of \\(G\\) isomorphic to \\(Q_3\\) (Theorem 4). In the second part median grid graphs are considered and characterized structurally; a grid graph is a subgraph of a complete grid (the Cartesian product of two paths) and complete grids are median graphs. The authors get as second result a characterization of a connected grid graph \\(G\\) by five equivalent statements, for instance: \\(G\\) is a median graph, \\(G\\) is a square-edge graph, or \\(G\\) contains \\(m-n+1\\) squares (Theorem 7).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1567686$D0D6891D-6749-455A-86E5-D9A6DC01CFE3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1567686$9AA1845E-A878-428A-BAC8-8C500DC8CF42","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0c4f6db4865522b91fa427236b198863acb541ba","datavalue":{"value":"1462339","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1567686$2AB81A56-1D66-4008-B797-192E4B02BFB9","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"34612b6e86c8bf5e7dd146886eeb9a44e341c7db","datavalue":{"value":"path distance","type":"string"},"datatype":"string"},"type":"statement","id":"Q1567686$B55E07D4-D390-40DB-9A9B-F1039A0072B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9bd9ea617060a6ee63b27777af2102ab68c462d8","datavalue":{"value":"median","type":"string"},"datatype":"string"},"type":"statement","id":"Q1567686$0CAF6DE9-9C93-4EA9-94E8-535CF52FC6CD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"419b197f204be1b3bb74cc8158cbf20cc120be7e","datavalue":{"value":"median graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1567686$3A98B66A-F1AB-47C9-B94A-247C4D7FC7E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"69483333b2a0642cb44016f8ffa7721e67114d7b","datavalue":{"value":"median grid graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1567686$37CD7E06-BB0E-4B40-A4A7-6D3B69C56936","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b0c8af976d4e103d0615fe9a393429f2ed204fe8","datavalue":{"value":"square-edge graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1567686$B1B7B872-49B3-481E-A147-8D32962F2C59","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"3fe0695de7d48830df5f66cbab382c56aa71a075","datavalue":{"value":"Q60962155","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1567686$23D8B54F-5DE2-40A5-92C4-DCDF6201B67E","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"31cef456e8646accdc28b523a232a52220366047","datavalue":{"value":{"entity-type":"item","numeric-id":593309,"id":"Q593309"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1567686$3C41BE9C-59FA-4B3A-B487-2C1CEA3F2600","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":"Q1567686$D83128EC-7A11-426C-B5D6-FAE5679A940B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6af0a8ba91e63478d2500b0a397f8c3c5fb8fc79","datavalue":{"value":"https://doi.org/10.1016/s0012-365x(00)00085-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q1567686$BA73604B-9FA6-4601-AD97-06AB94F23E3A","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3f8b0e887fd972113fbbbe3355e9cec147024829","datavalue":{"value":"W2124544650","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1567686$F77F4CFB-0C92-4437-BE7C-AD23971DE646","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f0d02056b2b923ceafeed10a94ccebac26c80e1c","datavalue":{"value":{"entity-type":"item","numeric-id":2480201,"id":"Q2480201"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ffdef01756116174d08e6e835367a98ce2c0f5f7","datavalue":{"value":{"amount":"+0.9267473","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":"Q1567686$3A507EF6-43E2-4EE8-B391-E066DE4ADCD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2bc19ed298497af102450890998d4a82bc08d17f","datavalue":{"value":{"entity-type":"item","numeric-id":2271138,"id":"Q2271138"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d271846245f78f52de10799b4a84993234937a3b","datavalue":{"value":{"amount":"+0.924824","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":"Q1567686$250A40E3-95DC-46AB-89FA-783295521CAB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4b010cea863b7b89475bfab79bd8d43c91d2b6a8","datavalue":{"value":{"entity-type":"item","numeric-id":1388033,"id":"Q1388033"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f5aa1283273270c8826f96f56905ab68ab01cdd6","datavalue":{"value":{"amount":"+0.9202553","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":"Q1567686$1BF85EB5-E8CB-4C23-BD22-3811334275FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5a573c7d3a1a0afaeb080a567d8e527215d6f7c8","datavalue":{"value":{"entity-type":"item","numeric-id":4264556,"id":"Q4264556"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bd615db94b76f322fdc75263c8f4ee823b83cf6f","datavalue":{"value":{"amount":"+0.9181909","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":"Q1567686$8F9ABC00-986A-4B96-A5C8-927521D700B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"feb4782c4c34b3f75fecdd971c5148a8592cdf59","datavalue":{"value":{"entity-type":"item","numeric-id":686442,"id":"Q686442"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6772424057aa4a797212b07614cb0a9da0d388db","datavalue":{"value":{"amount":"+0.9151286","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":"Q1567686$46BEE497-044B-4911-87FC-072201D656EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d68adf34a562e8ab63939d461c6b01bf6c6941e5","datavalue":{"value":{"entity-type":"item","numeric-id":5284578,"id":"Q5284578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"72be346fb3541d16d97b501ad3a3e62b48455877","datavalue":{"value":{"amount":"+0.9150271","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":"Q1567686$A238FFC1-91C4-4F2F-B57C-53BE53798901","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"698dc6c4128c47b759acdc582d062a34c3cecc32","datavalue":{"value":{"entity-type":"item","numeric-id":762504,"id":"Q762504"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3aa5908ddbf1979d274068bc739009febc946d9f","datavalue":{"value":{"amount":"+0.91440666","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":"Q1567686$F362E9BB-9388-4741-B969-0F624D296503","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"91835effb5138aea52783bbf9fa4ddb3d2d7cf45","datavalue":{"value":{"entity-type":"item","numeric-id":1322201,"id":"Q1322201"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"765394ae9f7f55d9b38ba91151c70cc34410d415","datavalue":{"value":{"amount":"+0.9098477","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":"Q1567686$52EB54A8-3129-4998-B973-85E340A022F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8d48ddf86794b922fe6daba766a825a8742794a8","datavalue":{"value":{"entity-type":"item","numeric-id":4255811,"id":"Q4255811"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"85d6b5b41a147c1f8c963f9f1d51e940e586cde0","datavalue":{"value":{"amount":"+0.90687805","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":"Q1567686$730A0878-DDBA-4234-ABDD-1891614375F3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On median graphs and median grid graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_median_graphs_and_median_grid_graphs"}}}}}