Stable 2-pairs and \((X,Y)\)-intersection graphs (Q5931414): Difference between revisions

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\). The \((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}\). In 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.