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

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

Abstract: Given a simple graph

G

, a set

C s u b s e t e q V (G)

is a neighborhood cover set if every edge and vertex of

G

belongs to some

G [v]

with

v i n C

, where

G [v]

denotes the subgraph of

G

induced by the closed neighborhood of the vertex

v

. Two elements of

E (G) c u p V (G)

are neighborhood-independent if there is no vertex

v i n V (G)

such that both elements are in

G [v]

. A set

S s u b s e t e q V (G) c u p E (G)

is neighborhood-independent if every pair of elements of

S

is neighborhood-independent. Let

h o_{m a t h r m n} (G)

be the size of a minimum neighborhood cover set and

a l p h a_{m a t h r m n} (G)

of a maximum neighborhood-independent set. Lehel and Tuza defined neighborhood-perfect graphs

G

as those where the equality

h o_{m a t h r m n} (G^{'}) = a l p h a_{m a t h r m 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.

Recommendations

Cites work

Cited in

(3)

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)