Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
packing; open packing; total domination
packing; open packing; total domination
Summary:
A subset $S$ of vertices in a graph $G$ is an open packing set if no pair of vertices of $S$ has a common neighbor in $G$. An open packing set which is not a proper subset of any open packing set is called a maximal open packing set. The maximum cardinality of an open packing set is called the open packing number and is denoted by $\rho ^{\rm o}(G)$. A subset $S$ in a graph $G$ with no isolated vertex is called a total dominating set if any vertex of $G$ is adjacent to some vertex of $S$. The total domination number of $G$, denoted by $\gamma _t(G)$, is the minimum cardinality of a total dominating set of $G$. We characterize graphs of order $n$ and minimium degree at least two with $\rho ^{\rm o}(G)=\gamma _t(G)=\frac 12n$.
References:
[1] Archdeacon, D., Ellis-Monaghan, J., Fisher, D., Froncek, D., Lam, P. C. B., Seager, S., Wei, B., Yuster, R.: Some remarks on domination. J. Graph Theory 46 (2004), 207-210. DOI 10.1002/jgt.20000 | MR 2063370 | Zbl 1041.05057
[2] Biggs, N.: Perfect codes in graphs. J. Comb. Theory, Ser. B 15 (1973), 289-296. DOI 10.1016/0095-8956(73)90042-7 | MR 0325457 | Zbl 0256.94009
[3] Chartrand, G., Lesniak, L.: Graphs & Digraphs. Chapman & Hall/CRC, Boca Raton (2005). MR 2107429 | Zbl 1057.05001
[4] Clark, L.: Perfect domination in random graphs. J. Comb. Math. Comb. Comput. 14 (1993), 173-182. MR 1238868 | Zbl 0793.05106
[5] Cockayne, E. J., Dawes, R. M., Hedetniemi, S. T.: Total domination in graphs. Networks 10 (1980), 211-219. DOI 10.1002/net.3230100304 | MR 0584887 | Zbl 0447.05039
[6] Cockayne, E. J., Hartnell, B. L., Hedetniemi, S. T., Laskar, R.: Perfect domination in graphs. J. Comb. Inf. Syst. Sci. 18 (1993), 136-148. MR 1317698 | Zbl 0855.05073
[7] Haynes, T. W., Hedetniemi, S. T., Slater, P. J.: Fundamentals of Domination in Graphs. Monographs and Textbooks in Pure and Applied Mathematics, 208. Marcel Dekker, New York (1998). MR 1605684 | Zbl 0890.05002
[8] Henning, M. A.: Packing in trees. Discrete Math. 186 (1998), 145-155. DOI 10.1016/S0012-365X(97)00228-8 | MR 1623900 | Zbl 0957.05090
[9] Henning, M. A., Slater, P. J.: Open packing in graphs. J. Comb. Math. Comb. Comput. 29 (1999), 3-16. MR 1677666 | Zbl 0922.05040
[10] Henning, M. A., Yeo, A.: Total Domination in Graphs. Springer Monographs in Mathematics. Springer, New York (2013). DOI 10.1007/978-1-4614-6525-6 | MR 3060714 | Zbl 06150331
[11] Meir, A., Moon, J. W.: Relations between packing and covering numbers of a tree. Pac. J. Math. 61 (1975), 225-233. DOI 10.2140/pjm.1975.61.225 | MR 0401519 | Zbl 0315.05102
[12] Rall, D. F.: Total domination in categorical products of graphs. Discuss. Math., Graph Theory 25 (2005), 35-44. DOI 10.7151/dmgt.1257 | MR 2152047 | Zbl 1074.05068
[13] Hamid, I. Sahul, Saravanakumar, S.: Packing parameters in graphs. Discuss. Math., Graph Theory 35 (2015), 5-16. DOI 10.7151/dmgt.1775 | MR 3313234 | Zbl 1307.05183
[14] Hamid, I. Sahul, Saravanakumar, S.: On open packing number of graphs. Iran. J. Math. Sci. Inform. 12 (2017), 107-117. DOI 10.7508/ijmsi.2017.01.009 | MR 3726632 | Zbl 1375.05214
[15] Topp, J., Volkmann, L.: On packing and covering number of graphs. Discrete Math. 96 (1991), 229-238. DOI 10.1016/0012-365X(91)90316-T | MR 1139450 | Zbl 0759.05077
Search
Partner of
