Geodesic
A note on the open packing number in graphs
Mathematica Bohemica, Tome 144 (2019) no. 2, pp. 221-224
Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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$.
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$.
DOI : 10.21136/MB.2018.0124-17
Classification : 05C69, 05C70
Keywords: packing; open packing; total domination 
@article{10_21136_MB_2018_0124_17,
     author = {Mohammadi, Mehdi and Maghasedi, Mohammad},
     title = {A note on the open packing number in graphs},
     journal = {Mathematica Bohemica},
     pages = {221--224},
     year = {2019},
     volume = {144},
     number = {2},
     doi = {10.21136/MB.2018.0124-17},
     mrnumber = {3974189},
     zbl = {07088847},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/MB.2018.0124-17/}
}
TY  - JOUR
AU  - Mohammadi, Mehdi
AU  - Maghasedi, Mohammad
TI  - A note on the open packing number in graphs
JO  - Mathematica Bohemica
PY  - 2019
SP  - 221
EP  - 224
VL  - 144
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.21136/MB.2018.0124-17/
DO  - 10.21136/MB.2018.0124-17
LA  - en
ID  - 10_21136_MB_2018_0124_17
ER  - 
%0 Journal Article
%A Mohammadi, Mehdi
%A Maghasedi, Mohammad
%T A note on the open packing number in graphs
%J Mathematica Bohemica
%D 2019
%P 221-224
%V 144
%N 2
%U http://geodesic.mathdoc.fr/articles/10.21136/MB.2018.0124-17/
%R 10.21136/MB.2018.0124-17
%G en
%F 10_21136_MB_2018_0124_17
Mohammadi, Mehdi; Maghasedi, Mohammad. A note on the open packing number in graphs. Mathematica Bohemica, Tome 144 (2019) no. 2, pp. 221-224. doi: 10.21136/MB.2018.0124-17

[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 | MR | JFM

[2] Biggs, N.: Perfect codes in graphs. J. Comb. Theory, Ser. B 15 (1973), 289-296. | DOI | MR | JFM

[3] Chartrand, G., Lesniak, L.: Graphs & Digraphs. Chapman & Hall/CRC, Boca Raton (2005). | MR | JFM

[4] Clark, L.: Perfect domination in random graphs. J. Comb. Math. Comb. Comput. 14 (1993), 173-182. | MR | JFM

[5] Cockayne, E. J., Dawes, R. M., Hedetniemi, S. T.: Total domination in graphs. Networks 10 (1980), 211-219. | DOI | MR | JFM

[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 | JFM

[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 | JFM

[8] Henning, M. A.: Packing in trees. Discrete Math. 186 (1998), 145-155. | DOI | MR | JFM

[9] Henning, M. A., Slater, P. J.: Open packing in graphs. J. Comb. Math. Comb. Comput. 29 (1999), 3-16. | MR | JFM

[10] Henning, M. A., Yeo, A.: Total Domination in Graphs. Springer Monographs in Mathematics. Springer, New York (2013). | DOI | MR | JFM

[11] Meir, A., Moon, J. W.: Relations between packing and covering numbers of a tree. Pac. J. Math. 61 (1975), 225-233. | DOI | MR | JFM

[12] Rall, D. F.: Total domination in categorical products of graphs. Discuss. Math., Graph Theory 25 (2005), 35-44. | DOI | MR | JFM

[13] Hamid, I. Sahul, Saravanakumar, S.: Packing parameters in graphs. Discuss. Math., Graph Theory 35 (2015), 5-16. | DOI | MR | JFM

[14] Hamid, I. Sahul, Saravanakumar, S.: On open packing number of graphs. Iran. J. Math. Sci. Inform. 12 (2017), 107-117. | DOI | MR | JFM

[15] Topp, J., Volkmann, L.: On packing and covering number of graphs. Discrete Math. 96 (1991), 229-238. | DOI | MR | JFM

Cité par Sources :