Graphs such that all minimum dominating sets intersect all maximally independent sets (Q2839679)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 6187580
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Graphs such that all minimum dominating sets intersect all maximally independent sets |
scientific article; zbMATH DE number 6187580 |
Statements
12 July 2013
0 references
domination
0 references
domination number
0 references
independent set
0 references
inverse domination number
0 references
independence number
0 references
explosion
0 references
X-join
0 references
0.9309239
0 references
0.91969085
0 references
0.91709673
0 references
0.91168886
0 references
0.90300924
0 references
0.9003994
0 references
0.8987128
0 references
Graphs such that all minimum dominating sets intersect all maximally independent sets (English)
0 references
Motivated by a problem about the inverse domination number, \(DI\)-pathological graphs are introduced as the graphs in which every minimum dominating set intersects every maximally independent set. It is proved that if \(G\) is a connected \(DI\)-pathological graph with \(\gamma(G)=3\), then every vertex from a minimum dominating set \(D\) has at least two private neighbors in \(V(G)\setminus D\). Consequently the unique connected \(DI\)-pathological graph with \(\gamma(G)=3\) and with the least number of vertices and edges is found. Infinite families of the so-called exploded paths and exploded cycles are proved to be \(DI\)-pathological. (Explosion is also known in the literature as the X-join and was introduced in [\textit{G. Sabidussi}, Math. Z. 76, 385-401 (1961; Zbl 0109.16404)]).
0 references
