×

zbMATH — the first resource for mathematics

Edge-domatic numbers of directed graphs. (English) Zbl 0847.05063
In [Networks 7, 247-261 (1977; Zbl 0384.05051)] E. J. Cockayne and 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 [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)\).
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:
05C35 Extremal problems in graph theory
05C20 Directed graphs (digraphs), tournaments
PDF BibTeX XML Cite
Full Text: EuDML
References:
[1] E. J. Cockayne, S. T. Hedetniemi: Towards a theory of domination of graphs. Networks 7 (1977), 247-261. · Zbl 0384.05051 · doi:10.1002/net.3230070305
[2] B. Zelinka: Edge-domatic number of a graph. Czech. Math. J. 33 (1983), 107-110. · Zbl 0537.05049 · eudml:13366
[3] B. Zelinka: Edge-chromatic numbers of directed graphs. Math. Slovaca. · Zbl 0847.05063 · eudml:31478
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.