A communication problem and directed triple systems (Q1392553): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Created claim: Wikidata QID (P12): Q127579744, #quickstatements; #temporary_batch_1722633721812 |
||
Property / Wikidata QID | |||
Property / Wikidata QID: Q127579744 / rank | |||
Normal rank |
Latest revision as of 23:23, 2 August 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A communication problem and directed triple systems |
scientific article |
Statements
A communication problem and directed triple systems (English)
0 references
2 December 1998
0 references
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.
0 references
balanced bipartite graph
0 references
transitive triple systems
0 references