On $f$-Edge Covered Critical Graphs

Abstract

Let $G(V,E)$ be a simple graph, and let $f$ be an integer function defined on $V$ with $1\le f(v)\le d(v)$ for each vertex $v\in V$. An $f$-edge covered colouring is an edge colouring $C$ such that each colour appears at each vertex $v$ at least $f(v)$ times. The maximum number of colours needed to $f$-edge covered colour $G$ is called the $f$-edge covered chromatic index of $G$ and denoted by ${\chi }_{fc}^{\prime }(G)$. Any simple graph $G$ has an $f$-edge covered chromatic index equal to ${\delta }_f$ or ${\delta }_f–1$, where ${\delta }_f=min\{\lfloor \frac{d(v)}{f(v)}\rfloor :v\in V(G)\}$. Let $G$ be a connected and not complete graph with ${\chi }_{fc}^{\prime }={\delta }_f–1$. If for each $u,v\in V$ and $e=uv\notin E$, we have ${\chi }_{fc}^{\prime }(G+e)>{\chi }_{fc}^{\prime }(G)$; then $G$ is called an $f$-edge covered critical graph. In this paper, some properties of $f$-edge covered critical graphs are discussed. It is proved that if $G$ is an $f$-edge covered critical graph, then for each $u,v\in V$ and $e=uv\notin E$ there exists $w\in \{u,v\}$ with $d(w)\le {\delta }_f(f(w)+1)–2$ such that $w$ is adjacent to at least $max\{d(w)–{\delta }_{f}f(w)+1,(f(w)+2)d(w)–{\delta }_f(f(w)+1{)}^2+f(w)+3\}$ vertices which are all ${\delta }_f$-vertices in $G$.