๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

On the complexity of digraph packings

โœ Scribed by Richard C. Brewster; Romeo Rizzi

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
99 KB
Volume
86
Category
Article
ISSN
0020-0190

No coin nor oath required. For personal study only.

โœฆ Synopsis

Let G be a fixed collection of digraphs. Given a digraph H , a G-packing of H is a collection of vertex disjoint subgraphs of H , each isomorphic to a member of G. For undirected graphs, Loebl and Poljak have completely characterized the complexity of deciding the existence of a perfect G-packing, in the case that G consists of two graphs one of which is a single edge on two vertices. We characterize G-packing where G consists of two digraphs one of which is a single arc on two vertices.

๐Ÿ“œ SIMILAR VOLUMES

On the Ferrers dimension of a digraph
On the Ferrers dimension of a digraph
โœ Olivier Cogis ๐Ÿ“‚ Article ๐Ÿ“… 1982 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 714 KB

The Ferrer-s dimension of a digraph has been shown to be an extension of the order dimension. By proving a property of (finite) transitive Ferrers digraphs, we give an original proof of this above result and derive Ore's alternative definition of the order dimension. Still, the order dimension is pr

On the Cover Polynomial of a Digraph
On the Cover Polynomial of a Digraph
โœ F.R.K. Chung; R.L. Graham ๐Ÿ“‚ Article ๐Ÿ“… 1995 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 511 KB
On the Capacity of Digraphs
On the Capacity of Digraphs
โœ Noga Alon ๐Ÿ“‚ Article ๐Ÿ“… 1998 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 76 KB

For a digraph G = (V, E) let w(G n ) denote the maximum possible cardinality of a subset S of V n in which for every ordered pair It is also shown that for every n there is a tournament T on 2n vertices whose capacity is at least โˆš n, whereas the maximum number of vertices in a transitive subtourna