Two Kinds of Equicoverable Paths and Cycles

Abstract

Packing and covering are dual problems in graph theory. A graph \(G\) is called \(H\)-equipackable if every maximal \(H\)-packing in \(G\) is also a maximum \(H\)-packing in \(G\). Dually, a graph \(G\) is called \(H\)-equicoverable if every minimal \(H\)-covering in \(G\) is also a minimum \(H\)-covering in \(G\). In 2012, Zhang characterized two kinds of equipackable paths and cycles: \(P_k\)-equipackable paths and cycles, and \(M_k\)-equipackable paths and cycles. In this paper, we characterize \(P_k\)-equicoverable (\(k > 3\)) paths and cycles, and \(M_k\)-equicoverable (\(k > 2\)) paths and cycles.