Some properties on \(f\)-edge covered critical graphs (Q2454989)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Some properties on \(f\)-edge covered critical graphs
scientific article

    Statements

    Some properties on \(f\)-edge covered critical graphs (English)
    0 references
    0 references
    0 references
    0 references
    22 October 2007
    0 references
    Let \(N_G(v)\) denote the neighborhood of \(v\) and let \(d(v)= |N_G(v)|\) be the degree of \(v\) in a simple graph \(G= (V,E)\). Let \(f\) be an integer function on \(V\) with \(1\leq f(v)\leq d(v)\) for each vertex \(v\in V\). Any graph \(G\) has an \(f\)-edge cover chromatic index equal to \(\delta_f\) or \(\delta_f-1\), where \(\delta_f=\min_{v\in V}\{\lfloor d(v)/f(v)\rfloor\}\). The authors prove the following result: Let \(G\) be an \(f\)-edge covered critical graph. Then for all \(u,v\in V\) and \(e= uv\not\in 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 \(d(w)- \delta_f f(w)+ 1\) vertices which are all \(\delta_f\)-vertices of \(G\).
    0 references
    \(f\)-edge cover-coloring
    0 references
    \(f\)-edge covered critical graph
    0 references
    \(f\)-edge cover chromatic index
    0 references

    Identifiers