A tight upper bound on the average order of dominating sets of a graph

DOI10.1002/JGT.23143MaRDI QIDQ6642500zbMATH OpenFDO

Authors I. Beaton, Ben Cameron

Publication date 24 November 2024

Published in Journal of Graph Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://doi.org/10.1002/JGT.23143

zbMATH Keywords

average graph parametersdominating setdomination polynomial

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph operations (line graphs, products, etc.) (05C76)

Review text

Investigation of the average order of any graph theoretic parameter is a significant problem. Let \(\mathcal{D}=\{D_1,D_2,\dots,D_r\}\) be the set of all dominating sets of a graph. Then \(\frac{1}{r}\sum\limits_{i=1}^r |D_i|\) is the average order of dominating sets in \(G\) and is denoted by \(\mathrm{avd}(G).\) It has been conjectured that if \(G\) is a graph of order \(n\) having no isolated vertices, then \(\mathrm{avd}(G)\leq \frac{2n}{3}.\) In this paper this conjecture is proved and the class of graphs for which \(\mathrm{avd}(G)=\frac{2n}{3}\) is completely classified.\N\N\textit{V. G. Vizing} [Russ. Math. Surv. 23, No. 6, 125--141 (1968; Zbl 0192.60502); translation from Usp. Mat. Nauk 23, No. 6(144), 117--134 (1968)] has conjectured that \(\gamma(G\Box H)\geq \gamma(G)\gamma(H)\) where \(G\Box H\) denotes the Cartesian product and \(\gamma(G)\) denotes the domination number of \(G.\) This is a long-standing conjecture in domination theory. The authors establish that \(\mathrm{avd}(G\Box H)> \mathrm{avd}(G\Box H),\) showing that Vizing's conjecture is valid for \(\mathrm{avd}(G).\) Finding tight upper and lower bounds for \(\mathrm{avd}(G)\) in terms of \(\gamma(G)\) is an interesting problem for further investigation.

Recommendations

• The average order of dominating sets of a graph
• On Vizing's conjecture
• scientific article; zbMATH DE number 2197881
• Improving some bounds for dominating Cartesian products
• scientific article; zbMATH DE number 140092

Cites work

• A lower bound on the average size of a connected vertex set of a graph
• scientific article; zbMATH DE number 3284071 (Why is no real title available?)
• Independent sets, matchings, and occupancy fractions
• Introduction to domination polynomial of a graph.
• Maximizing the mean subtree order
• Mean distance in a graph
• Monotonicity of the mean order of subtrees
• On the average number of nodes in a subtree of a tree
• On the average order of a dominating set of a forest
• On the average size of independent sets in triangle-free graphs
• On the Distribution of the Number of Successes in Independent Trials
• On the local and global means of subtree orders
• On the maximum mean subtree order of trees
• On the mean connected induced subgraph order of cographs
• On the mean order of connected induced subgraphs of block graphs
• On the mean subtree order of graphs under edge addition
• On the roots of domination polynomial of graphs
• On the roots of domination polynomials
• Sketchy tweets: ten minute conjectures in graph theory
• Subtrees of graphs
• The average order of a subtree of a tree
• The average order of dominating sets of a graph
• The average size of independent sets of graphs
• The average size of matchings in graphs
• The number and average size of connected sets in graphs with degree constraints
• The path minimises the average size of a connected induced subgraph

Cited in

(2)

• On the number of independent and \(k\)-dominating sets in graphs with average vertex degree at most \(k\)
• On average sizes and enumeration of minimal edge covers

This page was built for publication: A tight upper bound on the average order of dominating sets of a graph

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