|
This article is cited in 4 scientific papers (total in 4 papers)
On König graphs with respect to $P_4$
D. B. Mokeevab a Lobachevsky Nizhny Novgorod State University,
23 Gagarin Ave., 603950 Nizhny Novgorod, Russia
b Higher School of Economics in Nizhny Novgorod,
25/12 Bolshaya Pechyorskaya St., 603155 Nizhny Novgorod, Russia
Abstract:
We describe the class of graphs whose every induced subgraph has the property: The maximum number of disjoint induced $4$-paths is equal to the minimum size of the set of the vertices such that each $4$-path contains at least one of them. The description is based on the operation of replacing vertices by cographs which is to the vertices of the graphs obtained from bipartite graphs by subdividing their cycle edges. Bibliogr. 13.
Keywords:
packing of subgraphs, vertex covering of subgraphs, $4$-path, König graph.
Received: 30.12.2016 Revised: 24.01.2017
Citation:
D. B. Mokeev, “On König graphs with respect to $P_4$”, Diskretn. Anal. Issled. Oper., 24:3 (2017), 61–79; J. Appl. Industr. Math., 11:3 (2017), 421–430
Linking options:
https://www.mathnet.ru/eng/da875 https://www.mathnet.ru/eng/da/v24/i3/p61
|
Statistics & downloads: |
Abstract page: | 248 | Full-text PDF : | 84 | References: | 41 | First page: | 6 |
|