{"entities":{"Q1084114":{"pageid":1094866,"ns":120,"title":"Item:Q1084114","lastrevid":66698595,"modified":"2026-04-12T12:11:38Z","type":"item","id":"Q1084114","labels":{"en":{"language":"en","value":"Distance-hereditary graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3977036"}},"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":"Q1084114$DC8131BB-460F-4FA3-A5D3-A9A0A5D1E6B3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"656b5cf3f1348711fd954fe315770ba91919befd","datavalue":{"value":{"text":"Distance-hereditary graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1084114$E0FAA675-33EC-4EA6-BD8B-916635578B19","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ced71ac6e730e58257f2a0b7da6b10fd6813f0ff","datavalue":{"value":"0605.05024","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084114$A06BC34D-3937-42D0-9B4B-F1395296F097","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"cc0e1243ef3c98b9f99abe7e3898b45d0d4a9448","datavalue":{"value":"10.1016/0095-8956(86)90043-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084114$44807E99-ADC1-45E1-9400-65B1CC220DC6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5a3ffed180ac7e2996949603daeb9082af05d9d2","datavalue":{"value":{"entity-type":"item","numeric-id":290092,"id":"Q290092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084114$4CE0E0CE-7A84-4218-80D5-69F24CF006F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0adbb1357f28935f1684fc542514f52f1a06d10f","datavalue":{"value":{"entity-type":"item","numeric-id":494222,"id":"Q494222"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084114$C3723CBA-D3EF-4A18-AB3D-033D446EB5D5","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084114$465031E9-F9CA-43FA-B949-07D729C8DBA5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63df7153432d81fa42019fcabb076c89649b0b5b","datavalue":{"value":{"time":"+1986-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1084114$6F7E1BF5-2C6C-481A-AB1A-2FD14825CE60","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"833ac2d11bf552f4cde051016625c40c60ee4d49","datavalue":{"value":"A distance-hereditary graph is a connected graph in which every induced path is isometric, that is, the distance between any two vertices in an induced path equals their distance in the graph. A block graph is a conncted graph in which every block (i.e., maximal 2-connected subgraph) is complete. Let G be a graph with distance function d. Then d is said to satisfy the four-point condition if for any four vertices u, v, w, x the larger two of the three distance sums \\(d(u,v)+d(w,x)\\), \\(d(u,w)+d(v,x)\\) and \\(d(u,x)+d(v,w)\\) are equal. An induced subgraph H of a graph G is said to be an isometric subgraph if for any two vertices u, v of H the distance between u and v in H equals the distance between u and v in G. The authors show that if G is a connected graph having distance function d, then the following conditions are equivalent: (i) G is a block graph, (ii) d satisfies the four-point condition and (iii) neither \\(K_ 4\\) minus an edge nor any circuit \\(C_ n\\) with \\(n\\geq 4\\) is an isometric subgraph of G. It is also shown that the finite distance-hereditary graphs of order at least 2 are precisely those graphs which are obtained by applying a sequence of extensions (which are described in the paper) to \\(K_ 2\\). Several consequences of this result are addressed. Moreover, distance-hereditary graphs are characterized in terms of the distance function d, or via forbidden isometric subgraphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084114$106D6557-00E2-4B3B-85C5-A5631391D7C1","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7f532b639e1e3b8bde608d59d2d7e23b01bb3c75","datavalue":{"value":{"entity-type":"item","numeric-id":233441,"id":"Q233441"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084114$8935F019-C314-4613-86CE-D16EF7FBE84E","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084114$8F20E9EF-D82E-4FF9-B19D-DA89A028218A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084114$FCEB9975-EB55-454A-93C1-49AEAF62A342","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"af6f25eb71df82349c816563e7e2c5b01ba89d00","datavalue":{"value":"3977036","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084114$71BA0124-7EBB-4651-A6EE-0FAB7B65533D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"88c1c47738d3665042b1fa5d7685d01aa2ed0416","datavalue":{"value":"distance forbidden subgraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084114$388A818D-8377-45A7-9FFF-DDB3B560619D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"358b2a890150a714c444c1162c9c5b41fa67317e","datavalue":{"value":"distance-hereditary graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084114$1C854BB7-BF4C-4F6F-A607-EC7207E75206","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"79aef9db8e0c683ce6cc529a2f7d1366a38210b6","datavalue":{"value":"block graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084114$A339A4EB-5228-4E73-8E04-97BB409AB4F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c61ccaef0bfc82d891c57837445618d672eb8336","datavalue":{"value":"four-point condition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084114$1D3B89B0-2465-4203-BD5B-68305BE180A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"691c6079d895a302c8561fe33ccaf06d10bb18fa","datavalue":{"value":"isometric subgraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1084114$B311C6CE-419E-425B-9812-7FE5833E954C","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":"Q1084114$40A58420-5648-45EF-AB31-A5AAA0A8F853","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8fa0bdd39a82694c083cbe1abc249b83942c934e","datavalue":{"value":"https://doi.org/10.1016/0095-8956(86)90043-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q1084114$3A4C2EA9-37EA-4FDB-8953-4A48ACCB8A54","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"794916042a64be5fd6baae10abe0df3cdd271f07","datavalue":{"value":"W2041910029","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1084114$E59591FF-050F-44B1-B1E6-A2DC485A1B82","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"08536eb9e10d476ab0b8d5658dcccd83f10410d6","datavalue":{"value":{"entity-type":"item","numeric-id":791544,"id":"Q791544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084114$3010D9E6-52D4-49B4-B0C8-E553A4ABA639","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1870f0ea90fd249da759bb591a72af59317b161","datavalue":{"value":{"entity-type":"item","numeric-id":5610277,"id":"Q5610277"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084114$92CFA90A-D3D3-47A8-8BCF-264881EC951D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"885c0af17638cd451a44f54115261ee06f595123","datavalue":{"value":{"entity-type":"item","numeric-id":1845886,"id":"Q1845886"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084114$8856EE45-275E-47F6-B293-087309FC8DEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee75f7da201ea80c97a446f8f79ea0c77c60ac82","datavalue":{"value":{"entity-type":"item","numeric-id":3960876,"id":"Q3960876"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084114$48A9FA79-0267-4FF6-83C8-0905DB48FFEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ecb8b11e8657ed748318814c5aac440e71814ed0","datavalue":{"value":{"entity-type":"item","numeric-id":1153105,"id":"Q1153105"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084114$0E174FDE-FB0B-4969-9307-12F2FD8BD22A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ba53c03305fcd0c780c8b0cf1f62c0b6d41fecfa","datavalue":{"value":{"entity-type":"item","numeric-id":4154586,"id":"Q4154586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084114$90134ADC-011C-417A-9654-221FF154771E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2623a396ca4848746b70c36190cce2db09627458","datavalue":{"value":{"entity-type":"item","numeric-id":3877729,"id":"Q3877729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084114$47973BC7-974D-4017-AF00-BCD4764762CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9de98442a1ba49ab03432b6c4ee906ffb7310569","datavalue":{"value":{"entity-type":"item","numeric-id":1229892,"id":"Q1229892"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084114$86C51B7C-9100-41F8-ABDA-25727694E63C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"36a5aecc03b0d2165cfb1fd526fae9bd095f8edd","datavalue":{"value":{"entity-type":"item","numeric-id":3877730,"id":"Q3877730"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084114$06CF4D1E-3D4C-4E95-A4DC-5B2901E19878","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"744d1993b5491ce2bbce41e165951e2be6f83abe","datavalue":{"value":{"entity-type":"item","numeric-id":3958504,"id":"Q3958504"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084114$C48617B0-BDCD-493F-AA41-89FF3A62391E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"504295ab6ede06f72a77125fc9a02f368947b8a5","datavalue":{"value":{"entity-type":"item","numeric-id":3940405,"id":"Q3940405"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084114$4D72B002-A374-456C-B86A-DE76580F8E07","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"31403449edcb685befef57967c6d318e33df55c0","datavalue":{"value":{"entity-type":"item","numeric-id":1247984,"id":"Q1247984"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084114$EC72D69A-CA98-4CEC-99B1-D7488FCA94B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac817e1c17268c5892a41ffbf388b80be8630f33","datavalue":{"value":{"entity-type":"item","numeric-id":5514305,"id":"Q5514305"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084114$A0626455-810C-46A2-9030-919F0C1D9AC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae9c36826f0b7f3aca6e5fc18ede28a40704df88","datavalue":{"value":{"entity-type":"item","numeric-id":3953785,"id":"Q3953785"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084114$FDBE9E07-B648-4552-A8FB-AF5F0F6AD298","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"48cefa05d704d074dd504e3354a9ead2b249764a","datavalue":{"value":{"entity-type":"item","numeric-id":3890733,"id":"Q3890733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084114$85E02ABB-2D52-4F13-8294-B64F6ADE9E6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd98c2a60f025b7ae2ec990907c513189b099232","datavalue":{"value":{"entity-type":"item","numeric-id":5567012,"id":"Q5567012"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084114$79E4398E-433A-46C4-9907-0230E05C4D25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e7972f1f280fbed49770877335b3f018eb6b2bc6","datavalue":{"value":{"entity-type":"item","numeric-id":3346369,"id":"Q3346369"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084114$28CDDF5D-0223-4A72-8D48-A9EA81D948F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f663390b351622f1e79d16899c8c42507491ecbf","datavalue":{"value":{"entity-type":"item","numeric-id":5185609,"id":"Q5185609"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084114$1428755B-46B6-43C4-88C5-D8E7F9CBCD78","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"94791c42fa3a98e06bc99ffed3df2d41beb88692","datavalue":{"value":{"entity-type":"item","numeric-id":4073400,"id":"Q4073400"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1084114$F3C95FF7-4142-449D-BD4F-B02A65E035A3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"74391f9ec9c32ae79a79c85f66b861c6ff3ef5fd","datavalue":{"value":{"entity-type":"item","numeric-id":1025561,"id":"Q1025561"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b6c242a08673f4a1b368605a4bb1c1864ec7d331","datavalue":{"value":{"amount":"+0.8331339955329895","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":"Q1084114$8BB1FE6A-6F69-4649-8712-747D8034237B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"85a8b8e7192a06f21db561bfb354896a0bbf0f79","datavalue":{"value":{"entity-type":"item","numeric-id":5957743,"id":"Q5957743"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"771d3026dd8b509d3b79379ba08d09ed458f7cfe","datavalue":{"value":{"amount":"+0.82725590467453","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":"Q1084114$7E7964FE-DA7F-4727-BA95-951EDC410A1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5c1fa79e62daed7d2865cbe5ee35da7ef4d90a87","datavalue":{"value":{"entity-type":"item","numeric-id":3791188,"id":"Q3791188"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"771d3026dd8b509d3b79379ba08d09ed458f7cfe","datavalue":{"value":{"amount":"+0.82725590467453","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":"Q1084114$0A7C092A-9985-431C-999C-89D84A0535AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1ff134eb4ede0b7cebb8030c5127b9e780cac5e6","datavalue":{"value":{"entity-type":"item","numeric-id":3797229,"id":"Q3797229"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"be89e2ad5211a82ec50bf850cc132e89d32dffc6","datavalue":{"value":{"amount":"+0.8247964382171631","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":"Q1084114$DDD9B3F1-97DA-40DF-A01D-12ADBABF3C9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b720b6444f7f7b5ca1d00fe606082d5d6a44ec5b","datavalue":{"value":{"entity-type":"item","numeric-id":3439343,"id":"Q3439343"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c5dd3def677d4cb8e8139d149c6691324d0edd46","datavalue":{"value":{"amount":"+0.8177200555801392","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":"Q1084114$5EFAE1AF-B240-4439-91D7-29DB108E4021","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Distance-hereditary graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Distance-hereditary_graphs"}}}}}