No label defined (Q3684148)
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 3906528
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 3906528 |
Statements
1984
0 references
dominating set
0 references
forbidden subgraph
0 references
0 references
0.9446284
0 references
0.9399609
0 references
0 references
0 references
0.92941177
0 references
0.9279999
0 references
0.92460686
0 references
0.92313564
0 references
0.92198133
0 references
[For the entire collection see Zbl 0547.00011.] A referencing-dominating set S in a simple graph G is a set of vertices of minimum possible cardinality such that both (1) each vertex outside S is adjacent to at least one vertex of S, and (2) no two vertices outside S have exactly the same neighbors in S. Let RD(G) be the cardinality of any such S, and if \({\mathcal C}\) is any class of graphs then let \(\psi_ h({\mathcal C})\) be the maximum number of vertices possible for any graph G in \({\mathcal C}\) with \(RD(G)=h\). The authors determine \(\psi_ h({\mathcal C})\) for several families \({\mathcal C}\) of graphs defined by forbidden subgraph characterizations. In particular, they show that for the families \({\mathcal P}\) and \({\mathcal O}\) of planar and outerplanar graphs (respectively), we have \(\psi_ h({\mathcal P})=7h-10\) for \(h\geq 4\) and \(\psi_ h({\mathcal O})=\lfloor (7h-3)\rfloor.\)
0 references