Factor domination and minimum degree

DOI10.1016/S0012-365X(02)00522-8MaRDI QIDQ1868841zbMATH OpenOpenAlexFDO

Authors Peter Dankelmann, Renu C. Laskar

Publication date 28 April 2003

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(02)00522-8

zbMATH Keywords

dominationfactor

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

As their main result the authors prove the best-possible estimate \(\gamma(F_1,F_2)\leq \frac{2}{3}n\) where \(F_1\) and \(F_2\) are factors of the complete graph \(K_n\) of order \(n\) that have minimum degree at least \(1\). The proof idea also yields an upper bound of the factor domination number of \(k\geq 2\) factors of \(K_n\) of minimum degree \(1\). The second main result is an upper bound on \(\gamma(F_1,F_2,\dots ,F_k)\) in terms of the least minimum degree \(\delta\) of the factors, their number \(k\) and their order \(n\) that is proved using a well-known probabilistic argument.

Recommendations

• Factor domination in graphs
• scientific article; zbMATH DE number 140127
• Tight upper bounds for the domination numbers of graphs with given order and minimum degree
• Some nordhaus‐‐ gaddum‐type results
• scientific article; zbMATH DE number 1472173

Cited in

(6)

• On global domination critical graphs
• Minimum degree, independence number and regular factors
• Simultaneous graph parameters: factor domination and factor total domination
• Global domination
• Simultaneous domination in graphs
• Linear programming formulation for some generalized domination parameters

This page was built for publication: Factor domination and minimum degree

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