For a graph G,P(G,λ)denotes the chromatic polynomial of G.Two graphs G and H are said to be chromatically equivalent,denoted by G～H,if P(G,λ)=p(H,λ).Let [G]={H|H～G}.If [G]={G},then G is said to be chromaticall...For a graph G,P(G,λ)denotes the chromatic polynomial of G.Two graphs G and H are said to be chromatically equivalent,denoted by G～H,if P(G,λ)=p(H,λ).Let [G]={H|H～G}.If [G]={G},then G is said to be chromatically unique.For a complete 5 partite graph G with 5n vertices, define θ(G)=(α(G,6)-2 n+1 -2 n-1 + 5)/2 n-2 ,where α(G,6) denotes the number of 6 independent partition s of G.In this paper, the authors show that θ(G)≥0 and determine all g raphs with θ(G)=0,1,2,5/2,7/2,4,17/4.By using these results the chromaticity of 5 partite graphs of the form G-S with θ(G)=0,1,2,5/2,7/2,4,17/4 is inve stigated,where S is a set of edges of G.Many new chromatically unique 5 partite graphs are obtained.展开更多
The notion of w-density for the graphs with positive weights on vertices and nonnegative weights on edges is introduced.A weighted graph is called w-balanced if its w-density is no less than the w-density of any subgr...The notion of w-density for the graphs with positive weights on vertices and nonnegative weights on edges is introduced.A weighted graph is called w-balanced if its w-density is no less than the w-density of any subgraph of it.In this paper,a good characterization of w-balanced weighted graphs is given.Applying this characterization,many large w-balanced weighted graphs are formed by combining smaller ones.In the case where a graph is not w-balanced,a polynomial-time algorithm to find a subgraph of maximum w-density is proposed.It is shown that the w-density theory is closely related to the study of SEW(G,w) games.展开更多
In this paper, some new classes of integral graphs are given in two new ways. It is proved that the problem of finding such integral graphs is equivalent to the problem of solving diophantine equations. Some classes a...In this paper, some new classes of integral graphs are given in two new ways. It is proved that the problem of finding such integral graphs is equivalent to the problem of solving diophantine equations. Some classes are infinite. The discovery of these classes is a new contribution to the search of such integral graphs.展开更多
基金Supported by the National Natural Science Foundation of China (1 0 0 61 0 0 3) and the ScienceFoundation of the State Education Ministry of China
文摘For a graph G,P(G,λ)denotes the chromatic polynomial of G.Two graphs G and H are said to be chromatically equivalent,denoted by G～H,if P(G,λ)=p(H,λ).Let [G]={H|H～G}.If [G]={G},then G is said to be chromatically unique.For a complete 5 partite graph G with 5n vertices, define θ(G)=(α(G,6)-2 n+1 -2 n-1 + 5)/2 n-2 ,where α(G,6) denotes the number of 6 independent partition s of G.In this paper, the authors show that θ(G)≥0 and determine all g raphs with θ(G)=0,1,2,5/2,7/2,4,17/4.By using these results the chromaticity of 5 partite graphs of the form G-S with θ(G)=0,1,2,5/2,7/2,4,17/4 is inve stigated,where S is a set of edges of G.Many new chromatically unique 5 partite graphs are obtained.
文摘The notion of w-density for the graphs with positive weights on vertices and nonnegative weights on edges is introduced.A weighted graph is called w-balanced if its w-density is no less than the w-density of any subgraph of it.In this paper,a good characterization of w-balanced weighted graphs is given.Applying this characterization,many large w-balanced weighted graphs are formed by combining smaller ones.In the case where a graph is not w-balanced,a polynomial-time algorithm to find a subgraph of maximum w-density is proposed.It is shown that the w-density theory is closely related to the study of SEW(G,w) games.
文摘In this paper, some new classes of integral graphs are given in two new ways. It is proved that the problem of finding such integral graphs is equivalent to the problem of solving diophantine equations. Some classes are infinite. The discovery of these classes is a new contribution to the search of such integral graphs.
