Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 2 min ago
PreprintCC BY 4.0arXiv

Vertex Removal and Vertex-Edge Domination

  • Minhui Li
  • Shumin Zhang
  • Fengming Dong
Open at sourcePDFDOICite

Abstract

A vertex v of a graph G ve-dominates every edge incident with a vertex in its closed neighborhood NG[v]. A set of vertices is a vertex-edge dominating set (ve-dominating set) if every edge of G is ve-dominated by some vertex in the set. The minimum cardinality of such a set is the vertex-edge domination number γve(G), also known as the isolation number. In this paper, we study the effect of vertex removal on γve(G), establish sharp bounds on γve(G−v) and characterize the vertices whose removal decreases, preserves, or increases γve(G). Let V0(G) and V+(G) denote the sets of vertices whose removal preserves and increases γve(G), respectively, and let Vfix0(G) consist of the vertices in V0(G) belonging to every minimum ve-dominating set. We prove that |V0(G)|≥3|Vfix0(G)|+∑v∈ V+(G) (γve(G−v)−γve(G)+1). In particular, |V0(G)|≥ 2|V+(G)|. We also prove that every vertex in Vfix0(G) lies on a cycle and that V0(T)≠∅ for every tree T of order at least three.

Related

  1. Graphs with Large Vertex–Edge Roman {2}-Domination Number
    Ahlam Almulhim
    MathematicsPeer-reviewedCC BY 4.0General mathematicsCrossref
  2. A 50-Vertex Cubic Counterexample to the Domination-versus-Edge-Domination Conjecture
    Koyar Afrasyab
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. Robustness asymmetry under edge failures: A unified framework based on structural controllability and power domination
    Bader Alwasel
    PLOS OnePeer-reviewedCC BYFull textStatisticsPLOSEurope PMCPMC
  4. The Erdős-Hajnal Property for the six-vertex Graph with Edge Set {ab,bc,cd,de,af,bf,df}
    Viet-Hoang Tran, Tan M. Nguyen
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  5. Bricks in which every vertex is incident with a forcing edge
    Xinyu Dai, Fuliang Lu, Yaxian Zhang
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{li2026vertex,
  title = {{Vertex Removal and Vertex-Edge Domination}},
  author = {Minhui Li and Shumin Zhang and Fengming Dong},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.26912},
  eprint = {2610.26912},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.26912},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Vertex Removal and Vertex-Edge Domination
AU  - Minhui Li
AU  - Shumin Zhang
AU  - Fengming Dong
PY  - 2026
DA  - 2026/10/17
PB  - arXiv
DO  - 10.48550/arxiv.2610.26912
UR  - https://arxiv.org/abs/2610.26912
AB  - A vertex v of a graph G ve-dominates every edge incident with a vertex in its closed neighborhood N_G[v]. A set of vertices is a vertex-edge dominating set (ve-dominating set) if every edge of G is ve-dominated by some vertex in the set. The minimum cardinality of such a set is the vertex-edge domination number γ_ve(G), also known as the isolation number. In this paper, we study the effect of vertex removal on γ_ve(G), establish sharp bounds on γ_ve(G−v) and characterize the vertices whose removal decreases, preserves, or increases γ_ve(G). Let V^0(G) and V^+(G) denote the sets of vertices whose removal preserves and increases γ_ve(G), respectively, and let V_fix^0(G) consist of the vertices in V^0(G) belonging to every minimum ve-dominating set. We prove that |V^0(G)|≥3|V_fix^0(G)|+∑_v∈ V^+(G) (γ_ve(G−v)−γ_ve(G)+1). In particular, |V^0(G)|≥ 2|V^+(G)|. We also prove that every vertex in V_fix^0(G) lies on a cycle and that V^0(T)≠∅ for every tree T of order at least three.
ER  -