Neighborhood covering and independence on $$P_4$$P4-tidy graphs and tree-cographs

Guillermo Durán (), Martín Safe () and Xavier Warnes ()
Additional contact information
Guillermo Durán: Universidad de Buenos Aires
Martín Safe: Universidad Nacional del Sur
Xavier Warnes: Universidad de Buenos Aires

Annals of Operations Research, 2020, vol. 286, issue 1, No 4, 55-86

Abstract: Abstract Given a simple graph G, a set $$C \subseteq V(G)$$C⊆V(G) is a neighborhood cover set if every edge and vertex of G belongs to some G[v] with $$v \in C$$v∈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)$$E(G)∪V(G) are neighborhood-independent if there is no vertex $$v\in V(G)$$v∈V(G) such that both elements are in G[v]. A set $$S\subseteq V(G)\cup E(G)$$S⊆V(G)∪E(G) is neighborhood-independent if every pair of elements of S is neighborhood-independent. Let $$\rho _{\mathrm {n}}(G)$$ρn(G) be the size of a minimum neighborhood cover set and $$\alpha _{\mathrm {n}}(G)$$α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^\prime ) = \alpha _{\mathrm {n}}(G^\prime )$$ρn(G′)=αn(G′) holds for every induced subgraph $$G^\prime $$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$$P4-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. Finally we prove that although for complements of trees finding these optimal sets can be achieved in linear-time, for complements of bipartite graphs it is $$\mathrm {NP}$$NP-hard.

Keywords: Forbidden induced subgraphs; Neighborhood-perfect graphs; $$P_4$$ P 4 -tidy graphs; Tree-cographs; Recognition algorithms; Co-bipartite graphs; 05C17; 05C69; 05C75 (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10479-017-2712-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:286:y:2020:i:1:d:10.1007_s10479-017-2712-z

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-017-2712-z

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().