𝔖 Bobbio Scriptorium
✦   LIBER   ✦

The diameter of domination k-critical graphs

✍ Scribed by Odile Favaron; David P. Sumner; Ewa Wojcicka

Publisher
John Wiley and Sons
Year
1994
Tongue
English
Weight
525 KB
Volume
18
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A graph is k‐domination‐critical if γ(G) = k, and for any edge e not in G, γ(G + e) = k − 1. In this paper we show that the diameter of a domination k‐critical graph with k ≧ 2 is at most 2__k__ − 2. We also show that for every k ≧ 2, there is a k‐domination‐critical graph having diameter [(3/2)k − 1]. We also show that the diameter of a 4‐domination‐critical graph is at most 5.

📜 SIMILAR VOLUMES

Hamiltonian properties of domination-cri
Hamiltonian properties of domination-critical graphs
✍ Ewa Wojcicka 📂 Article 📅 1990 🏛 John Wiley and Sons 🌐 English ⚖ 445 KB

## Abstract In this paper we show that every connected, 3‐γ‐critical graph on more than 6 vertices has a Hamiltonian path.

Codiameters of 3-connected 3-domination
Codiameters of 3-connected 3-domination critical graphs
✍ Yaojun Chen; Feng Tian; Bing Wei 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 110 KB

## Abstract A graph __G__ is 3‐domination critical if its domination number γ is 3 and the addition of any edge decreases γ by 1. Let __G__ be a 3‐connected 3‐domination critical graph of order __n__. In this paper, we show that there is a path of length at least __n__−2 between any two distinct ve

Hamiltonicity, diameter, domination, pac
Hamiltonicity, diameter, domination, packing, and biclique partitions of Mycielski's graphs
✍ David C. Fisher; Patricia A. McKenna; Elizabeth D. Boyer 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 785 KB

Let w(G), x(G), A(G), bp(G), diam(Gi), v(G), and y(G) be the clique number, chromatic number, adjacency matrix, biclique partition number, diameter, packing number, and domination number of a connected graph G. Mycielski constructed a graph g(G) with W@(G)) =w(G

On the k-diameter of k-regular k-connect
On the k-diameter of k-regular k-connected graphs
✍ D. Frank Hsu; Tomasz Łuczak 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 391 KB

We study the k-diameter of k-regular k-connected graphs. Among other results, we show that every k-regular k-connected graph on n vertices has k-diameter at most n/2 and this upper bound cannot be improved when n = 4k -6 + i(2k -4). In particular, the maximal 3-diameter of 3-regular graphs with 2n v