pith. sign in

arxiv: 1807.01021 · v1 · pith:JITCBUZZnew · submitted 2018-07-03 · 🧮 math.CO

More on limited packings in graphs

classification 🧮 math.CO
keywords packinglimitednumbergraphverticesemphresulttight
0
0 comments X
read the original abstract

A set $B$ of vertices in a graph $G$ is called a \emph{$k$-limited packing} if for each vertex $v$ of $G$, its closed neighbourhood has at most $k$ vertices in $B$. The \emph{$k$-limited packing number} of a graph $G$, denoted by $L_k(G)$, is the largest number of vertices in a $k$-limited packing in $G$. The concept of the $k$-limited packing of a graph was introduced by Gallant et al., which is a generalization of the well-known packing of a graph. In this paper, we present some tight bounds for the $k$-limited packing number of a graph in terms of its order, diameter, girth, and maximum degree, respectively. As a result, we obtain the tight Nordhaus-Gaddum-type result of this parameter for general $k$. At last, we investigate the relationship among the open packing number, the packing number and $2$-limited packing number of trees.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.