Geodesic
Further Results on Packing Related Parameters in Graphs
Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 2, pp. 333-348

Voir la notice de l'article provenant de la source Library of Science

Given a graph G = (V, E), a set B ⊆ V (G) is a packing in G if the closed neighborhoods of every pair of distinct vertices in B are pairwise disjoint. The packing number ρ(G) of G is the maximum cardinality of a packing in G. Similarly, open packing sets and open packing number are defined for a graph G by using open neighborhoods instead of closed ones. We give several results concerning the (open) packing number of graphs in this paper. For instance, several bounds on these packing parameters along with some Nordhaus-Gaddum inequalities are given. We characterize all graphs with equal packing and independence numbers and give the characterization of all graphs for which the packing number is equal to the independence number minus one. In addition, due to the close connection between the open packing and total domination numbers, we prove a new upper bound on the total domination number γt(T) for a tree T of order n ≥ 2 improving the upper bound γt(T) ≤ (n + s)/2 given by Chellali and Haynes in 2004, in which s is the number of support vertices of T.
Keywords: packing number, open packing number, independence number, Nordhaus-Gaddum inequality, total domination number 
@article{DMGT_2022_42_2_a1,
     author = {Mojdeh, Doost Ali and Samadi, Babak and Yero, Ismael G.},
     title = {Further {Results} on {Packing} {Related} {Parameters} in {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {333--348},
     publisher = {mathdoc},
     volume = {42},
     number = {2},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a1/}
}
TY  - JOUR
AU  - Mojdeh, Doost Ali
AU  - Samadi, Babak
AU  - Yero, Ismael G.
TI  - Further Results on Packing Related Parameters in Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2022
SP  - 333
EP  - 348
VL  - 42
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a1/
LA  - en
ID  - DMGT_2022_42_2_a1
ER  - 
%0 Journal Article
%A Mojdeh, Doost Ali
%A Samadi, Babak
%A Yero, Ismael G.
%T Further Results on Packing Related Parameters in Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2022
%P 333-348
%V 42
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a1/
%G en
%F DMGT_2022_42_2_a1
Mojdeh, Doost Ali; Samadi, Babak; Yero, Ismael G. Further Results on Packing Related Parameters in Graphs. Discussiones Mathematicae. Graph Theory, Tome 42 (2022) no. 2, pp. 333-348. http://geodesic.mathdoc.fr/item/DMGT_2022_42_2_a1/