✦ LIBER ✦

Directed star decompositions of directed multigraphs

✍ Scribed by Charles J. Colbourn; D.G. Hoffman; C.A. Rodger

Publisher: Elsevier Science
Year: 1991
Tongue: English
Weight: 670 KB
Volume: 97
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(91)90428-5

No coin nor oath required. For personal study only.

✦ Synopsis

Colbourn, C.J., D.G. Hoffman and C.A. Rodger, Directed star decompositions of directed multigraphs, Discrete Mathematics 97 (1991) 139-148.

An (s, t)-directed star decomposition of a directed multigraph is a partition of the arcs into directed stars, each having s arcs into the center and t arcs out of the center. We determine necessary and sufficient conditions for a directed complete multigraph to have an (s, t)-directed star decomposition.

We further determine necessary and sufficient conditions for a regular directed symmetric graph to have such a decomposition in which each vertex is the center of the same number of stars.

📜 SIMILAR VOLUMES

Directed star decompositions of the comp

Directed star decompositions of the complete directed graph

✍ Charles J. Colbourn; D. G. Hoffman; C. A. Rodger 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 545 KB

## Abstract An (__s, t__)‐directed star is a directed graph with __s__ + __t__ + 1 vertices and s + t arcs; s vertices have indegree zero and outdegree one, __t__ have indegree one and outdegree zero, and one has indegree __s__ and outdegree __t__. An (__s, t__)‐directed star decomposition is a par

Counting spanning trees in directed regu

Counting spanning trees in directed regular multigraphs

✍ Jacek M. Wojciechowski; Michael Fellows 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 484 KB

The problem of counting spunning trees in regular multigraphs is considered. The emphasis is on the case of directed trees. It is shown that the numbers qf spanning intrees and out-trees with respect to any point of' a regular multigraph are the same. A general .formulafor counting directed spunning

Decomposition of complete multigraphs in

Decomposition of complete multigraphs into stars

✍ Michael Tarsi 📂 Article 📅 1979 🏛 Elsevier Science 🌐 English ⚖ 531 KB

A necessary and sufficient condition for the existence of a decomposition of A&, irto stars is given. A complete multigraph AK, is a complete graph & in which every edge is taken A times. A complete multigraph A&, is said to have a G-decomposition G[h, v] if it is a union of edge disjoint subgraphs

Path decompositions of multigraphs

✍ Leizhen Cai 📂 Article 📅 1995 🏛 John Wiley and Sons 🌐 English ⚖ 494 KB

Let G be a loopless finite multigraph. For each vertex x of G, denote its degree and multiplicity by d(x) and p(x) respectively. Define the least even integer 2 p(x), if d(x) is even, the least odd integer 2 p(x), if d(x) is odd. In this paper it is shown that every multigraph G admits a faithful p

Cycle decompositions of complete multigr

Cycle decompositions of complete multigraphs

✍ Benjamin R. Smith 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 106 KB

## Abstract In this paper we establish necessary and sufficient conditions for decomposing the complete multigraph λ__K__~__n__~ into cycles of length λ, and the λ‐fold complete symmetric digraph λ__K__ into directed cycles of length λ. As a corollary to these results we obtain necessary and suffic

Cycle decompositions of complete multigr

Cycle decompositions of complete multigraphs

✍ Darryn Bryant; Daniel Horsley; Barbara Maenhaut; Benjamin R. Smith 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 265 KB

It is shown that the obvious necessary conditions for the existence of a decomposition of the complete multigraph with n vertices and with k edges joining each pair of distinct vertices into m-cycles, or into m-cycles and a perfect matching, are also sufficient. This result follows as an easy conseq