{"entities":{"Q2004085":{"pageid":2014827,"ns":120,"title":"Item:Q2004085","lastrevid":57648057,"modified":"2026-03-31T18:59:58Z","type":"item","id":"Q2004085","labels":{"en":{"language":"en","value":"The threshold dimension of a graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7260824"}},"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":"Q2004085$3AB04102-B8CE-4F9A-B858-7AFE704157CA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"10b5402450f636529c80b9f43cb1be3b0b07aca8","datavalue":{"value":{"text":"The threshold dimension of a graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2004085$672739B8-B2AE-4C02-9C30-16CBDF537794","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"929c87d3b32844b13bad9077ab34ddc31f7020a6","datavalue":{"value":"1450.05020","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2004085$F3687FD7-8AF6-4B56-AE38-7402C04A951F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"29830149ae199bbf812bdac2cabf32639572e204","datavalue":{"value":{"entity-type":"item","numeric-id":2004084,"id":"Q2004084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2004085$70468FF5-3D29-450A-AA8F-597DC7A064AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"10d6b5e515dceb221a589d7f5f19f5051245a01e","datavalue":{"value":{"entity-type":"item","numeric-id":1413461,"id":"Q1413461"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2004085$07C940F9-CD40-479D-BBF5-C8505F2C305A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f35420b14e006c4a26de46d6172502a88cc18a63","datavalue":{"value":{"entity-type":"item","numeric-id":233441,"id":"Q233441"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2004085$9B7D631E-76FC-4914-A440-502922E63F52","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":"Q2004085$73F47B25-C091-4E1A-9064-843D4C9254D6","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"01d421ee24aa6ebdb05b23704eda826b87451a7c","datavalue":{"value":{"time":"+2020-10-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2004085$F882CB53-7C27-4CEC-AF4D-E3172921B9C3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6cb134356f8eb9901002b2eda70aab2559599ddd","datavalue":{"value":"https://arxiv.org/abs/2001.09168","type":"string"},"datatype":"url"},"type":"statement","id":"Q2004085$8430BC9B-463A-4CCB-9E1D-C53F33F84EAA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"605d695e0b0feffa104b43b0332b976cca8b4bcf","datavalue":{"value":"In this paper, the threshold dimension of a graph \\(G\\), denoted by \\(\\tau (G)\\) is defined as the minimum metric dimension among all graphs \\(H\\) having \\(G\\) as a spanning subgraph, or the minimum metric dimension among all graphs obtained from \\(G\\) by adding edges. If \\(\\beta (G)= \\tau (G)\\), where \\(\\beta (G)\\) denotes the metric dimension of \\(G\\), then \\(G\\) is said to be irreducible; otherwise, \\(G\\) is called reducible. If \\(H\\) is a graph having \\(G\\) as a spanning subgraph and such that \\(\\beta (H)=\\tau (G)\\), then \\(H\\) is called a threshold graph of \\(G\\). The first part of this paper gives an expression for the threshold dimension of a graph in terms of a minimum number of strong products of paths (each of sufficiently large order) that admits a certain type of embedding of the graph. Using this result, it is proved that there are trees of arbitrarily large metric dimension having threshold dimension equal to two. The second part of the paper focuses on the threshold dimension of trees, establishing a sharp upper bound for the threshold dimension of trees and showing that irreducible trees are precisely those of metric dimension at most 2. Moreover, if \\(T\\) is a tree with metric dimension 3 or 4, then \\(T\\) has threshold dimension 2 and in each of these two cases a threshold graph for \\(T\\) can be obtained by adding exactly one or two edges to \\(T\\), respectively but there are trees of metric dimension 5 with threshold dimension exceeding 2. Two open problems conclude the paper.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2004085$5BD9ACCD-9BC1-4694-998B-7E473B5E9288","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"49b058fb3bbcf2e2c0b60d335491b1fb69531246","datavalue":{"value":"05C12","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2004085$5BAAFF5E-599F-48BD-8F93-BEE366428641","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2004085$BB3EB3EA-62D1-45FE-A0B9-BACF13A06088","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f54624d6184313158324a5b5a097f6e611a50ba5","datavalue":{"value":"05C76","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2004085$3EF05CC6-D796-4496-81C7-A0DEE10B6332","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"be1728778b2c3c998d63d1dbe8dae78bd7f7648c","datavalue":{"value":"7260824","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2004085$95EFED1E-0039-42FE-9B0E-1E1A090BEDA1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"604cbdddca0830021cc6d38e636cc845e8de2443","datavalue":{"value":"metric dimension","type":"string"},"datatype":"string"},"type":"statement","id":"Q2004085$3EF9FA23-7835-43E0-914D-3AECFF02DED6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"36c128039aee3cc67b32bab9e0eaba683b60f0f0","datavalue":{"value":"threshold dimension","type":"string"},"datatype":"string"},"type":"statement","id":"Q2004085$48B91454-5AB8-4C21-8217-668F3E62890C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"80f5c28167f5ca94f50a19a1cc36379213f99b61","datavalue":{"value":"irreducible graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2004085$E86AC549-2E87-4E88-AB4F-0210821CB369","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ef9226da4ea410a4703b783a88869ea6aaacfe55","datavalue":{"value":"strong products of paths","type":"string"},"datatype":"string"},"type":"statement","id":"Q2004085$A5B48F27-7A6D-484C-8D1C-D3A32E730EE3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c24938459dbf20196734dcf6c3a35c8a8724abee","datavalue":{"value":"trees","type":"string"},"datatype":"string"},"type":"statement","id":"Q2004085$7FD2B76C-CA95-40E5-A229-4C9E75474F86","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"af6f91027425e6a3e182e3068da26575ef8e093e","datavalue":{"value":{"entity-type":"item","numeric-id":190560,"id":"Q190560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2004085$8A244EC4-5786-4EBC-A431-73CA25E6E7CF","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":"Q2004085$53EF4EE4-1B7D-438F-91C2-1FF0DFAF8E1E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"0129d13bbd5ec252ccad46e45c0d80916d329360","datavalue":{"value":"W3081036497","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2004085$DB5FDEF9-1199-40F9-8FDE-8374A6B9DD5B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2086d28af5b03d284378faa8645e4e8160ba3a79","datavalue":{"value":{"entity-type":"item","numeric-id":2946381,"id":"Q2946381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2004085$2693C90D-4DAD-4C08-A94F-B7B54FDD0BB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"11180e3bb44babecb541d0fb1385794f46c8b136","datavalue":{"value":{"entity-type":"item","numeric-id":3503226,"id":"Q3503226"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2004085$6475D63E-A490-4D4C-ADEA-660B3EFB7179","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9cb93926a95df0e62bbd2a829437998cb1795d97","datavalue":{"value":{"entity-type":"item","numeric-id":1582071,"id":"Q1582071"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2004085$B0B4B30D-5A35-48B8-BDFB-5D00E58D9506","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2aae9c613d2a3b0dcff5efe4742f4db9d42579e0","datavalue":{"value":{"entity-type":"item","numeric-id":4522458,"id":"Q4522458"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2004085$EF44EE2E-7E63-4F78-B174-406F9015769E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d543e0e002ccb8d633dfbf8d6e835be577ec4d3a","datavalue":{"value":{"entity-type":"item","numeric-id":3005852,"id":"Q3005852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2004085$8CF5C745-9949-4DF4-BC55-D568CA7C84B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a7cd472af80523eb239e1437aa7fbccca41b12e7","datavalue":{"value":{"entity-type":"item","numeric-id":4119237,"id":"Q4119237"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2004085$9ADF8C3E-0D46-4AE4-AC9D-A12395710CE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9b8371328a4cc5e415f27e3783ff411bce9bef4d","datavalue":{"value":{"entity-type":"item","numeric-id":2380462,"id":"Q2380462"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2004085$D0C98044-8FFA-4689-B73E-4FEAB5C648FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7258a410b3b3ed4403fdf40150ca82055928d00d","datavalue":{"value":{"entity-type":"item","numeric-id":3512801,"id":"Q3512801"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2004085$A01E3167-D829-43F9-925E-7A40F01B3F3D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d1a52d109a946993fa4a3f0a29b8406147954b2","datavalue":{"value":{"entity-type":"item","numeric-id":4075485,"id":"Q4075485"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2004085$5F6409AE-E3B3-4057-8FE7-88C255F9BE4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b32538aaf080cca92b226203418f1c485553626","datavalue":{"value":{"entity-type":"item","numeric-id":3654480,"id":"Q3654480"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2004085$514883A5-C9CF-495B-B721-ED9D34A5140F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"259efd86a7a99439b0a8320367782e0e3a57951e","datavalue":{"value":"10.1016/J.DAM.2020.08.007","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2004085$6D319544-1F10-4811-9674-16EACF842EB8","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"090fbbb95de959636af03d75fdfa50d0d7a7f3a4","datavalue":{"value":{"entity-type":"item","numeric-id":2107754,"id":"Q2107754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"65a52b795e5abf28442ea780717e409b4b4b79f2","datavalue":{"value":{"amount":"+0.9302197694778442","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":"Q2004085$D1178739-5843-4CEB-86FB-E740A585CFF6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"91846c48c76dfd1d6cbb50640e771e2a2ca53ddb","datavalue":{"value":{"entity-type":"item","numeric-id":2768132,"id":"Q2768132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d412f3ebb16ff64aaf3f628c21d9408f5561eef5","datavalue":{"value":{"amount":"+0.8703829050064087","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":"Q2004085$0AB29A56-01A1-4F37-B9D5-C876A65E50CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"016b9b77d9fc6f50c26acbad784cbe57e1a9a2ce","datavalue":{"value":{"entity-type":"item","numeric-id":2032722,"id":"Q2032722"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"59786f488c3b7f4fce4b3d01cae9ad16fa818035","datavalue":{"value":{"amount":"+0.853003740310669","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":"Q2004085$BEF3AE21-0CA2-49C1-AE71-E72FCF2BE00A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5ab67eda3203c2c1a5fae9b339f37a4bce8b6d76","datavalue":{"value":{"entity-type":"item","numeric-id":2073194,"id":"Q2073194"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c08c57104c8027388763258d3c53164345db4c3d","datavalue":{"value":{"amount":"+0.8315032124519348","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":"Q2004085$8C7C54B3-8E0C-49A3-9C4C-6B7285344B1F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"53eda79c764ea257f8f3d430f5a1e3857ae03c3c","datavalue":{"value":{"entity-type":"item","numeric-id":1582071,"id":"Q1582071"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b168f5a9932b1bfb400d7248dbff1b97d5a19c0d","datavalue":{"value":{"amount":"+0.7953775525093079","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":"Q2004085$FC68D4A7-C0CF-42C1-80C8-29960A91FB45","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2004085","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2004085"}}}}}