pipette
ESEspañol

Vertex Removal and Vertex-Edge Domination

Minhui Li, Shumin Zhang, and Fengming Dong

Preprint

In the authors' words

A vertex of a graph -dominates every edge incident with a vertex in its closed neighborhood . A set of vertices is a vertex-edge dominating set (-dominating set) if every edge of is -dominated by some vertex in the set. The minimum cardinality of such a set is the vertex-edge domination number , also known as the isolation number. In this paper, we study the effect of vertex removal on , establish sharp bounds on and characterize the vertices whose removal decreases, preserves, or increases . Let and denote the sets of vertices whose removal preserves and increases , respectively, and let consist of the vertices in belonging to every minimum -dominating set. We prove that \[ |V^0(G)|\geq3|V_{fix}^0(G)|+\sum_{v\in V^+(G)} \bigl(\gamma_{ve}(G-v)-\gamma_{ve}(G)+1\bigr). \] In particular, . We also prove that every vertex in lies on a cycle and that for every tree of order at least three.

Main resultThe abstract does not state a limitation.

Appeared: Wednesday, October 21. arXiv. Preprint, not yet peer-reviewed.