## Abstract

The linear programmimg formulations of graph domination and graph packing are duals. Likewise, fractional efficient domination for a graph G has as its dual the parameter discussed in this paper, namely the minimum weight of a real-valued function f: V(G) → [0, ∞) such that the sum of the weights in each closed neighborhood is at least its cardinality. The fractional and integer "closed neighborhood order domination" parameters, W_{f} and W, are introduced. Deciding if W(G) ≤ k is an NPcomplete problem even for just the class of bipartite graphs or chordal graphs. A linear time algorithm for computing W(T) for an arbitrary tree T is presented. Other theoretical and computational results are presented.

Original language | English |
---|---|

Pages (from-to) | 77-88 |

Number of pages | 12 |

Journal | Australasian Journal of Combinatorics |

Volume | 17 |

Publication status | Published - 1998 |

Externally published | Yes |

## ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics