Volume 19, No 4, 2012, P. 3-14

UDC 519.174.3
V. E. Alekseev, D. B. Mokeev 
König graphs with respect to 3-paths

Abstract:
We characterize the graphs whose each induced subgraph has the property: the packing number of induced 3-paths is equal to the corresponding vertex cover number.
Ill. 2, bibliogr. 4.

Keywords: subgraph packing, subgraph vertex covering, König graph, 3-path, forbidden subgraph.

Alekseev Vladimir Evgenyevich ¹
Mokeev Dmitrii Borisovich ^1,2
1. Nizhny Novgorod State University,
23 Gagarin ave., 603950 Nizhny Novgorod, Russia
2. National Research University “High school of economics”,
136 Rodionova str., 603093 Nizhny Novgorod, Russia
e-mail: aleve@rambler.ru, MokeevDB@gmail.com