Hostname: page-component-7b7567c8c-p67k6 Total loading time: 0 Render date: 2026-11-19T11:50:55.598Z Has data issue: false hasContentIssue false

Path decompositions of digraphs

Published online by Cambridge University Press:  17 April 2009

Issam Abdul-Kader
Affiliation:
Faculty of Science, Lebanese University, Beirut, Lebanon.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Let G = (X, U) be a digraph of order n. P(G) denotes the minimal cardinal of a path-partition of the arcs of G.

Oystein Ore, Theory of graphs (Amer. Math. Soc, Providence, Rhode Island, 1962) has proved that , where . We say that G satisfies Q if the preceeding inequality is an equality.

We give some properties of the digraphs satisfying Q, and in particular the case where G is strongly connected. Then we prove that P(G) ≤ [n2/4], and that this result is the best possible. Next we exhibit the existence of digraphs with circuits such that P(G) = [n2/4].

Finally we prove that if G is a strongly connected digraph of order n which satisfies Q, then there exists a strongly connected digraph H of order n + 1 having G as a sub-digraph and satisfying Q, too.

Information

Type
Research Article
Copyright
Copyright © Australian Mathematical Society 1979