{"entities":{"Q5931414":{"pageid":8108216,"ns":120,"title":"Item:Q5931414","lastrevid":41913816,"modified":"2025-05-15T08:03:52Z","type":"item","id":"Q5931414","labels":{"en":{"language":"en","value":"Stable 2-pairs and \\((X,Y)\\)-intersection graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1591066"}},"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":"Q5931414$4894DAA8-66BA-4D02-968B-F2087472392A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9d816aa2dcd9359a1cbc3a40f0f8f9fb75ea8d21","datavalue":{"value":{"text":"Stable 2-pairs and \\((X,Y)\\)-intersection graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5931414$D54E1AA8-A8E1-4A24-9EC2-AB5755E1BCDF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"60834d6c0d136ce274f1392eb80ffb9573935e6c","datavalue":{"value":"0974.05066","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5931414$F4F0DEEB-88B3-4D38-B3DF-721D2ABEB36F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7a13778d7d87f4577e70d932c7da3fada9d644bc","datavalue":{"value":"10.1016/S0012-365X(00)00075-3","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5931414$FC3826EB-2DC0-48A8-BB2F-CD5400D57221","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f00237d5739b07662cb51e9e957100249e47b2d2","datavalue":{"value":{"entity-type":"item","numeric-id":175508,"id":"Q175508"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5931414$2B710E16-261B-4CBA-9F56-6835D846BBD6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"eac3bc3b952de30e0dbd044a5b978d4bbca81a36","datavalue":{"value":{"entity-type":"item","numeric-id":1070246,"id":"Q1070246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5931414$36FD6673-FC30-4F2C-B71D-DE0238EFCBEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d176ad615a4e6a7168d3f60eb001c162327a80ae","datavalue":{"value":{"entity-type":"item","numeric-id":175510,"id":"Q175510"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5931414$D74C5493-E93E-4131-9B0F-9B68025157AD","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":"Q5931414$F57CAA90-C952-4BE7-B7D6-2340C4D709F9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"763e2fac54cd7102c0b681a36ae0f081948e4e0f","datavalue":{"value":{"time":"+2001-07-05T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5931414$A3667E54-CC48-4E9C-AF14-37E3679F1E5A","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":"Q5931414$332B96E4-97B3-445B-9DA0-B5CFCC168982","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5931414$C5C72466-49D9-4CFF-B6AD-BC2A9643BB6D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"8d6f1c1e897582a10ab15cd338b804fadf49e278","datavalue":{"value":"1591066","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5931414$D81DB4B0-1BA7-4F14-A70F-7F8E82EEC38E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3e59318472d6bda2a21811f1de69f55dbd86e59d","datavalue":{"value":"stable graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q5931414$36FC16F8-753F-4B56-8CCA-9B6276552B7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ba1f0068f5497654bb5d0e0ec4b40f12d4d645ab","datavalue":{"value":"generator","type":"string"},"datatype":"string"},"type":"statement","id":"Q5931414$466B717B-19A0-4D8D-A9B6-A3B43EB0A798","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9bc0d5058cf7773f67ff6548c4fa33edb07db16a","datavalue":{"value":"intersection graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q5931414$D9890195-235B-4A6B-8657-4F13049BAA6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3f4bc5ef64b80473f2dd853aa845c54c1eb0ce36","datavalue":{"value":"induced subgraphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q5931414$C3AA0A79-40B4-47E1-9827-1DBB17CD2607","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3b7eadc27ce41b0d93dbcecf28392dc785f9b950","datavalue":{"value":"compact 2-pair","type":"string"},"datatype":"string"},"type":"statement","id":"Q5931414$18A8A945-42E6-49FE-9369-6EB60FAB869B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"34783be7cb07be74f453b9d5a8761bddb5dcf0b1","datavalue":{"value":"line graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q5931414$775AEC1F-947E-4C1D-B609-CEDC7565781B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"34b44e7b40021effdee26093512bde7058814281","datavalue":{"value":"stability","type":"string"},"datatype":"string"},"type":"statement","id":"Q5931414$FD0ED55C-1832-4153-9A7F-1DEB8F359052","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"07dbf5a9d0ef4cb331c189b63c8c2eca9d331fe1","datavalue":{"value":"stable 2-pairs","type":"string"},"datatype":"string"},"type":"statement","id":"Q5931414$72F9679A-9CF4-4C45-8148-6FF27422F270","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":"Q5931414$BC8FBB73-8EF5-41B6-BEF6-2A608436DBDB","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"d9aec4ae73d16833f00d966e138a9b65b3a8662a","datavalue":{"value":"Q127814225","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5931414$F9B89EBB-F117-433A-8A4B-01B524277D61","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"52d557c061b85fc7c9efb70bd20a9a2cf1584cc1","datavalue":{"value":"https://doi.org/10.1016/s0012-365x(00)00075-3","type":"string"},"datatype":"url"},"type":"statement","id":"Q5931414$3E04AD94-D35E-4856-AF37-285355AB1443","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"4cccf2fa3db33ff89b3b1b6c7a093f51c7135b1c","datavalue":{"value":"W2042880596","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5931414$638A8BF1-E551-43A6-AFA5-D7A6BE958CE2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"59a85b77816323778f2e0032a5cfc8e21ed8fa76","datavalue":{"value":{"entity-type":"item","numeric-id":2672447,"id":"Q2672447"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3cbe94981f20d50191787d4d13fb4a4c121efc19","datavalue":{"value":{"amount":"+0.89128923","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":"Q5931414$4384103E-329A-4041-9B27-AA47B149D3CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5a63afb0f1755e9c924eec9d085d6b1b642d2bf4","datavalue":{"value":{"entity-type":"item","numeric-id":5919634,"id":"Q5919634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aa65f796c90bd7c27d0d9eb6ec71ccbed79b8474","datavalue":{"value":{"amount":"+0.8749568","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":"Q5931414$012CDBA0-DB4A-4CBB-98EE-20E4D1DA50D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"651a4de24b21f1802f78bcc35c4617d3400c45b9","datavalue":{"value":{"entity-type":"item","numeric-id":5919053,"id":"Q5919053"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aa65f796c90bd7c27d0d9eb6ec71ccbed79b8474","datavalue":{"value":{"amount":"+0.8749568","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":"Q5931414$A5D1EBC2-A041-4B50-B3D5-ACC093827B08","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e9243cae78287c288136a905b734a600f4fcab81","datavalue":{"value":{"entity-type":"item","numeric-id":2315571,"id":"Q2315571"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ae1f4ce20e46b749f709426c607c7a7849389884","datavalue":{"value":{"amount":"+0.87396336","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":"Q5931414$E3716330-9355-4EFF-BF93-13CE21711DD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ccc2c9dfb243ff57f174f5b36d982bc1a441e093","datavalue":{"value":{"entity-type":"item","numeric-id":2520774,"id":"Q2520774"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cddd7b6cddd78235961f903c75769bb768646fdf","datavalue":{"value":{"amount":"+0.86978626","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":"Q5931414$6EE0D2C8-EEB0-4CD4-A485-565332674666","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5d0189d4e6f2703893a96d5d434393ef02b0c0ca","datavalue":{"value":{"entity-type":"item","numeric-id":1853063,"id":"Q1853063"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"11fd9dd5f1f18509c553a64b86e086a201abdd9f","datavalue":{"value":{"amount":"+0.8674094","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":"Q5931414$30651DC5-B6CF-44CC-B08C-142066F58DEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"37e776c50f6a036565d45245417365b7d04511c0","datavalue":{"value":{"entity-type":"item","numeric-id":2222043,"id":"Q2222043"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fc217074db2f6d444ece06d55f9528b33acb5754","datavalue":{"value":{"amount":"+0.8651669","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":"Q5931414$8E42EC58-E795-4BC4-82AB-868D1FA34E10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1e22e676688e44c2f14c626fb127d7ff0322c0c0","datavalue":{"value":{"entity-type":"item","numeric-id":845675,"id":"Q845675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b043d693a3797cf9ac3e6f00b0a7903a1faec9c8","datavalue":{"value":{"amount":"+0.86426795","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":"Q5931414$A93F45D4-29D8-4EB1-883A-9E1E4EBE2C06","rank":"normal"},{"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":"46968f11952784fa67551fdd55a2e308ff42876f","datavalue":{"value":{"amount":"+0.86151445","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":"Q5931414$17929E84-DEE0-410D-97B4-BE9734CDC246","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"04c22729b99072ad753cc3553fab6c498539dc80","datavalue":{"value":{"entity-type":"item","numeric-id":1785209,"id":"Q1785209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"419c2506933a519ae5648d8a217f66af6e3bf246","datavalue":{"value":{"amount":"+0.8561747","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":"Q5931414$8B4A4DEE-464F-43C4-AB5D-B07108A7FC7E","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"30cea3543ba50de839bff2f67335fd4dca43b72f","datavalue":{"value":"Let \\(X\\), \\(Y\\) be two fixed graphs. The pair \\((X,Y)\\) is called a 2-pair if \\(Y\\) contains exactly two distinct copies of \\(X\\) that are induced subgraphs which are isomorphic to \\(X\\). The pair it is called a compact 2-pair if every vertex of \\(Y\\) is contained in at least one copy of \\(X\\).NEWLINENEWLINENEWLINEThe \\((X,Y)\\)-intersection graph of a graph \\(G\\) is a graph in which each vertex corresponds to a distinct copy of \\(Y\\) in \\(G\\) and where two vertices are adjacent iff the intersection of their corresponding copies contains a copy of \\(X\\). It can be seen that this notion generalizes the classical concept of the line graph of a graph. Furthermore, a pair \\((X,Y)\\) is hereditary if every induced subgraph of an arbitrary \\((X,Y)\\)-intersection graph is also an \\((X,Y)\\)-intersection graph. And \\((X,Y)\\) is an \\({\\mathfrak F}\\)-generator for any family \\({\\mathfrak F}\\) of graphs if the family of \\((X,Y)\\)-intersection graphs equals \\({\\mathfrak F}\\).NEWLINENEWLINENEWLINEIn present paper the families \\({\\mathfrak L}({\\mathfrak B})\\) (\\({\\mathfrak L}({\\mathfrak B}^*)\\), respectively) of line graphs of bipartite graphs (bipartite multigraphs, respectively) are treated and to this purpose the concept of stability of a 2-pair is introduced (see Definition 3.1). These stable 2-pairs are investigated in Section 3 and a necessary and sufficient condition for \\((X,Y)\\) to be stable is given (Proposition 3.2). The authors get the main results (Theorems 4.3 and 4.4) in Section 4 where they provide characterizations of stable 2-pairs that are \\({\\mathfrak L}({\\mathfrak B})\\)- or \\({\\mathfrak L}({\\mathfrak B^*})\\)-generators. For example, a stable 2-pair \\((X,Y)\\) is an \\({\\mathfrak L}({\\mathfrak B})\\)-generator iff it is non-reflexive, compact, even-stable and hereditary (Theorem 4.4). This means that \\({\\mathfrak L}({\\mathfrak B})\\) (and also \\({\\mathfrak L}({\\mathfrak B^*})\\)) to a certain degree play the ``smallest element'' role amongst the families of \\((X,Y)\\)-intersection graphs. Starting from \\(C_n\\), \\(n\\geq 4\\) (here \\(n= 6\\)), in Section 5 four graphs are constructed in detail which present examples of \\({\\mathfrak L}({\\mathfrak B})\\)- and \\({\\mathfrak L}({\\mathfrak B}^*)\\)-generators.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5931414$63A25CD1-9418-4781-BB63-ACAF71CDA27A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5931414","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5931414"}}}}}