A communication problem and directed triple systems (Q1392553): Difference between revisions
From MaRDI portal
Changed an Item |
Created claim: Wikidata QID (P12): Q127579744, #quickstatements; #temporary_batch_1722633721812 |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The Analysis of Directed Triple Systems by Refinement / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Networks communicating for each pairing of terminals / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3139528 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Three-regular path pairable graphs / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3715120 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3880849 / rank | |||
Normal rank | |||
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