Back to Search Start Over

Some properties onf-edge covered critical graphs

Authors :
Jianfeng Hou
Jihui Wang
Guizhen Liu
Source :
Journal of Applied Mathematics and Computing. 24:357-366
Publication Year :
2007
Publisher :
Springer Science and Business Media LLC, 2007.

Abstract

Let G(V, E) be a simple graph, and let f be an integer function on V with 1 ≤ f(v) ≤ d(v) to each vertex v e V. An f-edge cover-coloring of a graph G is a coloring of edge set E such that each color appears at each vertex v e V at least f(v) times. The f-edge cover chromatic index of G, denoted by χ′fc(G), is the maximum number of colors such that an f-edge cover-coloring of G exists. Any simple graph G has an f-edge cover chromatic index equal to δf or δf - 1, where δf= minv e V{⌊ d(v)/f(v)⌋} Let G be a connected and not complete graph with χ′fc(G) =δf-1, if for each u, v e V and e = uv ∉ E, we have χ′fc(G + e) > χ′fc(G) then G is called an f-edge covered critical graph. In this paper, some properties on f-edge covered critical graph are discussed. It is proved that if G is an f-edge covered critical graph, then for each u, v e V and e = uv ∉ E there exists w e {u,v} with d(w) ≤ δf(f(w)+1) -2 such that w is adjacent to at least d(w) - δf + 1 vertices which are all δf-vertex in G.

Details

ISSN :
18652085 and 15985865
Volume :
24
Database :
OpenAIRE
Journal :
Journal of Applied Mathematics and Computing
Accession number :
edsair.doi...........f03ca406e2249d2c856916840692e6ab
Full Text :
https://doi.org/10.1007/bf02832324