临界h棱连通图的最大棱数及最大图的结构(Ⅱ)——指数不小于h+3的情形

本文通过临界h棱连通图的指数概念,讨论了指数不小于h+3的p阶临界h(≥4)棱连通图的最大棱数问题。

关于（k—1）容错直径或k直径的最大图

本文确定了阶为ｎ，（ｋ－１）容错直径为ｄ或ｋ直径为ｄ的ｋ连通图Ｇ的边数的最大值，并给出了相应的最大图．

给定权集的赋权双圈图的谱半径(英文)

令BWn,n,n＋1表示阶为n的赋权双圈图的集合，W = {w1,w2,...,wn＋1}，其中w1 ≥ w2 ≥... ≥ wn＋1 〉 0为权集合．本文确定了它们中谱半径最大的赋权双圈图的结构及部分权值的分布情况．

给定顶点数和边数的连通图的Q-谱半径的界(英文)

图的无符号拉普拉斯矩阵是图的邻接矩阵和度对角矩阵的和,其特征值记为q_1≥q_2≥…≥q_n.设C(n,m)是由n个顶点m条边的连通图构成的集合,这里1≤n-1≤m≤((n/2)).如果对于任意的G∈C(n,m)都有q_1(G~*)≥q_1(G)成立,图G~*∈C(n,m)叫做最大图.这篇文章证明了对任意给定的正整数a=m-n+1,如果n>-1/2+a+1/2(1+12a+12a^2)^(1/2),那么n<q_1(G~*)<n+1,进而得到,对任意的G∈C(n,m),只要n>-1/2+a+1/2(1+12a+12a^2)^(1/2),就有q_1(G)<n+1.

关于无爪图最大团数的一个估计

设图 G=( V,E)是一个简单连通图 ,称所有同边 e关联的边集为 e的边邻集 ,记为 Γ( e) ,并称 | Γ( e) |为 e的边度 ,记为 d( e) .

Application of SAGE algorithm in PET image reconstruction using modified ordered subsets

A new method that uses a modified ordered subsets （MOS） algorithm to improve the convergence rate of space-alternating generalized expectation-maximization （SAGE） algorithm for positron emission tomography （PET） image reconstruction is proposed.In the MOS-SAGE algorithm,the number of projections and the access order of the subsets are modified in order to improve the quality of the reconstructed images and accelerate the convergence speed.The number of projections in a subset increases as follows：2,4,8,16,32 and 64.This sequence means that the high frequency component is recovered first and the low frequency component is recovered in the succeeding iteration steps.In addition,the neighboring subsets are separated as much as possible so that the correlation of projections can be decreased and the convergences can be speeded up.The application of the proposed method to simulated and real images shows that the MOS-SAGE algorithm has better performance than the SAGE algorithm and the OSEM algorithm in convergence and image quality.

Accelerating SAGE algorithm in PET image reconstruction by rescaled block-iterative method

A new method to accelerate the convergent rate of the space-alternatinggeneralized expectation-maximization (SAGE) algorithm is proposed. The new rescaled block-iterativeSAGE (RBI-SAGE) algorithm combines the RBI algorithm with the SAGE algorithm for PET imagereconstruction. In the new approach, the projection data is partitioned into disjoint blocks; eachiteration step involves only one of these blocks. SAGE updates the parameters sequentially in eachblock. In experiments, the RBI-SAGE algorithm and classical SAGE algorithm are compared in theapplication on positron emission tomography (PET) image reconstruction. Simulation results show thatRBI-SAGE has better performance than SAGE in both convergence and image quality.

On Simple MCD-Graphs

A simple graph G on n vettices is said to be a simple MCD-graph if G has no two cyties having the same length and has the maximum possible number of edges.Two results of the number of cy cles in G are given by introdueing the Concept of a path decomposition and by them,the following theorem is proved:If G is a simple MCD-graph,then G is not a 2-connected planar graph and for all n except seven integer,G is not a 2-connected graph on n vertices containing a subgraph homeomor phic to K_4.

The Complete Chromatic Number of Maximal Outerplane Graphs

Let G be a maximal outerplane graph and X0(G) the complete chromatic number of G. This paper determines exactly X0(G) for △(G)≠5 and proves 6≤X0.(G)≤7 for △(G) = 5, where △(G) is the maximum degree of vertices of G.

BLOCKING CUTSET OF A NETWORK AND ITS DETERMINATION (Ⅱ) Research on the Blocking Flow in a Transport Network

ransport network in the paper is defined as follows: (1) Connected and directed network without self loop;(2) There is only one source vertex with zero in degree; (3) There is only one sink vertex with zero out degree;(4) The capacity of every arc is non negative integer Blocking flow is a kind of flow commonly happened in a transport network . Its formation is due to the existance of a blocking cutset in the network. In this paper the fundamental concepts and theorems of the blocking flow and the blocking cutset are introduced and a linear programming model for determining the blocking cutset in a network is set up. In order to solve the problem by graph theoretical approach a method called 'two way flow augmenting algorithm' is developed. With this method an iterative procedure of forward and backward flow augmenting process is used to determine whether a given cutset is a blocking one.

Reconstruction of Tomographic Images from a Few Views by New Maximum Entropy Approach

