Edge Domination Critical Graphs

Abstract

A set of edges $D$ in a graph $G$ is a dominating set of edges if every edge not in $D$ is adjacent to at least one edge in $D$. The minimum cardinality of an edge dominating set of $G$ is the edge domination number of $G$, denoted $D_E(G)$. A graph $G$ is edge domination critical, or $EDC$, if for any vertex $v$ in $G$ we have $D_E(G–v)=D_E(G)–1$. Every graph $G$ must have an induced subgraph $F$ such that $F$ is $EDC$ and $D_E(G)=D_E(F)$. In this paper, we prove that no tree with more than 2 vertices is $EDC$, develop a forbidden subgraph characterization for the edge domination number of a tree, and we develop a construction that conserves the $EDC$ property.