𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Partitions of digraphs into paths or circuits

✍ Scribed by W. Bienia; H. Meyniel

Publisher
Elsevier Science
Year
1986
Tongue
English
Weight
178 KB
Volume
61
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

The problem of partitioning the arcs of a digraph into elementary paths has been considered first by B. Alspach and N.J. Pullman in . We consider the slightly different problem of partitioning the arcs of a digraph into elementary paths or circuits. A general conjecture is given which is solved in particular cases (with in fact slightly stronger results).

πŸ“œ SIMILAR VOLUMES

Partitions of a graph into paths with pr
Partitions of a graph into paths with prescribed endvertices and lengths
✍ Hikoe Enomoto; Katsuhiro Ota πŸ“‚ Article πŸ“… 2000 πŸ› John Wiley and Sons 🌐 English βš– 95 KB πŸ‘ 3 views

For a graph G, let ' 2 (G ) denote the minimum degree sum of a pair of nonadjacent vertices. We conjecture that if |V(G)| n i 1 k a i and ' 2 (G ) ! n k Γ€ 1, then for any k vertices v 1 , v 2 , F F F , v k in G, there exist vertex-disjoint paths P 1 , P 2 , F F F , P k such that |V (P i )| a i and v

Partitions of graphs into one or two ind
Partitions of graphs into one or two independent sets and cliques
✍ Andreas BrandstΓ€dt πŸ“‚ Article πŸ“… 1996 πŸ› Elsevier Science 🌐 English βš– 417 KB

It is shown in this note that it can be recognized in polynomial time whether the vertex set of a finite undirected graph can be partitioned into one or two independent sets and one or two cliques. Such graphs generalize bipartite and split graphs and the result also shows that it can be recognized