25
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Neighborhood covering and independence on two superclasses of cographs

      Preprint

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          Given a simple graph \(G\), a set \(C \subseteq V(G)\) is a neighborhood cover set if every edge and vertex of \(G\) belongs to some \(G[v]\) with \(v \in C\), where \(G[v]\) denotes the subgraph of \(G\) induced by the closed neighborhood of the vertex \(v\). Two elements of \(E(G) \cup V(G)\) are neighborhood-independent if there is no vertex \(v\in V(G)\) such that both elements are in \(G[v]\). A set \(S\subseteq V(G)\cup E(G)\) is neighborhood-independent if every pair of elements of \(S\) is neighborhood-independent. Let \(\rho_{\mathrm n}(G)\) be the size of a minimum neighborhood cover set and \(\alpha_{\mathrm n}(G)\) of a maximum neighborhood-independent set. Lehel and Tuza defined neighborhood-perfect graphs \(G\) as those where the equality \(\rho_{\mathrm n}(G') = \alpha_{\mathrm n}(G')\) holds for every induced subgraph \(G'\) of \(G\). In this work we prove forbidden induced subgraph characterizations of the class of neighborhood-perfect graphs, restricted to two superclasses of cographs: \(P_4\)-tidy graphs and tree-cographs. We give as well linear-time algorithms for solving the recognition problem of neighborhood-perfect graphs and the problem of finding a minimum neighborhood cover set and a maximum neighborhood-independent set in these same classes.

          Related collections

          Author and article information

          Journal
          1601.00032

          Combinatorics,Discrete mathematics & Graph theory
          Combinatorics, Discrete mathematics & Graph theory

          Comments

          Comment on this article