𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Matching properties in domination critical graphs

✍ Scribed by Nawarat Ananchuen; Michael D. Plummer

Publisher
Elsevier Science
Year
2004
Tongue
English
Weight
244 KB
Volume
277
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

A graph G is said to be k--critical if the size of any minimum dominating set of vertices is k, but if any edge is added to G the resulting graph can be dominated with k -1 vertices. A graph G is factor-critical if G -v has a perfect matching for every vertex v ∈ V (G) and is bicritical if G -u -v has a perfect matching for every pair of distinct vertices u; v ∈ V (G). In the present paper, it is shown that under certain assumptions regarding connectivity and minimum degree, a 3--critical graph G will be either factor-critical (if |V (G)| is odd) or bicritical (if |V (G)| is even).

πŸ“œ 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.

Domination critical graphs
Domination critical graphs
✍ David P Sumner; Pattie Blitch πŸ“‚ Article πŸ“… 1983 πŸ› Elsevier Science 🌐 English βš– 531 KB
Domination critical graphs
Domination critical graphs
✍ David P Sumner; Pattie Blitch πŸ“‚ Article πŸ“… 1983 πŸ› Elsevier Science 🌐 English βš– 531 KB

The smallest cardinality of any such dominating set is called the domination number of G and is denoted by y(G). The purpose of this paper is to initiate an investigation of those graphs which are critical in the following sense: For each v, u E V(G) with v not adjacent to u, y(G + vu) < y(G). Thus

Vertex domination-critical graphs
Vertex domination-critical graphs
✍ Jason Fulman; Denis Hanson; Gary Macgillivray πŸ“‚ Article πŸ“… 1995 πŸ› John Wiley and Sons 🌐 English βš– 293 KB