{"entities":{"Q1863531":{"pageid":1874273,"ns":120,"title":"Item:Q1863531","lastrevid":71014464,"modified":"2026-04-13T18:55:03Z","type":"item","id":"Q1863531","labels":{"en":{"language":"en","value":"A discrete nodal domain theorem for trees"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1880035"}},"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":"Q1863531$3EFBDCF7-2999-450F-9662-267B38145C99","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9c498caf8c53f7170e138f6e925cd471b0718b28","datavalue":{"value":{"text":"A discrete nodal domain theorem for trees","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1863531$0D7EED20-D331-4C32-B3A1-E1F739374925","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2a9d498818c9b79751ab74b43ea3cff4390c61e1","datavalue":{"value":"1012.05114","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1863531$E878393F-1088-4A83-B33D-BD1C8966BE17","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"bf7bb5bd3f4f297c60e92e318e9f5129da27a5c3","datavalue":{"value":"10.1016/S0024-3795(02)00451-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1863531$C4ED86FD-963E-4F4B-9667-38FCD8CDA2B3","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"8de031de05325b44570d0c47c3ec8813873d565c","datavalue":{"value":{"entity-type":"item","numeric-id":92813,"id":"Q92813"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1863531$479789A7-3474-4D8E-B820-68014DBE469A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"866f517bddd8ff45e5b81e4409969a3f73622ea5","datavalue":{"value":{"time":"+2003-03-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1863531$95776A82-C0E6-49F8-99EB-3CBE14D196F3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a8a6b1472c92389d629435b5a6fcbf22ad3796c9","datavalue":{"value":"consider a graph \\(G\\) on vertices \\(1,2,\\dots,n\\) and a real vector \\((x_1,x_2,\\dots,x_n)\\). A positive (negative) sign graph is a maximal connected subgraph of \\(G\\) on vertices \\(v\\) with \\(x_v>0\\) (\\(x_v<0\\)). Sign graphs are also called nodal domains. Their number is denoted by \\(\\eta(x)\\). Let \\(A\\) be a generalized Laplacian of \\(G\\), that is \\(A\\) is a symmetric \\(n \\times n\\) matrix and its entries are negative for adjacent vertices and zero for distinct non-adjacent vertices. Consider the eigenvalues \\(\\lambda_1 \\leq \\lambda_2 \\leq \\dots \\leq \\lambda_n\\) of \\(A\\). \\textit{E. B. Davies} et al.\\ [Linear Algebra Appl.\\ 336, 51-60 (2001; Zbl 0990.05093)] proved that \\(\\eta(y) \\leq k+r-1\\) for all eigenvectors \\(y\\) of \\(A\\) corresponding with an eigenvalue \\(\\lambda_k\\) of multiplicity \\(r\\). This discrete nodal domain theorem is strengthened for trees. If \\(G\\) is a tree and \\(y\\) is an eigenvector without a vanishing coordinate, then the corresponding eigenvalue \\(\\lambda_k\\) is simple and \\(\\eta(y)=k\\). For multiple eigenvalues more complicated bounds exist. Given a generalized Laplacian \\(A\\) of a tree and an eigenvalue \\(\\lambda\\) of \\(A\\) with multiplicity at least \\(2\\), a corresponding eigenvector \\(y\\) with maximal \\(\\eta(y)\\) can be found in time \\(O(n^2)\\). Deciding the corresponding minimization problem is NP-complete.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1863531$75B9E158-3B99-4B09-9713-378601D63D06","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"898109ac7e401de8fce76101fe27418b7afd5158","datavalue":{"value":"05C50","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1863531$6EFF7379-A2E8-4348-ADFD-E991F9F304AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d5da87a72c21717089feda882f568938059a9d84","datavalue":{"value":"05C05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1863531$82D8B031-BBFF-4DA0-A9CC-669BB02840E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b2773d305bb22ed635d748bc939993c6750608ab","datavalue":{"value":"05C22","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1863531$36CBAE52-DC5B-4579-BB86-89C8975F92B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"344f62a15ccd40e690364bd758985e8313f47f4a","datavalue":{"value":"68R10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1863531$50AD4F23-E6AB-4F44-855C-6BFF133A3F0D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6b72dc86b40f9e5d094a859b390064e95bcebea8","datavalue":{"value":"1880035","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1863531$168EED64-E74A-4EE3-8903-5A930B06A77B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9eea8eafae916b12cf6dfee9b921b3b01cd46172","datavalue":{"value":"discrete nodal domain theorem","type":"string"},"datatype":"string"},"type":"statement","id":"Q1863531$9432EE86-D75E-4473-BE8B-22A3A332A60B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"534805fa6153b1b3786edcd60407ef0861005e9a","datavalue":{"value":"tree","type":"string"},"datatype":"string"},"type":"statement","id":"Q1863531$9CCC77EE-A1E3-483A-8F16-DFD28123CDC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4ec93a15c9a7618c2aa9a194406bfb91d1160d49","datavalue":{"value":"sign graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1863531$2BAF4790-9A86-4724-9C92-1FEC2A91CA4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e4477d41489674f98c1165dfbc7009a4fbc3e7d1","datavalue":{"value":"graph Laplacian","type":"string"},"datatype":"string"},"type":"statement","id":"Q1863531$7550BED9-6688-42C1-9506-D9584DADFD42","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e1a5f15c0371cb136e7a83c39057f009821c0c2c","datavalue":{"value":{"entity-type":"item","numeric-id":405056,"id":"Q405056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1863531$38493910-F6CF-4889-A74F-A1E051CA8E6D","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":"Q1863531$9FDC3076-18F0-4AA0-ADEC-2CC5F04DC7A2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f6d472627728e344ffea6afbd6fed04594a534e4","datavalue":{"value":{"entity-type":"item","numeric-id":5954844,"id":"Q5954844"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1863531$37AD73D4-AFE2-4A6E-930E-CDBB2B1AE1B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"129f8584a55eb7817c20122932dec4fb7925cf24","datavalue":{"value":{"entity-type":"item","numeric-id":802573,"id":"Q802573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1863531$67157B2F-EF0B-4905-8B8A-8E7B3EBCCEF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b819e50e8bc452177ad96cc91118a110c2848ce","datavalue":{"value":{"entity-type":"item","numeric-id":4088941,"id":"Q4088941"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1863531$C32EDB5D-3B70-4696-89F1-639D95AF2B1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"836ad2a04f82225da478ca9f694f5cd99360b315","datavalue":{"value":{"entity-type":"item","numeric-id":4198056,"id":"Q4198056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1863531$F6686857-D29E-4369-870D-6B36EA47ABED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9e0011569afaab0aefe72ed32ddccc6d08e1a511","datavalue":{"value":{"entity-type":"item","numeric-id":1118004,"id":"Q1118004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1863531$6936B892-99FE-4C7A-A4A3-AACF1E7B77B7","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b0bed751c7fbe6ebe6dab90bd5169b8ca4c7d2cc","datavalue":{"value":{"entity-type":"item","numeric-id":5469422,"id":"Q5469422"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5cef764ff8c1e9fa6c1f5aab8d88e6bf77bef383","datavalue":{"value":{"amount":"+0.82435536","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1863531$5F2A3008-E757-401E-8F3F-E47D5B816AC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"47f051f1f027dd365d5c969991f0694fc97e5b66","datavalue":{"value":{"entity-type":"item","numeric-id":1886532,"id":"Q1886532"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a44934620e9bd2c847bfb2d43acd69b6f2695e4a","datavalue":{"value":{"amount":"+0.82398856","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1863531$DD36224B-2C0A-429A-9C53-5E36BD229073","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a8fb9aa66cc6cdb7e85818b0688882744923fad4","datavalue":{"value":{"entity-type":"item","numeric-id":1688867,"id":"Q1688867"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6fde778063cf7275208f418f022128a27fad3d02","datavalue":{"value":{"amount":"+0.78702915","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1863531$2CBE8FA1-8CB7-4565-B9C4-CA46D7CD5794","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c59e03bc4750b5c7a043b70883542bf9aca1356d","datavalue":{"value":{"entity-type":"item","numeric-id":1124888,"id":"Q1124888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c6cf3ac3a39bee255507bc7459a433cb2b3c292f","datavalue":{"value":{"amount":"+0.78537184","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1863531$B25015AC-E328-4F15-8DA2-88ADF54B0254","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"109487bc5955339595443e9ad697ba5afaaccd54","datavalue":{"value":{"entity-type":"item","numeric-id":2789408,"id":"Q2789408"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c8979363865f982803a09c598d3716344bf7e4b6","datavalue":{"value":{"amount":"+0.76925826","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1863531$E2246D00-7FF4-4B3B-8E02-8DCC4E5FCAD8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5595bd33777a3f3d7f3800d80c016b77a8d8fd92","datavalue":{"value":{"entity-type":"item","numeric-id":432729,"id":"Q432729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8ad6a3f465b935d5433e1a7bb7c30ff3793758c3","datavalue":{"value":{"amount":"+0.75849366","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1863531$75D5E2C8-98B3-418F-BC59-16DF099F0FAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b94d69e26b169c6aed886a4b126b29d7c25c2b7f","datavalue":{"value":{"entity-type":"item","numeric-id":4710059,"id":"Q4710059"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d086cee9768a2d08f818b0f4e2447f05f44ae250","datavalue":{"value":{"amount":"+0.75823295","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1863531$A0B0CF41-B02A-426D-A53D-BDD8CC870A7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8bbbbdf560dbfa5357417c802e9d6b26a1f63d2d","datavalue":{"value":{"entity-type":"item","numeric-id":742633,"id":"Q742633"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f0d69f68739985967306231bda5cd69d3d82cfac","datavalue":{"value":{"amount":"+0.7570833","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1863531$57036FB0-957C-41D7-A1E4-9115635D433E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"382945760fd6288e0505da4da51cf9cf2105b399","datavalue":{"value":{"entity-type":"item","numeric-id":6039199,"id":"Q6039199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7abd68e37c6d09a9d405112f3610b04c611d7b5c","datavalue":{"value":{"amount":"+0.7556448","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1863531$9B7BD378-9FBD-44CD-A792-707384373078","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"83c775ac34607deba5b298ab8c838eab9b5e7269","datavalue":{"value":{"entity-type":"item","numeric-id":2375849,"id":"Q2375849"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c5b691668c9c019c3992677416623407fd640fb4","datavalue":{"value":{"amount":"+0.7551865","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1863531$C9ABDEB9-6075-4AFC-9FE0-CC46D666D161","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A discrete nodal domain theorem for trees","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_discrete_nodal_domain_theorem_for_trees"}}}}}