A communication problem and directed triple systems

DOI10.1016/S0166-218X(98)00028-6MaRDI QIDQ1392553zbMATH OpenWikidataFDO

Authors András Gyárfás, R. H. Schelp

Publication date 2 December 1998

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL http://www.elsevier.com/locate/dam

zbMATH Keywords

balanced bipartite graphtransitive triple systems

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

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.

Recommendations

• A theory of higher order communicating systems
• A three-party communication problem
• scientific article; zbMATH DE number 3843756
• scientific article; zbMATH DE number 2146643
• Communication tree problems
• Extended directed triple systems
• Possibility and complexity of probabilistic reliable communication in directed networks
• Communication complexity in a 3-computer model
• On large sets of directed triple systems

Cites work

• scientific article; zbMATH DE number 434691 (Why is no real title available?)
• scientific article; zbMATH DE number 3943824 (Why is no real title available?)
• scientific article; zbMATH DE number 3685495 (Why is no real title available?)
• Networks communicating for each pairing of terminals
• The Analysis of Directed Triple Systems by Refinement
• Three-regular path pairable graphs

Cited in

(5)

• Terminal-pairability in complete bipartite graphs
• Terminal-pairability in complete bipartite graphs with non-bipartite demands. Edge-disjoint paths in complete bipartite graphs
• The terminal-pairability problem in complete bipartite graphs
• Three messages are not optimal in worst case interactive communication
• Decomposition of bipartite graphs into special subgraphs

This page was built for publication: A communication problem and directed triple systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1392553)