Equitable graph of a graph
Starting from the concept of a dominating set of a graph \(G = V \cup E\), the author defines a set \(D\) to be an equitable dominating set if it is: a) dominating and b) for every \(v \in V - D\) there is a \(u \in D\) adjacent to \(v\) such that \(|d(u) - d(v)| \leq 1\). NEWLINENEWLINENEWLINE \(\delta^e(G)\) denotes the size of a smallest equitable dominating set in \(G\). Two vertices of \(G\) are said to be degree-equitable if their degrees differ by at most \(1\).NEWLINENEWLINEThe equitable graph \(G^e\) of \(G = V \cup E\) has \(V(G^e) = V\) and for \(u,v \in V\) one has \(uv \in E(G^e)\) iff \(u\) and \(v\) are degree-equitable.NEWLINENEWLINEThese definitions imply \(\delta(G^e) \leq \delta^e(G)\) where \(\delta(H)\) is the domination number of \(H\); and equality holds if for all \(u \in V\) in \(G\) the vertices equitable with \(u\) are adjacent to \(u\). However, the converse is not true in general. On the other hand, \(\delta(G^e) < \delta^e(G)\) iff for any minimum dominating set \(D\) of \(G^e\) there is a vertex \(u \in V - D\) such that no neighbor of \(u\) in \(G^e\) which is also a neighbor of \(u\) in \(G\), lies in \(D\).NEWLINENEWLINEMoreover, \(\delta(G) = \delta^e(G)\) iff \(G\) has a minimum dominating set \(D\) such that for every \(u \in V - D\) at least one of its neighbors in \(G\) is degree-equitable and lies in \( D\). On the other hand, in general, \(\delta^e(G) - \delta(G)\) can be arbitrarily large (see, e.g., \(K_{1,r}\)). The author also exhibits classes of graphs where \(\delta = \delta^e\).
- New families of equitable graphs
- Equitable domination in graphs
- Equitable associate graph of a graph
- Equitable edge domination in graphs
- scientific article; zbMATH DE number 6704963 (Why is no real title available?)
- A note on the equitable covering and equitable packing of a graph
- Bounds for out degree equitable domination numbers in graphs
- Degree equitable chromatic number of a graph
- Degree equitable domination on graphs
- Degree equitable restrained double domination in graphs
- Complementary equitably totally disconnected equitable domination in graphs
- Equitable fair domination in graphs
- _e-graphs of graphs
- Excellent-just excellent degree equitable domination in fuzzy graphs
- A study on the inherent Inj-equitable graphs
- Semientire equitable dominating graphs
- A linear time algorithm for minimum equitable dominating set in trees
- Equitably strong non-split equitable domination in graphs
This page was built for publication: Equitable graph of a graph
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2869949)
