{"entities":{"Q1106858":{"pageid":1117607,"ns":120,"title":"Item:Q1106858","lastrevid":49194499,"modified":"2026-01-06T18:06:12Z","type":"item","id":"Q1106858","labels":{"en":{"language":"en","value":"On the stable set polytope of a series-parallel graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4063122"}},"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":"Q1106858$9983F6FB-58EE-4202-B174-1A277F5030DB","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"8938bfcff292125f72e177e3e12b69f446057712","datavalue":{"value":{"text":"On the stable set polytope of a series-parallel graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1106858$8D898A85-81AF-43B9-903E-6A543AFADF4E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"bb08f54377f7b632c79ac6dff0edfbf36f8a5c97","datavalue":{"value":"0652.05029","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106858$615EDFBF-F5FA-48C5-A922-7CDB274C48D5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f849da7bf4038eea97d8d0842cd5f4ff0b9594a8","datavalue":{"value":"10.1007/BF01580723","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106858$13490582-34E0-424C-A719-11BC39372C94","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"99da72655942e9c2c9c01874c026b7cceeb02de6","datavalue":{"value":{"entity-type":"item","numeric-id":163006,"id":"Q163006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106858$47BD9C33-25A2-4E35-BBF2-F52B8EE57553","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1106858$218CD236-A05F-4365-BB7A-E62D816CDEDA","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"92849522965d0d95a7acd906abe24ae1039f051a","datavalue":{"value":"Let \\(G=(V,E)\\) be a graph. A stable (independent) set in \\(G\\) is a set of nodes, no two of which are adjacent. Given a stable set \\(S\\) of \\(G\\), the incidence vector of \\(S\\), \\(x^ s\\) is the 0-1 vector such that \\(x^ s(u)=1\\) if \\(u\\in S\\) and \\(x^ s(u)=0\\) if not. The stable set polytope of \\(G\\), denoted by \\(P(G)\\), is the convex hull of the incidence vectors of all the stable sets of \\(G\\).    If \\(G=(V,E)\\) is a graph, then each incidence vector of a stable set of \\(G\\) satisfies the inequalities  \\[  \\begin{cases} 0\\leq x(u)\\leq 1 \\quad&\\text{for all }u\\in V, \\\\ x(u) + x(v)\\leq 1 \\quad&\\text{for all }uv\\in E, \\\\ \\sum_{u\\in C} x(u) \\leq \\frac{| C| -1}{2} \\quad&\\text{for all induced cycles \\(C\\) of \\(G\\) such that \\(| C|\\) is odd.} \\end{cases} \\tag{1}  \\]  In 1975, Chvatal conjectured that (1) defines the polytope \\(P(G)\\) when \\(G\\) is series-parallel. This conjecture has been proved by J. P. Uhry and Boulala in 1979 using LP-duality, and independently by Clamcy in 1977.    In this note we give a short proof of Chvatal's conjecture. Given a graph \\(G=(V,E)\\), if \\(ax \\leq \\alpha\\) defines a facet of \\(P(G)\\) (i.e. a face of dimension \\(| V| -1)\\) and \\(G_ a\\) is the graph induced by it, we show that:    (i) If \\(G_ a\\) contains a path \\((v_0, v_1, \\ldots, v_{p+1})\\) whose intern al nodes \\(v_1, \\ldots, v_ p\\) are of degree two, then \\(a(v_1)= \\ldots =a(v_ p)\\).   (ii) If \\(u\\), \\(v\\) are two nodes of \\(G_ a\\), then at most one path in \\(G_ a\\) wh ich joins \\(u\\) and \\(v\\) can have all internal nodes of degree two.    (iii) \\(G_ a\\) does not contain a node of degree one.    Using this, we prove that if \\(G\\) is a series-parallel graph, then any facet defining inequality of \\(P(G)\\) is of the forms described in (1).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106858$D38EAA53-3242-4F1C-9D5D-55A46D2051B8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106858$B0548132-5104-4D1E-ACDB-DF56F637C757","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c62d6cfba834d796c26ce7140adfe442abe29356","datavalue":{"value":"4063122","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106858$25C0B409-141E-43C7-ACEB-27DE696444D2","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"80b1491c8684cebef940f5fdf61a7b6168399e1c","datavalue":{"value":"facets of polyhedra","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106858$FCF1913E-5F4D-43E6-852B-AA276F6451A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3b9500328a0a0a93ae778cd33d5ecd620868459d","datavalue":{"value":"stable set polytope","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106858$5A82D75C-0BE4-4481-AA79-A97803FEBFAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"cb191028560f8580185d25fb1e0694b4ee05dbf4","datavalue":{"value":"series-parallel graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1106858$A25BFA37-BFA3-4BAA-9C7A-FF96EA6C5B37","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d752a8c8ec156de44a5b16b085911c20996c2330","datavalue":{"value":{"entity-type":"item","numeric-id":1070247,"id":"Q1070247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106858$E204F052-95FA-4361-8C46-EACADA18CB53","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":"Q1106858$79D17C38-3640-4E13-92FD-E3530E28FC3D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e9b4b0263bf157bc56ee9f4278362c292a571a65","datavalue":{"value":{"entity-type":"item","numeric-id":1147168,"id":"Q1147168"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106858$8E1ED5C8-4D8B-480B-A04A-3383E97DD727","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b3ecc4ed854f4c2fb93ed2e8327283eb9cc15cf0","datavalue":{"value":{"entity-type":"item","numeric-id":1393418,"id":"Q1393418"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106858$232DC278-A3F0-4828-9BB1-8CB53D9539D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df25916ae88cfd882e8cb6b5b5569c6957043ab0","datavalue":{"value":{"entity-type":"item","numeric-id":2394739,"id":"Q2394739"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106858$20F11F58-7AF7-40EA-84C6-C850C96B3870","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2bf25153ab80bc4bc546912fe83f90a99c1cd869","datavalue":{"value":{"entity-type":"item","numeric-id":1100483,"id":"Q1100483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106858$D7307868-A79F-440E-862E-1EB20A0851BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"45412ad54a9b259c5451ea01244192b9b86a0cfb","datavalue":{"value":{"entity-type":"item","numeric-id":799701,"id":"Q799701"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1106858$20E90056-7C29-4B12-878E-7CA1190891B6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e1ccef958657add364c790709bed2fcd7848864c","datavalue":{"value":"https://doi.org/10.1007/bf01580723","type":"string"},"datatype":"url"},"type":"statement","id":"Q1106858$D3A22995-9DFC-4EF3-AB37-D70EFC8920DB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"2c35193b2a24300a9b510d4c055ba78ce551eaa7","datavalue":{"value":"W2050692400","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1106858$E0889043-85C6-4766-AB26-F0FEAE630FE4","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bb576cc963e74bbb680ba318680948c99ffecc99","datavalue":{"value":{"entity-type":"item","numeric-id":4307045,"id":"Q4307045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aca57f54e768944dbcec608a9bbdfeeb3b136613","datavalue":{"value":{"amount":"+0.8207401037216187","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":"Q1106858$92E719E5-F303-4AB5-BFB4-1ED5350E22C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8a18f3066d988d49d0fda729b272ecd9522acfc7","datavalue":{"value":{"entity-type":"item","numeric-id":1751117,"id":"Q1751117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a7d89ffdb5bde1c86bf6edd9b0023d9b1bca8110","datavalue":{"value":{"amount":"+0.8044800758361816","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":"Q1106858$D8D05880-D59E-4B79-8012-C39E8D984E5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9b5207cece962fcd8c95d1bfb1f3ea1cb7f466be","datavalue":{"value":{"entity-type":"item","numeric-id":1591354,"id":"Q1591354"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"91b678550fedeee87a88df301e437b77baadce08","datavalue":{"value":{"amount":"+0.7957879304885864","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":"Q1106858$5C5EBA93-21C0-48D6-BF39-D69270B71B83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"340c83e2cc408ffced9245266592baff4eff288a","datavalue":{"value":{"entity-type":"item","numeric-id":3762334,"id":"Q3762334"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cfb7a07c368b4461226a97e198377cee987f1d9c","datavalue":{"value":{"amount":"+0.7928755283355713","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":"Q1106858$E5F1645D-4B6A-4F02-9056-B2ACC4E065C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2091a2d86a0b733cbbe741eb1f8675084a0c2dc8","datavalue":{"value":{"entity-type":"item","numeric-id":1373764,"id":"Q1373764"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"47e66d0401781d2348ba1755efd918d09b9d8098","datavalue":{"value":{"amount":"+0.7839540839195251","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":"Q1106858$30156854-91D5-439C-B058-490803076171","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1106858","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1106858"}}}}}