{"entities":{"Q1613397":{"pageid":1624137,"ns":120,"title":"Item:Q1613397","lastrevid":71473362,"modified":"2026-04-13T22:29:54Z","type":"item","id":"Q1613397","labels":{"en":{"language":"en","value":"NeST graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1792339"}},"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":"Q1613397$AA5FAA3A-2745-4ED4-B28C-D518C209CFB9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4fdc346283231d65ad1c7f4ed43897a20945bf70","datavalue":{"value":{"text":"NeST graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1613397$8537A31C-6A5E-4520-B0E0-1927D1F13624","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"0ea963d773079c62d35b9c9108e0528a67c76330","datavalue":{"value":"1003.05087","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613397$477107D2-19BB-48E2-90EA-25674899EC49","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0935ef66f64dc201bfe3bd2ca6f3dcc87b6b3031","datavalue":{"value":"10.1016/S0166-218X(01)00207-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613397$14D9E974-A71A-4F92-9726-0CE1D91A60AE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"46bd635dd0821de2113c270b8d0c0de1c106ffb3","datavalue":{"value":{"entity-type":"item","numeric-id":222626,"id":"Q222626"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613397$E00FF210-F6A4-4C0C-A94F-DF6A73BDD8E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"7d091b157f768ca461d27fad72977102c350ed3b","datavalue":{"value":{"entity-type":"item","numeric-id":1613395,"id":"Q1613395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613397$C4995157-163E-4D25-B777-3D411A3F9CAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f19123f56c195a5b228aca240dadda997ad3bba7","datavalue":{"value":{"entity-type":"item","numeric-id":1080648,"id":"Q1080648"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613397$299F8988-EC30-4840-B3AD-864C7FEEB23A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"087f55844cc920aae060b09644168bf17b022e1a","datavalue":{"value":{"entity-type":"item","numeric-id":96294,"id":"Q96294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613397$8D890D29-8BB2-44E1-A514-6FF307E01F32","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"04ef60e6a08d63a03521c7b80b58e0a998b63b55","datavalue":{"value":{"time":"+2002-08-29T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1613397$99038184-3D00-4B54-9161-2B7F7D0C0C3F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c35fb394bae3ab231f3d7abc9afb976fdf2c4309","datavalue":{"value":"Let all graphs \\(G= (V,E)\\) considered in the paper be simple and undirected ones. \\(G\\) is a generalization of the known interval graph if there is a set \\(\\{I_v\\mid v\\in V\\}\\) of intervals of the real line and a set \\(\\{\\tau_v\\mid v\\in V\\}\\) of positive tolerances such that \\(xy\\in E\\) iff \\(|I_x\\cap I_y|\\geq \\min\\{\\tau_x,\\tau_y\\}\\). Such a graph \\(G\\) is called a tolerance graph. And by replacing neighborhoods of the line (namely intervals) with neighborhoods of an embedded tree this generalization of the tolerance graph yields the class of neighborhood subtree tolerance (NeST) graphs (see the exact Definition 1).   In the present paper properties of NeST graphs are investigated and especially the following four subclasses are considered: (1) unit NeST graphs, in which all neighborhood subtrees have unit diameter; (2) proper NeST graphs, in which no neighborhood subtree is properly contained in another; (3) fixed distance NeST graphs, in which neighborhood subtree centers are equidistant; (4) fixed tolerance NeST graphs, in which all tolerances are the same.   Besides numerous detailed results the authors get the following main results which partly are equivalence relations: (1) \\(G\\) is a proper NeST graph iff \\(G\\) is a unit NeST graph (Theorem 2). (2) \\(G\\) is a fixed distance NeST graph iff \\(G\\) is a threshold tolerance graph (Theorem 7). (3) \\(G\\) is a threshold graph iff it is a fixed tolerance, fixed distance NeST graph (Theorem 8). (4) It is known that NeST graphs are weakly chordal (i.e. neither the graph nor its complement contains an induced cycle with five or more vertices), but the authors could show that there exists a class of weakly chordal graphs which are not NeST (e.g. the 2-star, 3-star and 4-star; see figure in the paper). The authors prove that NeST graphs form a proper subclass of the weakly chordal graphs (Lemma 6). Finally three open problems are given.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1613397$0257FF3F-8C52-4399-A7E9-6D6CA5B15DCF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613397$BB22D939-7F5F-4B57-8DC3-6A43D5A9F578","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"52f8a45271974d4b1f6e121afc58846c68e37378","datavalue":{"value":"1792339","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613397$FF302CB3-B99C-4473-9482-0C87BFCED656","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7a949c568749d2f4337e1772be827516d5211abc","datavalue":{"value":"interval graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1613397$CF9E7436-37A9-471D-9BF0-67201A50BEEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ee4bd296f647a0b2b6777617b5e8acfeee896b9e","datavalue":{"value":"tolerance graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1613397$AC4D653B-AE46-46B3-B5D4-9FADA1B13DDD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"59a429e6072f19afe1e133ca8ac15d67857ff6e9","datavalue":{"value":"neighborhood subtree tolerance","type":"string"},"datatype":"string"},"type":"statement","id":"Q1613397$5572C1D5-CDAB-4F20-85A8-22799BEA4AAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"67b7f2b7d313afc14e0737023f53318c1fc147e8","datavalue":{"value":"threshold graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1613397$0D36798D-3B68-4BC2-9D9D-B1BE58A2B21B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"853bd0b31f9734652041500f2e432a6c8df42e70","datavalue":{"value":"chordal graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1613397$8FC248AA-1B71-4CDC-87F4-4980ACE449CC","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":"Q1613397$7EAFB2F5-ED06-420A-8467-2D0A4AF8BA7D","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":"Q1613397$C9E53712-F291-4FDE-8ED8-3E5D6F6FB96E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8a74f042ba1f29a12a670ab9d659cf777707121","datavalue":{"value":{"entity-type":"item","numeric-id":798301,"id":"Q798301"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613397$76A4E4B6-FDF3-4923-BA54-9EA20115150C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d1d3ea4c16eb24d54ef2e96440608aca01a61c8","datavalue":{"value":{"entity-type":"item","numeric-id":1801665,"id":"Q1801665"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613397$FAE0BFB5-1BFF-45CD-9CBB-ED4912059109","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4cc9754122bf000f04f8ae1416524e4c1550a854","datavalue":{"value":{"entity-type":"item","numeric-id":1894354,"id":"Q1894354"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613397$AD7EDC43-E5DF-44D2-8A58-7F692F288F91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ea8f9edc5faa2fd277810a544fb03be621def82f","datavalue":{"value":{"entity-type":"item","numeric-id":3097395,"id":"Q3097395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613397$2C3443E1-F64B-40A9-B95B-CBEAD85B73F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e458531dc8f9b4a4f76ca8cb6a5d9d31ac768ee2","datavalue":{"value":{"entity-type":"item","numeric-id":2562090,"id":"Q2562090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613397$4FF6DC88-FF6D-4B08-AEC3-D86B52BE039A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"83ab81b85457f990d5674daf61fc32a97eb26853","datavalue":{"value":{"entity-type":"item","numeric-id":1254334,"id":"Q1254334"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613397$4CE95E2D-255D-47BA-8D15-53DD01A45575","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"49716778d2052bc48c41f915a376cfa1f999ef74","datavalue":{"value":{"entity-type":"item","numeric-id":3328583,"id":"Q3328583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613397$1F71E134-D7C4-4EA9-A707-81F4F8DC9048","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c2e498f8f059ec2cdc0575cdc006d5c453bc3e3f","datavalue":{"value":{"entity-type":"item","numeric-id":1060226,"id":"Q1060226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613397$D9085C2B-D04A-4D79-8EEB-2AD6EBE819D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"70932f1cf740819121b6dff2db80775f668b9c68","datavalue":{"value":{"entity-type":"item","numeric-id":3216686,"id":"Q3216686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613397$26A67C4F-6A6C-43F5-A9BD-5855EF587C1E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc441cc049bd37d953303b05fb551abe2b633925","datavalue":{"value":{"entity-type":"item","numeric-id":3322150,"id":"Q3322150"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613397$258615A1-45F5-41D0-AD42-7DC29A3A1290","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0ddcab77cc06a1867f1053994ad87177b46c2d8a","datavalue":{"value":{"entity-type":"item","numeric-id":798675,"id":"Q798675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613397$DF58E7E6-F696-4E36-AF6D-2B2A4B34C405","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7855dbbf166d4e2ba530b2ed8bcd7465cd77369c","datavalue":{"value":{"entity-type":"item","numeric-id":4828541,"id":"Q4828541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613397$C507A1E2-15CC-485A-ADAC-78DD5EE0968A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5b276fdb2188dac0c4b19127d85e1049cb332b2c","datavalue":{"value":{"entity-type":"item","numeric-id":801088,"id":"Q801088"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613397$54A9874A-6B47-4DAF-937E-113E6798D649","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8b41f4b79d989014d94998f0c88d8168c94ef06d","datavalue":{"value":{"entity-type":"item","numeric-id":1974525,"id":"Q1974525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613397$79C1B6F7-CFDA-4220-A7DE-6466FDD3DB31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d6cd373381835c6f2d57b342c7a1782c31e49f1","datavalue":{"value":{"entity-type":"item","numeric-id":3797238,"id":"Q3797238"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613397$F0565866-C312-4B73-94BF-6238120ABB22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cfd444ac2099fb3b5a15da02a0171b8b4a45b7ea","datavalue":{"value":{"entity-type":"item","numeric-id":5588432,"id":"Q5588432"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613397$94BB7178-A275-478E-94B4-AE4CE49F669C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3909e251ac5ae019aa4dbb6092982ac711a36f1b","datavalue":{"value":{"entity-type":"item","numeric-id":3222208,"id":"Q3222208"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1613397$70173CDD-7388-460D-8A65-E4A8233A0A01","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"4e56d6e378fee66e0152b3788e1ac8bd300dbb6d","datavalue":{"value":"https://doi.org/10.1016/s0166-218x(01)00207-4","type":"string"},"datatype":"url"},"type":"statement","id":"Q1613397$8AF31138-B891-496A-82D4-463F88FAA19F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"8b989bf313d089bf72621d73864deae191560593","datavalue":{"value":"W2914372882","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1613397$021C66EA-2804-4D8C-8CD0-2FF5D891C53E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e0f6c1e5c641f6aeed1a55fd5c606a83d9482607","datavalue":{"value":{"entity-type":"item","numeric-id":1894354,"id":"Q1894354"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6e2db8e833a56fe296b72de3fc8c99c5eb7d8e05","datavalue":{"value":{"amount":"+0.7493100166320801","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":"Q1613397$232F65F9-08E5-4895-B21E-7E9569EA169F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9f77de3db67d8ee13111e7adbe9c803dc1dbfe4a","datavalue":{"value":{"entity-type":"item","numeric-id":689957,"id":"Q689957"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1b0c165d976187ce115b0a85fb77b0e5ae94ba18","datavalue":{"value":{"amount":"+0.7493099570274353","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":"Q1613397$7E116D84-38E7-4551-9F97-73C69DB491AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e620be9501f51033c8cd1576b44bd4ddf7391d1d","datavalue":{"value":{"entity-type":"item","numeric-id":4873748,"id":"Q4873748"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0b614030e29dd5c057552deb7856a9913e2cf6bd","datavalue":{"value":{"amount":"+0.7439301609992981","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":"Q1613397$7958E0C7-CF76-42B1-A18C-2B45B25E1BAF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a407519ee19de36652f806367f59441ef6f733b4","datavalue":{"value":{"entity-type":"item","numeric-id":4329117,"id":"Q4329117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"09b38b52fb1c3e1591aeb55c941406e7045c84f2","datavalue":{"value":{"amount":"+0.7345417141914368","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":"Q1613397$D7245E05-7A6C-45AF-9277-37E464042982","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1ce80f0364521c25eb3efadb078507826bda5088","datavalue":{"value":{"entity-type":"item","numeric-id":2910023,"id":"Q2910023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"09b38b52fb1c3e1591aeb55c941406e7045c84f2","datavalue":{"value":{"amount":"+0.7345417141914368","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":"Q1613397$8392967E-0FD9-453F-8C5B-F0F8EE6CAB11","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"NeST graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/NeST_graphs"}}}}}