Article in volume
Authors:
Title:
Graphs with unique maximum packing of closed neighborhoods
PDFSource:
Discussiones Mathematicae Graph Theory 42(3) (2022) 779-797
Received: 2019-03-26 , Revised: 2020-01-20 , Accepted: 2020-01-20 , Available online: 2020-02-17 , https://doi.org/10.7151/dmgt.2304
Abstract:
A packing of a graph $G$ is a subset $P$ of the vertex set of $G$ such that the
closed neighborhoods of any two distinct vertices of $P$ do not intersect. We
study graphs with a unique packing of the maximum cardinality. We present
several general properties for such graphs. These properties are used to
characterize the trees with a unique maximum packing. Two characterizations
are presented where one of them is inductive based on five operations.
Keywords:
unique maximum packing, closed neighborhoods, trees
References:
- N. Biggs, Perfect codes in graphs, J. Combin. Theory Ser. B 15 (1973) 289–296.
https://doi.org/10.1016/0095-8956(73)90042-7 - B. Brešar, K. Kuenzel and D. F. Rall, Graphs with a unique maximum open packing (2019).
arXiv: 1901.09859 - M.P. Dobson, E. Hinrichsen and V. Leoni, Generalized limited packings of some graphs with a limited number of $P_4$-partners, Theoret. Comput. Sci. 579 (2015) 1–8.
https://doi.org/10.1016/j.tcs.2014.11.014 - R.D. Dutton, Global domination and packing numbers, Ars Combin. 101 (2011) 489–501.
- A. Gagarin and V. Zverovich, The probabilistic approach to limited packings in graphs, Discrete Appl. Math. 184 (2015) 146–153.
https://doi.org/10.1016/j.dam.2014.11.017 - R. Gallant, G. Gunther, B. Hartnell and D.F. Rall, Limited packings in graphs, Discrete Appl. Math. 158 (2010) 1357–1364.
https://doi.org/10.1016/j.dam.2009.04.014 - G. Gunther, B.L. Hartnell, L.R. Markus and D.F. Rall, Graphs with unique minimum dominating sets, Congr. Numer. 101 (1994) 55–63.
- T.W. Haynes and M.A. Henning, Trees with unique minimum total dominating sets, Discuss. Math. Graph Theory 22 (2002) 233–246.
https://doi.org/10.7151/dmgt.1172 - M.A. Henning, C. Löwenstein and D. Rautenbach, Dominating sets, packings, and the maximum degree, Discrete Math. 311 (2011) 2031–2036.
https://doi.org/10.1016/j.disc.2011.04.030 - G. Hopkins and W. Staton, Graphs with unique maximum independent sets, Discrete Math. 57 (1985) 245–251.
https://doi.org/10.1016/0012-365X(85)90177-3 - M.-J. Jou and G.J. Chang, The number of maximum independent sets in graphs, Taiwanese J. Math. 4 (2000) 685–695.
https://doi.org/10.11650/twjm/1500407302 - K. Junosza-Szaniawski and P. Rzążewski, On the number of $2$-packings in a connected graph, Discrete Math. 312 (2012) 3444–3450.
https://doi.org/10.1016/j.disc.2012.02.005 - A.P. Kazemi, B. Pahlavsay and R.J. Stones, Cartesian product graphs and $k$-tuple total domination, Filomat 32 (2018) 6713–6731.
https://doi.org/10.2298/FIL1819713K - S. Klavžar, I. Peterin and I.G. Yero, Graphs that are simultaneously efficient open domination and efficient closed domination graphs, Discrete Appl. Math. 217 (2017) 613–621.
https://doi.org/10.1016/j.dam.2016.09.027 - A. Meir and J.W. Moon, Relations between packing and covering numbers of a tree, Pacific J. Math. 61 (1975) 225–233.
https://doi.org/10.2140/pjm.1975.61.225 - D.A. Mojdeh, B. Samadi, A. Khodkar and H.R. Golmohammadi, On the packing numbers in graphs, Australas. J. Combin. 71 (2018) 468–475.
- I. Sahul Hamid and S. Saravanakumar, Packing parameters in graphs, Discuss. Math. Graph Theory 35 (2015) 5–16.
https://doi.org/10.7151/dmgt.1775
Close