Maximum sizes of graphs with given domination parameters

DOI10.1016/J.DISC.2003.07.010MaRDI QIDQ1827704zbMATH OpenOpenAlexFDO

Authors Peter Dankelmann, Gayla S. Domke, Johannes H. Hattingh, H. C. Swart, Wayne Goddard, Paul Grobler

Publication date 6 August 2004

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2003.07.010

zbMATH Keywords

dominationextremal graphsindependent dominationirredundancesizetotal domination

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Review text

As their main results the authors prove upper bounds on the sizes of (i) graphs of given order and total domination number, (ii) bipartite graphs of given order and total domination number, (iii) graphs of given order and independent domination number and (iv) bipartite graphs of given order and independent domination number. Whereas in cases (i), (iii) and (iv) the given bounds are sharp for all considered values, the bound in case (ii) is only sharp for all even considered values of the total domination number and a related conjecture is presented. In case (iv) the authors also characterize all extremal graphs. Finally, using known results due to Vizing and Ferneyhough et al. the authors solve the same problems for the lower irredundance number, the independence number, the upper domination number and the upper irredundance number.

Recommendations

• Maximum size of a connected graph with given domination parameters
• On domination parameters and maximum degree of a graph
• scientific article; zbMATH DE number 1506495
• Theory of domination in graphs
• scientific article; zbMATH DE number 1124607

Cites work

• A generalization of Vizing's theorem on domination
• A linear vizing-like relation between the size and the domination number of a graph
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1506495 (Why is no real title available?)
• scientific article; zbMATH DE number 3221976 (Why is no real title available?)
• Maximum number of edges in connected graphs with a given domination number
• Maximum size of a connected graph with given domination parameters
• On the number of edges in graphs with a given connected domination number
• Star forests, dominating sets and Ramsey-type problems
• Total domination in graphs

Cited in

(23)

• Relating the size of a connected graph to its total and restricted domination numbers
• Bounds on neighborhood total domination number in graphs
• Extremal graphs for a new upper bound on domination parameters in graphs
• Equality in a linear Vizing-like relation that relates the size and total domination number of a graph
• Graphs with maximum size and given paired-domination number
• Maximum size of a connected graph with given domination parameters
• Equality in a bound that relates the size and the restrained domination number of a graph
• On the characterization of the maximal connected bipartite graphs with given domination number
• Maximum size of digraphs with some parameters
• Upper bounds for domination related parameters in graphs on surfaces
• Maximal core size in singular graphs
• scientific article; zbMATH DE number 5717187 (Why is no real title available?)
• On size, order, diameter and minimum degree
• scientific article; zbMATH DE number 5498807 (Why is no real title available?)
• My favorite domination conjectures in graph theory are bounded
• An inequality that relates the size of a bipartite graph with its order and restrained domination number
• Extremal problems related to the cardinality-redundance of graphs
• Optimal linear‐Vizing relationships for (total) domination in graphs
• On size, order, diameter and edge-connectivity of graphs
• Improving a bound that relates the size of a bipartite graph with its restrained domination number
• Independent domination, order, size, and maximum degree
• Some spin glass ideas applied to the clique problem
• A survey of selected recent results on total domination in graphs

This page was built for publication: Maximum sizes of graphs with given domination parameters

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