{"entities":{"Q1302141":{"pageid":1312891,"ns":120,"title":"Item:Q1302141","lastrevid":46666344,"modified":"2025-12-25T09:02:35Z","type":"item","id":"Q1302141","labels":{"en":{"language":"en","value":"On the \\(p\\)-connectedness of graphs---a survey"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1340623"}},"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":"Q1302141$7F8695F0-56F6-47D3-B83F-267320AFDEF4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d3f863d0074df45280f23ace310b2225604c51ff","datavalue":{"value":{"text":"On the \\(p\\)-connectedness of graphs---a survey","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1302141$2C143AE7-A62F-419A-8C60-C2B0A335AD17","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"e3cbf40e526b7158bd16811e28012f3bc5335bf3","datavalue":{"value":"0947.05079","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1302141$86E496DE-5300-4C14-A04A-76A2A2E76A25","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"774b918c0ead020763e6006391ca7223444c11be","datavalue":{"value":"10.1016/S0166-218X(99)00062-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1302141$630206B7-2D68-4568-BC43-2E65B7D85CB1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"206b3ec8cbaf149080c58314ec18c3b633966649","datavalue":{"value":{"entity-type":"item","numeric-id":190504,"id":"Q190504"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1302141$527512C7-EA5C-47D2-B13B-CBAC0B5CF9A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3e7020a54266d4b2ab3b7f83a2814036c1ab56ec","datavalue":{"value":{"entity-type":"item","numeric-id":185063,"id":"Q185063"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1302141$5D876DF2-BF4E-4E6E-870E-342D5358FF14","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":"Q1302141$1D52F944-D451-4C1D-9C7D-BB2D3DC252DD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"fb9b4aa9d0b203b9e99aed58aa82b9d85ad6a7f8","datavalue":{"value":{"time":"+1999-12-12T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1302141$98200D41-8796-425F-8F56-66C5BD48CE60","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f1bca67bd7c383107742ef00b83be91a12342b40","datavalue":{"value":"A graph \\(G\\) is called \\(p\\)-connected if every partition \\(V(G)= V_1\\cup V_2\\) is crossed by some \\(P_4\\in{\\mathfrak P}_4(G)\\), the set of induced 4-vertex paths in \\(G\\). Every graph decomposes into maximal \\(p\\)-connected induced subgraphs, the \\(p\\)-components. An important role play separable \\(p\\)-connected graphs which by definition allow a (then unique) decomposition \\(V(G)= V_1\\cup V_2\\), where all \\(V_1\\), \\(V_2\\) crossing elements of \\({\\mathfrak P}_4(G)\\) have exactly their end vertices in \\(V_2\\). The authors first recall a basic structure theorem for arbitrary graphs and its relation to the ``primeval'' decomposition into homogeneous sets. In sections 4 and 5 the analogy between \\(p\\)-connectedness and connectivity is stressed: \\(p\\)-chains, \\(p\\)-connected vertex pairs and \\(p\\)-articulations are addressed. In sections 6 and 7 reconstruction and decomposition of \\(p\\)-connected graphs are discussed. The considerations involve homogeneous and separable-homogeneous subsets of \\(V(G)\\) and lead (in section 8) to a refinement of the primeval decomposition. These refinements are related to certain graph operations and so-called \\(p\\)-trees. In section 9 on \\(p\\)-trees and \\(p\\)-forests are presented: various characterizations of \\(p\\)-trees and general classes of \\(p\\)-forests are described: for example cographs and \\(P_4\\)-reducible graphs are \\(p\\)-forests. Section 10 is devoted to graphs \\(G\\) with small \\(|{\\mathfrak P}_4(G)|\\). The last section addresses algorithmic aspects, especially linear-time algorithms for the recognition and the computation of graph parameters of certain graph classes.   Additional reference: \\textit{A. Brandst\u00e4dt}, \\textit{Van Bang Le} and \\textit{J. P. Spinrad} [Graph classes: a survey (SIAM Monographs on Discrete Mathematics and Applications, Philadelphia, PA) (1999; Zbl 0919.05001)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q1302141$28DAC686-F348-4D55-9FD1-C11323C0435C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"e35cfda1c439de499de525a8a9009114d934bb37","datavalue":{"value":"05C99","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1302141$FFBA64C3-163A-43C6-975E-0203C281B7F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1302141$B862723F-F79E-473D-98D4-E38FE1FFD48E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5106252eb72617afc052c075699a4fbf786bbc66","datavalue":{"value":"05-02","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1302141$603F634F-0699-4ACE-A78B-0E6564F4E3EB","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f6b84be4fb7d0ea120c0d481efce90bc85ac5d77","datavalue":{"value":"1340623","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1302141$A420839F-53BC-4667-B5E4-1387D20A6070","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e41fb471c5632503b8716f23269ac7a1a49e160e","datavalue":{"value":"partition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1302141$C2FF1A2A-A100-4360-9D8A-E58D4058475F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"aa1e525d54206328a886fec979ed8544cdef4e48","datavalue":{"value":"\\(p\\)-components","type":"string"},"datatype":"string"},"type":"statement","id":"Q1302141$01011EFE-5E33-4614-BA24-89014930DCFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3058f647041da6bec8a2db92f2579e20d4702f72","datavalue":{"value":"\\(p\\)-connected graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1302141$4C3A1206-41AF-4ECA-99C0-198C3ED947A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"615f2a3773e3a9a3bad386a540fbc6c58cfa22ee","datavalue":{"value":"decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1302141$094F122E-CE42-4B60-B810-4D8C575CA6ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2487cac0456b181f1568f080f3f08b9aea30edd0","datavalue":{"value":"end vertices","type":"string"},"datatype":"string"},"type":"statement","id":"Q1302141$74A0ED1D-9E83-4844-8DCC-2041482273E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d6956089deb76e31e6b0559c31a59db3aefd8d9f","datavalue":{"value":"\\(p\\)-connectedness","type":"string"},"datatype":"string"},"type":"statement","id":"Q1302141$E0491E2A-5B57-4C6A-A707-476667B529F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"eba61a8abead030333429495c832d733d94064bd","datavalue":{"value":"connectivity","type":"string"},"datatype":"string"},"type":"statement","id":"Q1302141$B8CA6C45-215E-4CE9-8F52-45971957B9E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"20cb5f900346d6218be2e7d1c87b3ca77a3b494d","datavalue":{"value":"reconstruction","type":"string"},"datatype":"string"},"type":"statement","id":"Q1302141$C7DA21BA-72D0-4AD3-8E3C-E98D394FD11C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7734f1fbb64ec3612cffb99160c3d129513fc23a","datavalue":{"value":"graph operations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1302141$8BD76FB1-B8D1-4CE8-94D6-1C4121345092","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1c06f0e53c6c5fbb7dd3a27c773a95e9573990cd","datavalue":{"value":"characterizations","type":"string"},"datatype":"string"},"type":"statement","id":"Q1302141$98F94860-F482-4A95-9BAD-6455CAFAE767","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7250963987d7e4c99272889381793742a1498efc","datavalue":{"value":"linear-time algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q1302141$7D103626-950A-4AB0-B820-11ECD37D3A7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8aa823381996fcc0ccd3a2cba10b758f14d14704","datavalue":{"value":"graph classes","type":"string"},"datatype":"string"},"type":"statement","id":"Q1302141$99BDBFD3-2734-4C00-8298-45328F1C452D","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"433fb6cae617f41cffa9072777c6627719427b87","datavalue":{"value":{"entity-type":"item","numeric-id":968421,"id":"Q968421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1302141$5F80E7F3-2EF0-4480-BDB8-681CEA4732EF","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":"Q1302141$740B009E-C311-4F98-BCE0-22FD25951E4E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"3b7d2b977c816cf89da9209c50e5a4c0b66b54e4","datavalue":{"value":"https://doi.org/10.1016/s0166-218x(99)00062-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q1302141$3D32B5D5-17AF-4AE7-A3E5-7F3C5A0F6C27","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"2108a97e607d2e49cb2fd92fc40ceac72de666fa","datavalue":{"value":"W2077462389","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1302141$F2E4423C-6829-4A3B-B2F8-890BBC023D34","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"55e3037ee361edd0c0d352f50ad04f1cbb92a001","datavalue":{"value":{"entity-type":"item","numeric-id":1584426,"id":"Q1584426"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"36bc3d70b60729e5583b29955f68adcba0db3af9","datavalue":{"value":{"amount":"+0.8455618023872375","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":"Q1302141$9203E8DA-BEB6-45D3-9B0F-02DC5E024B70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c268bcd3fc809a7d0301b97ca3a159fbb02678ed","datavalue":{"value":{"entity-type":"item","numeric-id":1962050,"id":"Q1962050"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2faa500c3e039f5e6a3a6b8b46965174587d2282","datavalue":{"value":{"amount":"+0.8305651545524597","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":"Q1302141$3D1CD574-1A5A-4B9E-AB09-012BDE37D4BA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8a929e682bc117ba375db7df810d68de6e37124e","datavalue":{"value":{"entity-type":"item","numeric-id":4281643,"id":"Q4281643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3fa5692898e74d25c2e879ec24bbcb93992ea07d","datavalue":{"value":{"amount":"+0.8283750414848328","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":"Q1302141$12DB65D4-1552-471A-8CDE-EEBEA16F7421","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1302141","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1302141"}}}}}