Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 0847.05063
Zelinka, Bohdan
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

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Simple Search

Zentralblatt MATH Berlin [Germany]