Neighborhood covering and independence on P₄-tidy graphs and tree-cographs

DOI10.1007/S10479-017-2712-ZzbMATH Open1441.05087arXiv1601.00032OpenAlexW2769048201MaRDI QIDQ2178334FDOQ2178334

Authors: Guillermo Durán, Martín D. Safe, Xavier Warnes 

Publication date: 11 May 2020

Published in: Annals of Operations Research (Search for Journal in Brave)

Abstract: Given a simple graph $G$, a set $CsubseteqV(G)$ is a neighborhood cover set if every edge and vertex of $G$ belongs to some $G[v]$ with $vinC$, where $G[v]$ denotes the subgraph of $G$ induced by the closed neighborhood of the vertex $v$. Two elements of $E(G)cupV(G)$ are neighborhood-independent if there is no vertex $vinV(G)$ such that both elements are in $G[v]$. A set $SsubseteqV(G)cupE(G)$ is neighborhood-independent if every pair of elements of $S$ is neighborhood-independent. Let $h{o}_{mathrmn}(G)$ be the size of a minimum neighborhood cover set and $alph{a}_{mathrmn}(G)$ of a maximum neighborhood-independent set. Lehel and Tuza defined neighborhood-perfect graphs $G$ as those where the equality $h{o}_{mathrmn}(G^{\prime })=alph{a}_{mathrmn}(G^{\prime })$ holds for every induced subgraph $G^{\prime }$ 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.

Full work available at URL: https://arxiv.org/abs/1601.00032

Recommendations

• k-Neighborhood-Covering and -Independence Problems for Chordal Graphs
• \(k\)-trees and covering invariants of total closed neighborhood graphs
• scientific article; zbMATH DE number 1145229
• On the \(b\)-coloring of \(P_{4}\)-tidy graphs
• scientific article; zbMATH DE number 29793
• Partitioning \(P_4\)-tidy graphs into a stable set and a forest
• scientific article; zbMATH DE number 1375569
• scientific article; zbMATH DE number 1963455
• The neighborhood union of independent sets and hamiltonicity of graphs
• Hitting subgraphs in \(P_4\)-tidy graphs

zbMATH Keywords

recognition algorithmsforbidden induced subgraphstree-cographsco-bipartite graphs\(P_4\)-tidy graphsneighborhood-perfect graphs

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Structural characterization of families of graphs (05C75) Perfect graphs (05C17)

Cites Work

• Depth-first search and the vertex cover problem
• Modular decomposition and transitive orientation
• On computing a longest path in a tree
• Linear time solvable optimization problems on graphs of bounded clique-width
• On the Algorithmic Complexity of Total Domination
• Total domination in graphs
• On the hardness of approximating minimum vertex cover
• The strong perfect graph theorem
• Transitiv orientierbare Graphen
• Clique r-Domination and Clique r-Packing Problems on Dually Chordal Graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• The complexity of first-order and monadic second-order logic revisited
• A survey of the algorithmic aspects of modular decomposition
• New results on induced matchings
• Algorithmic aspects of clique-transversal and clique-independent sets
• Simpler Linear-Time Modular Decomposition Via Recursive Factorizing Permutations
• Algorithmic Aspects of Neighborhood Numbers
• On a property of the class of n-colorable graphs
• A multivariate interlace polynomial and its computation for graphs of bounded clique-width
• A Fast Algorithm for the Decomposition of Graphs and Posets
• The neighbourhood number of a graph
• Linear algorithms on recursive representations of trees
• Efficient and practical algorithms for sequential modular decomposition
• A note on the total domination number of a tree
• Strong tree-cographs are Birkhoff graphs
• On semi-\(P_ 4\)-sparse graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Coordinated graphs and clique graphs of clique-Helly perfect graphs
• Neighborhood perfect graphs
• Neighbourhood-perfect line graphs
• Minimal non-neighborhood-perfect graphs

Cited In (3)

• Hitting subgraphs in \(P_4\)-tidy graphs
• Partitioning \(P_4\)-tidy graphs into a stable set and a forest
• Neighborhood perfect graphs

This page was built for publication: Neighborhood covering and independence on \(P_4\)-tidy graphs and tree-cographs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2178334)