Perfect matchings in paired domination vertex critical graphs

Perfect matchings in paired domination vertex critical graphs

0.00 Avg rating0 Votes
Article ID: iaor20123736
Volume: 23
Issue: 4
Start Page Number: 507
End Page Number: 518
Publication Date: May 2012
Journal: Journal of Combinatorial Optimization
Authors: , ,
Keywords: optimization
Abstract:

A vertex subset S of a graph G=(V,E) is a paired dominating set if every vertex of G is adjacent to some vertex in S and the subgraph induced by S contains a perfect matching. The paired domination number of G, denoted by γ pr (G), is the minimum cardinality of a paired dominating set of G. A graph with no isolated vertex is called paired domination vertex critical, or briefly γ pr ‐critical, if for any vertex v of G that is not adjacent to any vertex of degree one, γ pr (G-v)<γ pr (G). A γ pr ‐critical graph G is said to be k‐γ pr ‐critical if γ pr (G)=k. In this paper, we firstly show that every 4‐γ pr ‐critical graph of even order has a perfect matching if it is K 1,5‐free and every 4‐γ pr ‐critical graph of odd order is factor‐critical if it is K 1,5‐free. Secondly, we show that every 6‐γ pr ‐critical graph of even order has a perfect matching if it is K 1,4‐free.

Reviews

Required fields are marked *. Your email address will not be published.