| 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:
|
http://hdl.handle.net/10338.dmlcz/147761 |
| . |
| 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 |
| . |
