Total chromatic number of one kind of join graphs

The total chromatic number χ_T(G) of a graph G is the minimum number of colors needed to color the elements (vertices and edges) of G such that no adjacent or incident pair of elements receive the same color. G is called Type 1 if χ_T(G)=Δ(G)+1. In this paper we prove that the join of a complete inequibipartite graph K_n1,n2 and a path P_m is of Type 1.     

Variations on the Theorem of Birkhoff – von Neumann and Extensions

 The theorem of Birkhoff – von Neumann concerns bistochastic matrices (i.e., matrices with nonnegative real entries such that all row sums and all column sums are equal to one). We consider here real matrices with entries unrestricted in sign and we extend the notion of permutation matrices (integral bistochastic matrices); some generalizations of the theorem are derived by using elementary properties of graph theory. Received: October 10, 2000 Final version received: April 11, 2002     

简单完整正则平面图

对简单完整正则平面图的特性和结构进行了分析和讨论 ,找出了简单完整正则平面图的可能的种类 .此外 ,对各种简单完整正则平面图的色数进行了求解 ,并用不同的方法给出了各个简单完整正则平面图的作色方案 .     

Construction for bicritical graphs and k-extendable bipartite graphs

A graph G is said to be bicritical if G-u-v has a perfect matching for every choice of a pair of points u and v. Bicritical graphs play a central role in decomposition theory of elementary graphs with respect to perfect matchings. As Plummer pointed out many times, the structure of bicritical graphs is far from completely understood. This paper presents a concise structure characterization on bicritical graphs in terms of factor-critical graphs and transversals of hypergraphs. A connected graph G with at least 2k+2 points is said to be k-extendable if it contains a matching of k lines and every such matching is contained in a perfect matching. A structure characterization for k-extendable bipartite graphs is given in a recursive way. Furthermore, this paper presents an O(mn) algorithm for determining the extendability of a bipartite graph G, the maximum integer k such that G is k-extendable, where n is the number of points and m is the number of lines in G.     

An inequality for the group chromatic number of a graph

We give an inequality for the group chromatic number of a graph as an extension of Brooks’ Theorem. Moreover, we obtain a structural theorem for graphs satisfying the equality and discuss applications of the theorem.     

Partitioning series-parallel multigraphs intoν*-excluding edge covers

We prove that, for any given vertexν* in a series-parallel graph G, its edge set can be partitioned into k= min{k′(G) 1,δ(G)} subsets such that each subset covers all the vertices of G possibly except forν*, whereδ(G) is the minimum degree of G and k′(G) is the edge-connectivity of G. In addition, we show that the results in this paper are best possible and a polynomial time algorithm can be obtained for actually finding such a partition by our proof.     

Embedding a novel objective function in a two-phased local search for robust vertex coloring

In this paper, we propose a two-phased local search for vertex coloring. The algorithm alternately executes two closely interacting functionalities, i.e., a stochastic and a deterministic local search. The stochastic phase is basically based on biased random sampling that, according to a probability matrix storing the probability a vertex can be assigned to a color, iteratively constructs feasible colorings. The deterministic phase, instead, consists in assigning sequentially, according to a given ordering, each vertex to the color which causes the lowest increase of the solution penalty, and then, when the schedule is constructed, swap operations are executed to improve the performance. The interaction between the two phases is implemented by tunnelling information of what happened during a phase to the successive ones. Beyond the algorithm scheme, the novelty of the approach stems from the fact that the objective function is not minimizing the number of colors but a new penalty function. The proposed approach is tested on known benchmarks for the studied problem available on the public domain. From a comparison to the state of the art it appears that the proposed approach is robust and is able to achieve best known results.     

关于Tuza和Voigt的(Dm,m)-可选择性刻画定理

给出一个不属于Non-D的图,但该图却不是(Dm,m)-可选择的.这表明在Tuza Zs和Voigt M的Non-D定义和(Dm,m)-可选择图的特征化定理中存在一定的冲突.针对如上冲突,对Tuza Zs和Voigh M所给出的Non-D的定义,以及(Dm,m)-可选择图的特征化定理的证明进行了修正.     

Dammann光栅在光互连中的应用

本文将Ｄａｍｍａｎｎ光栅［１，２］应用于光互连，提出了用Ｄａｍｍａｎｎ光栅实现完全混洗的方法．一个２×２的Ｄａｍｍａｎｎ光栅与一个成像透镜的组合，具有与四焦点透镜类似的成像作用．像面上，像的位置与Ｄａｍｍａｎｎ光栅的位置有关，适当选择光栅的位置可以实现不同元素数目及不同元素密度的完全混洗．本文给出了有关的理论推导及实验结果．     

两类积图的邻点可区别全染色

本文.证明了,当n≥2时,Xat(K_n×K′_n)=2n;当p,q≥2时,Xat(C_(2p)×K_(2q))=2q 3,其中K_n×K′_n是两个不同标号完全图的积图,C_(2p)×K_(2q)是偶圈和偶阶完全图的积图.