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

      0 references
      0 references
      1984
      0 references
      dominating set
      0 references
      forbidden subgraph
      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

      Identifiers