On \(f\)-Edge Covered Critical Graphs

Let \( G(V, E) \) be a simple graph, and let \( f \) be an integer function defined on \( V \) with \( 1 \leq f(v) \leq 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}'(G) \). Any simple graph \( G \) has an \( f \)-edge covered chromatic index equal to \( \delta_f \) or \( \delta_f – 1 \), where \( \delta_f = \min \left\{\left\lfloor\frac{d(v)}{f(v)}\right\rfloor : v \in V(G)\right\} \). Let \( G \) be a connected and not complete graph with \( \chi_{fc}’ = \delta_f – 1 \). If for each \( u, v \in V \) and \( e = uv \notin E \), we have \( \chi_{fc}'(G+e) > \chi_{fc}'(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) \leq \delta_f(f(w) + 1) – 2 \) such that \( w \) is adjacent to at least \( \max \left\{d(w) – \delta_f f(w) + 1, (f(w) + 2)d(w) – \delta_f(f(w) + 1)^2 + f(w) + 3\right\} \) vertices which are all \( \delta_f \)-vertices in \( G \).