×

zbMATH — the first resource for mathematics

Domatic number and linear arboricity of cacti. (English) Zbl 0583.05050
A cactus is a connected graph of order at least 2, each edge of which belongs to at most one cycle. A dominating set in a graph G is a set D of V(G) with the property that for each vertex x in V(G)-D, there is a vertex y in D adjacent to x. A domatic partition of G is a partition of V(G), all of whose classes are dominating sets in G. The domatic number of G is the maximum number of classes in a domatic partition of G. An idomatic partition of G is a partition of V(G), each of whose classes is a set that is both dominating and independent in G. If there exists at least one idomatic partition of G, then the maximum number of classes in such a partition is the idomatic number of G; otherwise, the idomatic number of G is 0. The linear arboricity of a graph G is the minimum number of linear forests into which E(G) can be partitioned. The author presents a number of results on cacti, involving the parameters domatic number, idomatic number and linear arboricity.
Reviewer: G.Chartrand

MSC:
05C99 Graph theory
05C15 Coloring of graphs and hypergraphs
PDF BibTeX XML Cite
Full Text: EuDML
References:
[1] AKIYAMA J., EXOO G., HARARY R.: Covering and packing in graphs III: Cyclic and acyclic invariants. Math. Slovaca 30, 1980, 405-417. · Zbl 0458.05050
[2] COCKAYNE E. J., HEDETNIEMI S. T.: Towards a theory of domination in graphs. Networks 7, 1977, 247-261. · Zbl 0384.05051
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.