FoCM 2014 conference
Workshop A4 - Graph Theory and Combinatorics
No date set
Linear-time algorithms for neighborhood covering and independence on two superclasses of cographs
Xavier Sebastián Warnes
Universidad de Buenos Aires, Argentina - xwarnes@dc.uba.ar
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 said to be a neighborhood-independent set 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 as those where $\rho_{\mathrm n}(G') = \alpha_{\mathrm n}(G')$ for every induced subgraph $G'$ of $G$.\\
In this work we present linear-time algorithms for finding a minimum neighborhood cover set and a maximum neighborhood-independent set for two superclasses of cographs --- namely, $P_4$-tidy graphs and tree-cographs. We also give linear-time algorithms for recognizing neighborhood-perfect graphs within the same graph classes. These algorithms rely on the structure of the corresponding modular decomposition trees.
Joint work with Guillermo Durán (Universidad de Buenos Aires, Argentina) and Martín Safe (Universidad Nacional de General Sarmiento, Argentina).