Hypo-efficient domination and hypo-unique domination

Document Type : Original paper

Author

University of Architecture, Civil Еngineering and Geodesy; Department of Mathematics

Abstract

For a graph $G$ let $\gamma (G)$ be its domination number. We define a graph G to be (i)  a  hypo-efficient domination graph (or  a  hypo-$\mathcal{ED}$ graph) if $G$ has no  efficient dominating set (EDS)  but every graph formed by removing a single vertex from $G$ has at least one EDS, and (ii)  a hypo-unique domination graph (a hypo-$\mathcal{UD}$ graph) if $G$ has at least two  minimum dominating sets, but $G-v$ has a unique minimum dominating set  for each $v\in V(G)$. We  show that each  hypo-$\mathcal{UD}$ graph $G$ of order at least $3$  is connected  and $\gamma(G-v) <\gamma(G)$ for all $v \in V$. We obtain a tight  upper bound  on the order of a hypo-$\mathcal{P}$ graph in terms of the domination number and maximum degree of the graph, where $\mathcal{P} \in \{\mathcal{UD}, \mathcal{ED}\}$.  Families of  circulant graphs, which achieve these bounds, are presented. We also prove that the bondage number of any  hypo-$\mathcal{UD}$ graph is not more than the minimum degree plus one.  

Keywords

Main Subjects

References

[1] M. Araya and G. Wiener, On cubic planar hypohamiltonian and hypotraceable graphs, Electron. J. Combin. 18 (2011), no. 1, #P85.
[2] A. Bange, D. Barkauskas and P. Slater, Disjoint dominating sets in trees, Sandia Laboratories Report SAND 78-1087J (1987).
[3] A. Bange, D. Barkauskas and P. Slater, Effcient dominating sets in graphs, Applications of Mathematics (R. Ringeisen and F. Roberts, eds.), SIAM, Philadelphia, PA, 1988, pp. 189–199.
[4] Xu Baogen, E. Cockayne, S.T. Hedetniemi, and Z. Shangchao, Extremal graphs for inequalities involving domination parameters, Discrete Math. 216 (2000), no. 1–3, 1–10.
[5] D. Bauer, F. Harary, J. Nieminen, and C. Suffel, Domination alteration sets in graphs, Discrete Math. 47 (1983), 153–161.
[6] R. Brigham, P. Chinn, and R. Dutton, Vertex domination-critical graphs, Networks 18 (1988), no. 3, 173–179.
[7] R. Brigham, T. Haynes, M. Henning, and D. Rall, Bicritical domination, Discrete Math. 305 (2005), no. 1–3, 18–32.
[8] A. Coetzer, Criticality of the lower domination parameters of a graph, Master’s thesis, University of Stellenbosch, 3 2007.
[9] J. Fink, M. Jacobson, L. Kinch, and J. Roberts, On graphs having domination number half their order, Period. Math. Hungar. 16 (1985), no. 4, 287–293.
[10] M. Fischermann, Domination parameters and their unique realizations, Ph.D. thesis, Techn. Hochsch Aachen, 2 2002.
[11] J. Fulman, D. Hanson, and G. MacGillivray, Vertex domination-critical graphs, Networks 25 (1995), no. 3, 41–43.
[12] W. Goddard and M. Henning, Independent domination in graphs: A survey and recent results, Discr. Math. 313 (2013), no. 7, 839–854.
[13] P.G.P. Grobler, Critical concepts in domination, independence and irredundance of graphs, Ph.D. thesis, University of Sauth Africa, 11 1988.
[14] T. Haynes, S.T. Hedetniemi, and P. Slater, Domination in graphs: Advanced topics, Marcel Dekker New York, 1998.
[15] T. Haynes, S.T. Hedetniemi, and P. Slater, Fundamentals of domination in graphs, Marcel Dekker New York, 1998.
[16] M. Henning and A. Yeo, Total domination in graphs, Springer, 2013. 
[17] F.-T. Hu and J.-M. Xu, On the complexity of the bondage and reinforcement problems, J. of Complexity 28 (2012), no. 2, 192–201.
[18] S. Kapoor, Hypo-eulerian and hypo-traversable graphs, Elemente der Mathematik 28 (1973), 111–116.
[19] S. Klavzar, I. Peterin, and I.G. Yero, Graphs that are simultaneously efficient open domination and efficient closed domination graphs, http://arxiv.org/pdf/ 1511.01916v1.pdf, 2015.
[20] W. McCuaig and B. Shepherd, Domination in graphs with minimum degree two, J. Graph Theory 13 (1989), no. 6, 749–762.
[21] J. Mitchem, Hypo-properties in graphs, The Many Facets of Graph Theory (G. Chartrand and S.F. Kapoor, eds.), Springer-Verlag, Berlin, 1969, pp. 223–230.
[22] O. Ore, Theory of graphs, Amer. Math. Soc, Providence, RI, 1962.
[23] C. Payan and N. Xuong, Domination-balanced graphs, J. Graph Theory 6 (1982), no. 1, 23--32.
[24] M.D. Plummer, Graph factors and factorization: 1985–2003: A survey, Discrete Math. 307 (2007), no. 7–8, 791–821.
[25] U. Teschner, New results about the bondage number of a graph, Discrete Math. 171 (1997), no. 1–3, 249–259.
[26] K. Wagner, Fastpl¨attbare graphen, J. Combin. Theory 3 (1967), 326–365.
[27] J.-M. Xu, On bondage numbers of graphs: a survey with some comments, Inter. Journ. Comb. 2013 (2013), 34p.
[28] C.T. Zamfirescu, On hypohamiltonian and almost hypohamiltonian graphs, J. Graph Theory 79 (2015), no. 1, 63–81.
Communications in Combinatorics and Optimization
Volume 1, Issue 2 - Serial Number 2
December 2016
Pages 103-116

Files

Share

How to cite

Statistics