Language:   Search:   Contact
Zentralblatt MATH has released its new interface!
For an improved author identification, see the new author database of ZBMATH.

# Simple Search

Query:
Enter a query and click »Search«...
Format:
Display: entries per page entries
Zbl 0847.05063
Edge-domatic numbers of directed graphs.
(English)
[J] Czech. Math. J. 45, No.3, 449-455 (1995). ISSN 0011-4642; ISSN 1572-9141/e

In [Networks 7, 247-261 (1977; Zbl 0384.05051)] {\it E. J. Cockayne} and {\it S. T. Hedetniemi} introduced the domatic number of an undirected graph $G$ as the maximum number of classes of a partition of the vertex set of $G$ into dominating sets. Many variants of this number have been later studied, among them the edge-domatic number of an undirected graph [{\it B. Zelinka}, Czech. Math. J. 33(108), 107-110 (1983; Zbl 0537.05049)]. Here we will study an analogous concept for directed graphs. The adjacency of edges in a directed graph will be introduced analogously to our paper [Edge-chromatic numbers of directed graphs (to appear)]. We consider finite directed graphs (shortly digraphs) without loops in which two vertices may be joined by two edges only if these edges are oppositely directed. Two edges of a digraph $G$ will be called adjacent, if the terminal vertex of one of them is the initial vertex of the other. A subset $D$ of the edge set $E(G)$ of $G$ is called edge-dominating, if for each edge $e \in E(G) - D$ there exists an edge $f \in D$ adjacent to $e$. A partition of $E(G)$ is called an edge-domatic partition of $G$, if all of its classes are edge-dominating sets in $G$. The maximum number of classes of an edge-domatic partition of $G$ is called the edge-domatic number of $G$ and denoted by $\text {ed} (G)$.\par Sometimes it is more convenient to speak about edge-domatic colourings instead of edge-domatic partitions. A colouring of edges of a digraph $G$ is called edge-domatic, if each edge is adjacent in $G$ to edges of all colours different from its own. (Two adjacent edges may be coloured by the same colour). Then the edge-domatic number of $G$ is equal to the maximum number of colours of an edge-domatic colouring of $G$. Equivalence of this definition with the previous one is evident. The edge domatic number of a directed graph $G$ is evidently equal to the domatic number of the graph $L(G)$ whose vertex set is is the edge set of $G$ and in which two vertices are adjacent if and only if they are adjacent as edges in $G$.
MSC 2000:
*05C35 Extremal problems (graph theory)
05C20 Directed graphs (digraphs)

Keywords: domatic number; digraphs; edge-domatic partition; edge-dominating sets; edge-domatic number; edge-domatic colourings

Citations: Zbl 0384.05051; Zbl 0537.05049

Highlights
Master Server