R-annihilated and independent perfect neighborhood sets in chordal graphs

DOI10.1016/S0012-365X(99)00235-6MaRDI QIDQ1974533zbMATH OpenWikidataFDO

Authors Joël Puech

Publication date 28 May 2001

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0012-365X(99)00235-6

zbMATH Keywords

\(R\)-annihilated setchordal graphsdominating setindependent perfect neighborhood set

Mathematics Subject Classification ID

Paths and cycles (05C38) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Review text

Let \(\theta_i(G)\), \(\text{ra}(G)\) be the minimum cardinality of an independent perfect neighborhood set and an \(R\)-annihilated set, respectively. In 1999, Favaron and the author showed that the difference \(\theta_i(G)- \text{ra}(G)\) can be arbitrarily large; see \textit{O. Favaron} and \textit{J. Puech} [Discrete Math. 197/198, 269-284 (1999; Zbl 0957.05081)]. In the present paper, the author shows that the inequality \(\theta_i(G)\leq \text{ra}(G)\) holds for chordal graphs and for \(C_{1,2,2}\)-free graphs.

Recommendations

• k-Neighborhood-Covering and -Independence Problems for Chordal Graphs
• scientific article; zbMATH DE number 1229623
• On perfect neighborhood sets in graphs
• scientific article; zbMATH DE number 1416480
• Irredundant and perfect neighborhood sets in graphs and claw-free graphs
• A note on independence complexes of chordal graphs and dismantling
• Remarks on neighborhoods of independent sets and \((a,b,k)\)-critical graphs
• Independent sets in \(n\)-vertex \(k\)-chromatic \(\ell \)-connected graphs
• NEIGHBOURHOODS OF INDEPENDENT SETS FOR (a,b,k)-CRITICAL GRAPHS
• Chordal graphs and upper irredundance, upper domination and independence

Cited in

(3)

• Irredundant and perfect neighborhood sets in graphs and claw-free graphs
• The private neighbor concept
• scientific article; zbMATH DE number 1229623 (Why is no real title available?)

This page was built for publication: \(R\)-annihilated and independent perfect neighborhood sets in chordal graphs

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