Some Properties of Edge Covered Critical Graphs
Guizhen Liu · Advances in Mathematics · 2004
Let G be a graph with vertex set V(G) and edge set E(G). A subset of E(G) is called an edge covering of G if the subgraph induced by S is a spanning subgraph of G. The maximum number of edge coverings which construct a partition of E(G) is called the edge covered chromatic index of G and denoted by x'c(G). It is well known that δ - 1 ≤ x'c(G) ≤ δ. If x'c(G) = δ, then G is called a graph of CI class, otherwise G is called a graph of CII class. Let G be a connected and not complete graph of CII class. If for any u, v ∈ V(G) and e = uv (?) E(G), we have x'c(G + e) x'c(G), then G is called an edge covered critical graph. In this paper some properties of edge covered critical graphs are discussed. It is proved that if G is an edge covered critical graph, then for any u, v ∈ V(G) and uv (?) E(G) there is a vertex w ∈{u, v} such that d(w) ≤ 26 - 2 and w is adjacent to at least max{d(w) - δ + 1, 3d(w) - 4δ + 4} vertices with minimum degree in G.