On graphs having one size of maximal open packings

MaRDI QIDQ5156331zbMATH OpenFDO

Authors Douglas F. Rall, Bert L. Hartnell

Publication date 15 October 2021

Full work available at URL https://arxiv.org/abs/2006.01616

zbMATH Keywords

open packingwell-covered graph

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Structural characterization of families of graphs (05C75)

Abstract: A set $P$ of vertices in a graph $G$ is an open packing if no two distinct vertices in $P$ have a common neighbor. Among all maximal open packings in $G$, the smallest cardinality is denoted $h{o}_L^{mo}(G)$ and the largest cardinality is $h{o}^{mo}(G)$. There exist graphs for which these two invariants are arbitrarily far apart. In this paper we begin the investigation of the class of graphs that have one size of maximal open packings. By presenting a method of constructing such graphs we show that every graph is the induced subgraph of a graph in this class. The main result of the paper is a structural characterization of those $G$ that do not have a cycle of order less than $15$ and for which $h{o}_L^{mo}(G)=h{o}^{mo}(G)$.

Recommendations

• Packing parameters in graphs
• scientific article; zbMATH DE number 1286740
• On open packing number of graphs
• Open packing number for some classes of perfect graphs
• A note on the open packing number in graphs

Cited in

(4)

• On \(k^+\)-neighbour packings and one-sided Hadwiger configurations
• An introduction to set-sized packing
• Open packing number for some classes of perfect graphs
• Packing parameters in graphs

This page was built for publication: On graphs having one size of maximal open packings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5156331)