Optimal Domination Polynomials
- PDF / 280,086 Bytes
- 11 Pages / 439.37 x 666.142 pts Page_size
- 33 Downloads / 238 Views
(0123456789().,-volV)(0123456789().,-volV)
ORIGINAL PAPER
Optimal Domination Polynomials Iain Beaton1 • Jason I. Brown1 • Danielle Cox2 Received: 15 April 2019 / Revised: 6 February 2020 Springer Japan KK, part of Springer Nature 2020
Abstract Let G be a graph on n vertices and m edges and D(G, x) the domination polynomial of G. In this paper we completely characterize the values of n and m for which optimal graphs exist for domination polynomials. We also show that there does not always exist least optimal graphs for the domination polynomial. Applications to network reliability are highlighted. Keywords Domination polynomial Optimality Reliability
Mathematics Subject Classification 05C31 05C69
1 Introduction Consider a graph G with vertex set V(G) and edge set E(G) (we assume throughout that all graphs are simple, that is, without loops and multiple edges, as neither of these affect domination). Let S be a subset of vertices or edges such that S has a particular graph property, P. Perhaps P is that S is independent, complete, a dominating set or a matching. The sequences of the number of sets of varying cardinality that have property P have also been studied, particularly through the associated generating polynomials (which are graph polynomials). Independence, clique, domination and matching polynomials have all arisen and been studied in & Danielle Cox [email protected] Iain Beaton [email protected] Jason I. Brown [email protected] 1
Department of Mathematics and Statistics, Dalhousie University, Halifax, NS B3H 4R2, Canada
2
Department of Mathematics, Mount Saint Vincent University, Halifax, NS B3M 2J6, Canada
123
Graphs and Combinatorics
this setting. The evaluation of these polynomials at 1 yields the counts of the number of subsets in question, important graph invariants, and all of the graph polynomials can all be considered as functions on the domain ½0; 1Þ. If the number of vertices n and edges m are fixed, one can ask whether there exists optimal graphs with respect to a property, in the following sense. Let Gn;m denote the set of (simple) graphs of order n and size m (that is, with n vertices and m edges). A graph H 2 Gn;m is optimal if f ðH; xÞ f ðG; xÞ for all graphs G 2 Gn;m and all x 0 (for any particular value of x 0, of course, there is such a graph H, as the number of graphs of order n and size m is finite, but we are interested in uniformly optimal graphs). Of course, if there is a graph H such that the counts for the associated property sets are each greater than or equal to that for any other graph of the same order and size, that graph will be optimal. Optimality has been studied for independence polynomials [7], as well for other graph polynomials such as network reliability over the domain [0, 1] [3–6, 9, 10] and chromatic polynomials [11, 12]. In this paper we will investigate optimality of domination polynomials. Let G be a graph of order n and size m. A subset of vertices is called dominating if every vertex of G is either in S or adjacent to a vertex
Data Loading...
