Publications Repository - Gdańsk University of Technology

We consider (ψk−γk−1)-perfect graphs, i.e., graphs G for which ψk(H) =γk−1(H) for any induced subgraph H of G, where ψk and γk−1 are the k -path vertex cover number and the distance (k−1)-domination number, respectively. We study (ψk−γk−1)-perfect paths, cycles and complete graphs for k≥2. Moreover, we provide a complete characterisation of (ψ2−γ1)-perfect graphs describing the set of its forbidden induced subgraphs and providing the explicit characterisation of the structure of graphs belonging to this family.

Authors

• dr inż. Magda Dettlaff link open in new tab ,
• dr inż. Magdalena Lemańska link open in new tab ,
• Gabriel Semanišin,
• Rita Zuazua