A communication problem and directed triple systems (Q1392553): Difference between revisions

Consider the graph obtained from a balanced bipartite graph with \(m\) vertices in each part by adding \(2m\) vertex disjoint stars with \(t\) edges, one centered at each of the \(2m\) vertices. This gives a graph with \(2m(t+1)\) vertices and \(tm\) vertices of degree \(1\) on each side of the bipartite graph. In the case when the balanced bipartite graph is complete, denote this graph by \(G(m,t)\). Given an arbitrary pairing of the \(tm\) vertices in each part, what are the conditions that imply there exist edge disjoint paths between the \(tm\) pairs of vertices are studied. The graph is called pairable if the paths exists. This pairable problem is reduced to the existence of transitive triple systems in an appropriate directed multigraph on \(m\) vertices. For special classes of graphs the existence of transitive triple systems are exhibited. In particular, it is shown that if \(t \leq m/12\), then \(G(m,t)\) is pairable, and it was conjectured that \(G(m,t)\) is pairable if \(t \leq m/3\). Several interesting questions and conjectures are presented in the paper.