König graphs for 3-paths and 3-cycles

Given a set X, a König graph G for X is a graph with the following property: for every induced subgraph H of G, the maximum number of vertex-disjoint induced subgraphs from X in H is equal to the minimum number of vertices whose deletion from H results in a graph containing no graph in X as an induc...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2016-05, Vol.204, p.1-5
Main Authors: Alekseev, V.E., Mokeev, D.B.
Format: Article
Language:English
Subjects:
[formula omitted]-cover
[formula omitted]-packing
Algorithms
Deletion
Graph theory
Graphs
König graphs
Mathematical analysis
Recognition
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Given a set X, a König graph G for X is a graph with the following property: for every induced subgraph H of G, the maximum number of vertex-disjoint induced subgraphs from X in H is equal to the minimum number of vertices whose deletion from H results in a graph containing no graph in X as an induced subgraph. The purpose of this paper is to characterize all König graphs for X, where X has only the 3-path or X consists of the 3-path and 3-cycle. We give also polynomial-time algorithms for the recognition of König graphs for the 3-path and for finding the corresponding packing and cover numbers in graphs of this type.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2015.10.002