A new algorithm for the reconstruction of tomographic images from a few views is presented. A variable metric method is used to solve the unconstrained optimization problem which resulted from the analysis by use of the maximum ent ropy formalism. The numerical simulation is used to study the reconstruction eff ect on the different asymmetric functions. The results show that the reconstruct ion accuracy is satisfactory.

MAP based blocking artifact reduction for DCT domain distributed video coding

This paper proposes a maximum a posteriori （MAP） based blocking artifact reduction algorithm for discrete cosine transform （DCT） domain distributed video coding, in which the SI and the initial reconstructed Wyner-Ziv （WZ） frame are utilized to further estimate the original WZ frame. Though the MAP estimate improves quality of the artifact region, it also leads to over-smoothness and decreases quality of the non-artifact region. To overcome this problem, a criterion is presented to discriminate the artifact and the non-artifact region in the initial reconstructed WZ frame, and only the artifact region is updated with the MAP estimate. Simulation results show that the proposed algorithm provides obvious improvement in terms of both objective and subjective evaluations.

A Graph-based Ant Colony Optimization Approach for Integrated Process Planning and Scheduling

This paper considers an ant colony optimization algorithm based on AND/OR graph for integrated process planning and scheduling(IPPS). Generally, the process planning and scheduling are studied separately. Due to the complexity of manufacturing system, IPPS combining both process planning and scheduling can depict the real situation of a manufacturing system. The IPPS is represented on AND/OR graph consisting of nodes, and undirected and directed arcs. The nodes denote operations of jobs, and undirected/directed arcs denote possible visiting path among the nodes. Ant colony goes through the necessary nodes on the graph from the starting node to the end node to obtain the optimal solution with the objective of minimizing makespan. In order to avoid local convergence and low convergence, some improved strategy is incorporated in the standard ant colony optimization algorithm. Extensive computational experiments are carried out to study the influence of various parameters on the system performance.

Maximum Genus and Girth of a Graph

It is known (for example, see [4]) that the maximum genus of a graph is mainly determined by the Betti deficiency of the graph. In this paper, we establish a best upper bound on the Betti deficiency of a graph bounded by its independence number and girth, and immediately obtain a new result on the maximum genus.

The Total Chromatic Number of Graphs with an Unique Major Vertex of Degree Four

The total chromatic number χ T(G) of a graph G is the least number k such that G admits a total coloring with k colors. In this paper, it is proved that χ T(G)=Δ(G)+1 for all graphs with an unique major vertex of degree 4.

THE CONNECTIVITY OF MAXIMUM MATCHING GRAPHS

The maximum matching graph of a graph has a vertex for each maximummatching and an edge for each pair of maximum matchings which differ by exactly oneedge. In this paper, we prove that the connectivity of maximum matching graph of abipartite graph is equal to its minimum degree.

Acyclic improper colouring of graphs with maximum degree 4

A k-colouring （not necessarily proper） of vertices of a graph is called acyclic, if for every pair of distinct colours i and j the subgraph induced by the edges whose endpoints have colours i and j is acyclic. We consider acyclie k-eolourings such that each colour class induces a graph with a given （hereditary） property. In particular, we consider aeyclic k-eolourings in which each colour class induces a graph with maximum degree at most t, which are referred to as acyclic t-improper k-colourings. The acyelic t-improper chromatic number of a graph G is the smallest k for which there exists an acyclic t-improper k-colouring of G. We focus on acyclic colourings of graphs with maximum degree 4. We prove that 3 is an upper bound for the acyclic 3-improper chromatic number of this class of graphs. We also provide a non-trivial family of graphs with maximum degree 4 whose acyclic 3-improper chromatic number is at most 2, namely, the graphs with maximum average degree at most 3. Finally, we prove that any graph G with A（G） ≤ 4 can be acyelically coloured with 4 colours in such a way that each colour class induces an acyclic graph with maximum degree at most 3.

ON APPROXIMATION OF MAX n/2-UNCUT PROBLEM

Using outward rotations, we obtain an approximation algorithm for MAXn/2-UNCUT problem, i.e., partitioning the vertices of a weighted graph into two blocks of equalcardinality such that the total weight of edges that do not cross the cut is maximized. In manyinteresting cases, the algorithm performs better than the algorithms of Ye and of Halperin andZwick. The main tool used to obtain this result is semidefinite programming.

Acyclic colorings of graphs with bounded degree

A k coloring(not necessarily proper) of vertices of a graph is called acyclic, if for every pair of distinct colors i and j the subgraph induced by the edges whose endpoints have colors i and j is acyclic. We consider some generalized acyclic k colorings, namely, we require that each color class induces an acyclic or bounded degree graph. Mainly we focus on graphs with maximum degree 5. We prove that any such graph has an acyclic 5 coloring such that each color class induces an acyclic graph with maximum degree at most 4. We prove that the problem of deciding whether a graph G has an acyclic 2 coloring in which each color class induces a graph with maximum degree at most 3 is NP complete, even for graphs with maximum degree 5. We also give a linear time algorithm for an acyclic t improper coloring of any graph with maximum degree d assuming that the number of colors is large enough.

Graphs of nonsolvable groups with four degree-vertices

Let G be a finite group. The degree(vertex) graph Γ(G) attached to G is a character degree graph.Its vertices are the degrees of the nonlinear irreducible complex characters of G, and different vertices m, n are adjacent if the greatest common divisor(m, n) > 1. In this paper, we classify all graphs with four vertices that occur as Γ(G) for nonsolvable groups G.