Domination-compliance graphs are planar (Q2716664)

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 1599302
Language Label Description Also known as
default for all languages
No label defined
    English
    Domination-compliance graphs are planar
    scientific article; zbMATH DE number 1599302

      Statements

      0 references
      0 references
      18 October 2001
      0 references
      planar graph
      0 references
      tournament
      0 references
      domination
      0 references
      compliance
      0 references
      domination-compliance graph
      0 references
      Domination-compliance graphs are planar (English)
      0 references
      A tournament \(T\) is considered. Two vertices \(x\), \(y\) of \(T\) are a dominating (or compliant) pair, if for each vertex \(z\) distinct from both \(x\) and \(y\) either \(x\), or \(y\) beats \(z\) (or is beaten by \(z\), respectively). The domination graph \(\text{dom}(T)\) (or compliance graph \(\text{com}(T)\)) of \(T\) is an undirected graph whose vertex set is equal to that of \(T\) and in which two vertices are adjacent if and only if they form a dominating (or, respectively, compliant) pair in \(T\). The domination-compliance graph \(\text{DC}(T)\) of \(T\) is the union \(\text{dom}(T)\cup \text{com}(T)\). The structure of \(\text{DC}(T)\) is studied. The main result states that if \(T\) is a tournament whose domination graph is made up of nontrivial components, then \(\text{DC}(T)\) is planar.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references