## Abstract

Let G be a spanning subgraph of K_{s,s} and let H be the complement of G relative to K_{s,s}; that is, K_{s,s} = G ⊕ H is a factorization of K_{s,s}. The graph G is γ-critical relative to K_{s,s} if γ(G) = γand γ(G + e) = γ - 1 for all e ∈ E(H), where γ(G) denotes the domination number of G. We investigate γ-critical graphs for small values of γ. The 2-critical graphs and 3-critical graphs are characterized. A characterization of disconnected 4-critical graphs is presented. We show that the diameter of a connected 4-critical graph is at most 5 and that this bound is sharp. The diameter of a connected γ-critical graph, γ ≥ 4, is shown to be at most 3γ - 6.

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

Pages (from-to) | 115-126 |

Number of pages | 12 |

Journal | Australasian Journal of Combinatorics |

Volume | 18 |

Publication status | Published - 1998 |

Externally published | Yes |

## ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics