{"entities":{"Q1363699":{"pageid":1374438,"ns":120,"title":"Item:Q1363699","lastrevid":46485456,"modified":"2025-12-24T21:42:27Z","type":"item","id":"Q1363699","labels":{"en":{"language":"en","value":"Clique neighborhoods and nearly chordal graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1047087"}},"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":"Q1363699$E0DB8871-F3E1-40C0-9B17-AA04DFC5B24D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a8663ab0df8d680875d22c362c35e8e6241b1486","datavalue":{"value":{"text":"Clique neighborhoods and nearly chordal graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1363699$90D39249-B77C-433D-AF50-DC7F6018A1D4","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"da14df98c5f0a972aa6084425ec5b11fae687adb","datavalue":{"value":"0880.05073","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1363699$135D9B05-B91E-411C-A276-20B057651670","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"233cb8d23f51f01f7250082632aef1b2f9256475","datavalue":{"value":"10.1016/S0012-365X(96)00028-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1363699$EFA42119-B423-4A94-8464-68A332DB8F05","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"703b1f79ea71713ba8c8eda07544b2290c123390","datavalue":{"value":{"entity-type":"item","numeric-id":376560,"id":"Q376560"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1363699$34E6B8DA-D847-47D4-9D12-D506A3F3BD53","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1363699$C64DF861-EB2C-424D-9336-8FB0545CF7E4","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e923552579303fe8b30d2a139bb2fde0734b1912","datavalue":{"value":{"time":"+1998-01-19T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1363699$9A879CAB-F1EB-44D9-8F1C-808470627CEE","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a48f035958c188f49e882dd411ba35372502a254","datavalue":{"value":"The families of maximal complete subgraphs (max-cliques) and of minimal vertex separators are studied. The second family consists of minimal vertex sets \\(S\\) for which there exist vertices \\(u\\), \\(v\\) such that every \\(u,v\\)-path contains a vertex in \\(S\\). It is a fundamental concept for the characterization of chordal graphs (the ``1-ekachordal'' graphs). Let \\(k_i(G)\\) denote the number of \\(i\\)-cliques contained in a graph \\(G\\) (hence \\(k_1(G)\\) is the number of vertices and \\(k_2(G)\\) the number of edges of \\(G\\)). Let \\(\\text{comp }G\\) denote the number of components in \\(G\\) and \\(\\text{char }G\\) the (Euler) characteristic \\(k_1(G)- k_2(G)+ k_3(G)-\\cdots\\). Further, the (clique) neighborhood \\(N(Q)\\) of a complete subgraph \\(Q\\) of a graph \\(G\\) is defined to be the subgraph induced by those vertices that are adjacent to every vertex of \\(Q\\). By using this concept, the two above-mentioned families are generalized to three families \\({\\mathfrak C}_1\\), \\({\\mathfrak C}_2\\), and \\({\\mathfrak C}_3\\).   When a neighborhood separator of \\(G\\) is defined to be a complete subgraph \\(Q\\) such that \\(N(Q)\\) is disconnected, then \\({\\mathfrak C}_2= {\\mathfrak C}_2(G)\\) is defined to be the multiset (a set with possibly repeated elements) consisting of all neighborhood separators of \\(G\\), with the multiplicity of \\(Q\\in{\\mathfrak C}_2\\) equal to \\(\\text{comp }N(Q)- 1\\). Let \\({\\mathfrak C}_3= {\\mathfrak C}_3(G)\\) be the multiset consisting of all complete subgraphs \\(Q\\) of \\(G\\) for which \\(\\text{comp }N(Q)> \\text{char }N(Q)\\), with the multiplicity of \\(Q\\in{\\mathfrak C}_3\\) equal to \\(\\text{comp }N(Q)-\\text{char } N(Q)\\). \\({\\mathfrak C}_1= {\\mathfrak C}_1(G)\\) is the family of all max-cliques of \\(G\\). In the case of chordal graphs, \\({\\mathfrak C}_2\\) is the family of minimal vertex separators, and \\({\\mathfrak C}_3= {\\mathfrak C}_1=\\varnothing\\).   The author investigates the so-called 2-ekachordal graph \\(G\\) which is an intersection graph of a family \\(\\{H_v\\mid v\\) a vertex of \\(G\\}\\) of induced subgraphs of a host \\(K_4\\)-free chordal graph \\(H\\) such that a given clique intersection condition and a given clique cover condition hold.   Section 2 shows that \\({\\mathfrak C}_2\\) and \\({\\mathfrak C}_3\\) play an important role for these graphs, and in Theorems 1 and 2 the meaning of \\({\\mathfrak C}_2\\) and \\({\\mathfrak C}_3\\) for 2-ekachordal graphs \\(G\\) is described. It is also shown that for such graphs \\(G\\) we have: (a) \\(\\text{char }G= \\text{comp }G\\) (Theorem 3), and (b) \\(c_1(G)- c_2(G)+ c_3(G)=\\text{comp }G\\) with \\(c_i=|{\\mathfrak C}_i(G)|\\) for \\(1\\leq i\\leq 3\\) (Theorem 4).   In Section 3, the role of \\({\\mathfrak C}_1\\), \\({\\mathfrak C}_2\\) and \\({\\mathfrak C}_3\\) for general graphs \\(G\\) is investigated. The author gets the following results: (a) Every graph \\(G\\) satisfies \\(c_1(G)- c_2(G)\\leq\\text{comp } G\\), with equality iff \\(G\\) is chordal (Theorem 5). (b) Every graph \\(G\\) satisfies \\(\\text{char }G\\leq c_2(G)- c_2(G)+ c_3(G)\\) (Theorem 6). (c) A necessary and sufficient condition for the equality in Theorem 6 is given (Theorem 7). From this follows that the equality holds for (at least) all 2-ekachordal graphs, all \\(K_4\\)-free graphs, and all planar graphs (Corollary 2).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1363699$16ABE07D-F6FE-4E78-9C0C-4B7D4D4AFBFD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1363699$33FB5104-A28B-4EB7-93CD-9CDA939339AA","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"71ef99e3b86cf625dc304bfad9eab35bdd76af72","datavalue":{"value":"1047087","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1363699$93DA7C2B-CF5E-4645-96C3-B40368A9FFB0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c89639778a113cbe54a2efcba7f98ccd79f62275","datavalue":{"value":"characterization","type":"string"},"datatype":"string"},"type":"statement","id":"Q1363699$7F3DB848-A653-4E43-BB8A-253C49B3EA8B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"73e241fa73d7c1967178d3e23e14ab11700a8635","datavalue":{"value":"neighborhood separator","type":"string"},"datatype":"string"},"type":"statement","id":"Q1363699$011FEF66-4278-41D3-A622-221442A4BFCE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9bc0d5058cf7773f67ff6548c4fa33edb07db16a","datavalue":{"value":"intersection graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1363699$5F3BAE86-BE2C-4DF5-8E9D-5616AD7206E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dae41303426e6695786e3a6d28699919bfeab34a","datavalue":{"value":"chordal graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1363699$AD47FE4A-91E7-4D56-BEBA-0088EE1A9747","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"08baab614f58f18056b00337698f0e127fe54ec2","datavalue":{"value":"clique intersection condition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1363699$FF628E86-FB93-459E-80CC-2A8556BB9C9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5aacf7f2a04cb9f3ea3cc7753637b871920549d1","datavalue":{"value":"clique cover condition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1363699$0CF779A7-EBC8-4173-9D6C-6490AA00AFBD","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":"Q1363699$3142592B-5327-4D39-9464-8888F7069531","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":"Q1363699$96A46E43-A80F-4D97-963D-45F18389779F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"cd8ac350c5bd2d5a17da8118cd84bc5cfa71ac65","datavalue":{"value":{"entity-type":"item","numeric-id":4288578,"id":"Q4288578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1363699$74578C04-E2DD-4550-A215-319AEF54C4DA","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":"Q1363699$BB29B4E7-1738-43E2-AF4D-FB00EE04395C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"19cb93c4705740808cc7f6f87f6408051d23b78c","datavalue":{"value":{"entity-type":"item","numeric-id":1313863,"id":"Q1313863"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1363699$C8FB1F9D-7AC9-4B11-AE11-627475F4724E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"99cc24ebd6edf6f508062e8d8f0c30333ede2920","datavalue":{"value":{"entity-type":"item","numeric-id":4309133,"id":"Q4309133"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1363699$6710F6A8-5950-4E45-97E5-4E209F22C9D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d5c2a08a834fa7f901b75781e36bc6c4605a6e2e","datavalue":{"value":{"entity-type":"item","numeric-id":4337344,"id":"Q4337344"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1363699$C64283F9-594A-4913-89DB-74712738D0B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7070132b910bc8411c9c2b720e41984bb799b200","datavalue":{"value":{"entity-type":"item","numeric-id":4173395,"id":"Q4173395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1363699$B63A44E7-CA76-4944-A117-74071A184E93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f15ffe5d7fcc7a148d30208be3c50de6dfd3aa8c","datavalue":{"value":{"entity-type":"item","numeric-id":1332411,"id":"Q1332411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1363699$C7B636D0-C6F1-4BC5-B608-73D65CA6BAA5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bf6ae0b3b9610778165b5d40f2c3e2cc0caa2d55","datavalue":{"value":{"entity-type":"item","numeric-id":1408522,"id":"Q1408522"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b79a27d44ae7ca948ce6363ed1765dd2df1fda5c","datavalue":{"value":{"amount":"+0.7715407609939575","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":"Q1363699$A79FABCB-DC63-4FDE-A9C2-AC685879D179","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5f1e30098ca8394ea61e235001091629f2a3bd76","datavalue":{"value":{"entity-type":"item","numeric-id":2365702,"id":"Q2365702"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7725754ef2ade3a5e004af2877bfff52d58dd92c","datavalue":{"value":{"amount":"+0.761846125125885","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":"Q1363699$61926F3A-C06B-4B61-8C4B-C8B1D28B1689","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ebf677f6100ac1d8a5d979f5e4486f820639cf6c","datavalue":{"value":{"entity-type":"item","numeric-id":1081622,"id":"Q1081622"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"09e81466e2c35c9e3d3c8983e538aaaddcca5be4","datavalue":{"value":{"amount":"+0.7487437725067139","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":"Q1363699$79F846A0-AC82-4D90-81F5-7963A4E7E969","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a6dc83c3f0f2b7af4389ec4999ec4bbee0583b0d","datavalue":{"value":{"entity-type":"item","numeric-id":5957745,"id":"Q5957745"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"916962db99637bb22422dd1f02a34888f3c315d2","datavalue":{"value":{"amount":"+0.7475600242614746","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":"Q1363699$118951AC-9C49-4040-A01D-86991E3BF0C9","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1363699","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1363699"}}}}}