Edge-domatic number of a graph

From MaRDI portal





An edge-dominating set of a graph G is a subset D of the edge set E(G) with the property that for each edge \(e\in E(G)-D\) there exists at least one edge \(f\in D\) adjacent to e. The maximum number of classes of partitions of E(G) into edge-dominating sets is called the edge-domatic number of G and is denoted by ed(G). This concept is studied for complete graphs, complete bipartite graphs, cycles and trees. If T is a tree it is found that \(ed(T)=\delta_ e+1,\) where \(\delta_ e(G)\) is the minimum degree of a vertex in the line-graph of G, analogous to \(\delta\) (G), the minimum degree of G. The main result is that for a finite undirected graph G \(\delta(G)\leq ed(G)\leq \delta_ e(G)+1.\)











This page was built for publication: Edge-domatic number of a graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3322140)