On consistent families of circuits (Q1112839): Difference between revisions

For a graph G and any subset \(S\subset V(G)\), let \(G^ S\) be a graph with vertex set V(G)-S and \(xy\in E(G^ S)\) iff x any y are connected in G by a path all of whose interior vertices belong to S. Two graphs \(G_ i=(V_ i,E_ i)\), \(i=1,2\), are consistent iff \(G_ 1^{V_ 1-V_ 2}=G_ 2^{V_ 2-V_ 1}\). It is proved that if V is a finite set and if F is a family of pairwise consistent circuits of length \(| V| -1\) with vertices in V, then there is at most one circuit on V that is consistent with each element of F when \(| V| \geq 5\) and \(| F| \geq 3\), and there is a unique such circuit on V when \(| V| \geq 6\) and \(| F| \geq 4\). Moreover, the smallest numbers of pairwise consistent circuits on k-subsets of \(\{\) 1,2,...,v\(\}\) are determined such that there is at most or at least one circuit on \(\{\) 1,2,...,v\(\}\) that is consistent with each of these circuits. At last, similar results are obtained for paths instead of circuits.