A note on graphs which have upper irredundance equal to independence

DOI10.1016/0166-218X(93)90224-CMaRDI QIDQ686250zbMATH OpenFDO

Authors Kenneth Peters, Michael Jacobson

Publication date 20 March 1994

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0166-218X(93)90224-C

zbMATH Keywords

independence number irredundance number upper domination number

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (05C99)

Review text

A subset \(D\) of the vertex set \(V(G)\) of a graph \(G\) is called independent, if no two vertices of \(D\) are adjacent in \(G\). A set \(I\subseteq V(G)\) is called irredundant, if for each \(x\in I\) either \(x\) is isolated, or there exists \(y\in V(G)-I\) adjacent to \(x\) and to no other vertex of \(I\). The greatest number of vertices of an independent (or irredundant) set in \(G\) is called the independence number \(\beta(G)\) (or upper irredundance number \(\text{IR}(G)\) respectively) of the graph \(G\). If \(\text{IR}(H)=\beta(H)\) for all induced subgraphs \(H\) of \(G\), then \(G\) is called irredundant perfect. These graphs are characterized. Some further results are presented concerning the upper domination number.

Recommendations

Cites work

Cited in

(25)

This page was built for publication: A note on graphs which have upper irredundance equal to independence

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