آمار
| تعداد نشریات | 6 |
| تعداد شمارهها | 121 |
| تعداد مقالات | 1,448 |
| تعداد مشاهده مقاله | 1,554,801 |
| تعداد دریافت فایل اصل مقاله | 1,459,127 |
Hypo-efficient domination and hypo-unique domination | ||
| Communications in Combinatorics and Optimization | ||
| مقاله 2، دوره 1، شماره 2، اسفند 2016، صفحه 103-116 اصل مقاله (517.94 K) | ||
| نوع مقاله: Original paper | ||
| شناسه دیجیتال (DOI): 10.22049/cco.2016.13553 | ||
| نویسنده | ||
| Vladimir Samodivkin* | ||
| University of Architecture, Civil Еngineering and Geodesy; Department of Mathematics | ||
| چکیده | ||
| 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. | ||
| کلیدواژهها | ||
| Domination number؛ Efficient Domination؛ unique domination؛ hypo-property | ||
| مراجع | ||
|
[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. | ||
|
آمار تعداد مشاهده مقاله: 1,892 تعداد دریافت فایل اصل مقاله: 2,706 |
||