## 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,),-relative-critical if γ(G) = γ and γ(G + e) = γ - 1 for all e ∈ E(H), where γ(G) denotes the domination number of G. The 2-relative-critical graphs and 3-relative-critical graphs are characterized in [7]. In [7], it is shown that the diameter of a connected 4-relativecritical graph is at most 5. In this paper, we construct five families of connected 4-relative-critical graphs of diameter 5 and show that a graph G is a connected 4-relative-critical graph of diameter 5 if and only if G belongs to one of these five families.

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

Pages (from-to) | 19-36 |

Number of pages | 18 |

Journal | Australasian Journal of Combinatorics |

Volume | 22 |

Publication status | Published - 2000 |

Externally published | Yes |

## ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics