Previous |  Up |  Next


Title: A note on the open packing number in graphs (English)
Author: Mohammadi, Mehdi
Author: Maghasedi, Mohammad
Language: English
Journal: Mathematica Bohemica
ISSN: 0862-7959 (print)
ISSN: 2464-7136 (online)
Volume: 144
Issue: 2
Year: 2019
Pages: 221-224
Summary lang: English
Category: math
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$. (English)
Keyword: packing
Keyword: open packing
Keyword: total domination
MSC: 05C69
MSC: 05C70
idZBL: Zbl 07088847
idMR: MR3974189
DOI: 10.21136/MB.2018.0124-17
Date available: 2019-06-21T11:35:57Z
Last updated: 2020-07-01
Stable URL:
Reference: [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. Zbl 1041.05057, MR 2063370, 10.1002/jgt.20000
Reference: [2] Biggs, N.: Perfect codes in graphs.J. Comb. Theory, Ser. B 15 (1973), 289-296. Zbl 0256.94009, MR 0325457, 10.1016/0095-8956(73)90042-7
Reference: [3] Chartrand, G., Lesniak, L.: Graphs & Digraphs.Chapman & Hall/CRC, Boca Raton (2005). Zbl 1057.05001, MR 2107429
Reference: [4] Clark, L.: Perfect domination in random graphs.J. Comb. Math. Comb. Comput. 14 (1993), 173-182. Zbl 0793.05106, MR 1238868
Reference: [5] Cockayne, E. J., Dawes, R. M., Hedetniemi, S. T.: Total domination in graphs.Networks 10 (1980), 211-219. Zbl 0447.05039, MR 0584887, 10.1002/net.3230100304
Reference: [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. Zbl 0855.05073, MR 1317698
Reference: [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). Zbl 0890.05002, MR 1605684
Reference: [8] Henning, M. A.: Packing in trees.Discrete Math. 186 (1998), 145-155. Zbl 0957.05090, MR 1623900, 10.1016/S0012-365X(97)00228-8
Reference: [9] Henning, M. A., Slater, P. J.: Open packing in graphs.J. Comb. Math. Comb. Comput. 29 (1999), 3-16. Zbl 0922.05040, MR 1677666
Reference: [10] Henning, M. A., Yeo, A.: Total Domination in Graphs.Springer Monographs in Mathematics. Springer, New York (2013). Zbl 06150331, MR 3060714, 10.1007/978-1-4614-6525-6
Reference: [11] Meir, A., Moon, J. W.: Relations between packing and covering numbers of a tree.Pac. J. Math. 61 (1975), 225-233. Zbl 0315.05102, MR 0401519, 10.2140/pjm.1975.61.225
Reference: [12] Rall, D. F.: Total domination in categorical products of graphs.Discuss. Math., Graph Theory 25 (2005), 35-44. Zbl 1074.05068, MR 2152047, 10.7151/dmgt.1257
Reference: [13] Hamid, I. Sahul, Saravanakumar, S.: Packing parameters in graphs.Discuss. Math., Graph Theory 35 (2015), 5-16. Zbl 1307.05183, MR 3313234, 10.7151/dmgt.1775
Reference: [14] Hamid, I. Sahul, Saravanakumar, S.: On open packing number of graphs.Iran. J. Math. Sci. Inform. 12 (2017), 107-117. Zbl 1375.05214, MR 3726632, 10.7508/ijmsi.2017.01.009
Reference: [15] Topp, J., Volkmann, L.: On packing and covering number of graphs.Discrete Math. 96 (1991), 229-238. Zbl 0759.05077, MR 1139450, 10.1016/0012-365X(91)90316-T


Files Size Format View
MathBohem_144-2019-2_9.pdf 234.1Kb application/pdf View/Open
Back to standard record
Partner of
EuDML logo