EDGE COVERING COLORING AND FRACTIONAL EDGE COVERING COLORING

Abstract. Let G be a graph with edge set E(G). S E(G) is called an edge cover of G ifevery vertex of G is an end vertex of some edges in S. The edge covering chromatic numberof a graph G, denoted by Xc(G) is the maximum size of a partition of E(G) into edgecovers of G. It is known that for any graph G with minimum degree δ,δ- 1 The fractional edge covering chromatic number of a graph G, denoted by Xcf(G), is thefractional matching number of the edge covering hypergraph H of G whose vertices arethe edges of G and whose hyperedges the edge covers of G. In this paper, we studythe relation between X’c(G) and δ for any graph G, and give a new simple proof of theinequalities δ - 1 ≤ X’c(G) ≤ δ by the technique of graph coloring. For any graph G, wegive an exact formula of X’cf(G), that is,where A(G)=minand the minimum is taken over all noempty subsets S of V(G) and C[S] is the set of edgesthat have at least one end in S.

On Network Designs with Coding Error Detection and Correction Application

The detection of error and its correction is an important area of mathematics that is vastly constructed in all communication systems.Furthermore,combinatorial design theory has several applications like detecting or correcting errors in communication systems.Network(graph)designs(GDs)are introduced as a generalization of the symmetric balanced incomplete block designs(BIBDs)that are utilized directly in the above mentioned application.The networks(graphs)have been represented by vectors whose entries are the labels of the vertices related to the lengths of edges linked to it.Here,a general method is proposed and applied to construct new networks designs.This method of networks representation has simplified the method of constructing the network designs.In this paper,a novel representation of networks is introduced and used as a technique of constructing the group generated network designs of the complete bipartite networks and certain circulants.A technique of constructing the group generated network designs of the circulants is given with group generated graph designs(GDs)of certain circulants.In addition,the GDs are transformed into an incidence matrices,the rows and the columns of these matrices can be both viewed as a binary nonlinear code.A novel coding error detection and correction application is proposed and examined.

Some Class 1 Graphs on gc-colorings

An edge-coloring of a graph G is an coloring of a graph G is an edge-coloring of G such assignment of colors to all the edges of G. A go- that each color appears at each vertex at least g（v） times. The maximum integer k such that G has a go-coloring with k colors is called the gc-chromatic index of G and denoted by X＇gc （G）. In this paper, we extend a result on edge-covering coloring of Zhang X＇gc（ ） = δg（G）, and Liu in 2011, and give a new sufficient condition for a simple graph G to satisfy ＇ x＇gc（G）=δg（G）,where δg（G）=minv∈V（G）{[d（v）/g（v）]}.

On the Distribution of Laplacian Eigenvalues of a Graph

This paper presents some bounds on the number of Laplacian eigenvalues contained in various subintervals of [0, n] by using the matching number and edge covering number for G, and asserts that for a connected graph the Laplacian eigenvalue 1 appears with certain multiplicity. Furthermore, as an application of our result （Theorem 13）, Grone and Merris＇ conjecture [The Laplacian spectrum of graph II. SIAM J. Discrete Math., 7, 221-229 （1994）] is partially proved.

On the Relations of Graph Parameters and Its Total Parameters

In this paper we get some relations between α（G）, α＇（G）, β（G）, β＇（G） and αT（G）, βT（G）. And all bounds in these relations are best possible, where α（G）, α＇（G）,/3（G）, β（G）, αT（G） and βT（G） are the covering number, edge-covering number, independent number, edge-independent number （or matching number）, total covering number and total independent number, respectively.