一类泛圈图

本文证明了如果G是2连通无爪图,G不是圈,n=|v(G)|>q,G的每个导出子图A都满足φ(a_1,a_2),且G中不存在W′作为其导出子图,则G是泛圈图。     

中国邮路问题的0-1规划解法

在用“奇偶点图上作业法”求解“中国邮路问题”时,需检查图中的每一个回路.当图中回路较多时,检查不便且易出错.针对此,本文建立了求解“中国邮路问题”的0-1规划模型,并给出了算例。     

On potentially <Emphasis Type="Italic">H</Emphasis>-graphic sequences

For given a graph H, a graphic sequence π = (d ₁, d ₂,..., d _n) is said to be potentially H-graphic if there is a realization of π containing H as a subgraph. In this paper, we characterize the potentially (K ₅ − e)-positive graphic sequences and give two simple necessary and sufficient conditions for a positive graphic sequence π to be potentially K ₅-graphic, where K _r is a complete graph on r vertices and K _r-e is a graph obtained from K _r by deleting one edge. Moreover, we also give a simple necessary and sufficient condition for a positive graphic sequence π to be potentially K ₆-graphic. Project supported by National Natural Science Foundation of China (No. 10401010).     

Drawing c-planar biconnected clustered graphs

In a graph, a cluster is a set of vertices, and two clusters are said to be non-intersecting if they are disjoint or one of them is contained in the other. A clustered graph C consists of a graph G and a set of non-intersecting clusters. In this paper, we assume that C has a compound planar drawing and each cluster induces a biconnected subgraph. Then we show that such a clustered graph admits a drawing in the plane such that (i) edges are drawn as straight-line segments with no edge crossing and (ii) the boundary of the biconnected subgraph induced by each cluster is a convex polygon.     

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 κ = min{κ′(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 κ′(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.     

Sizes of Critical Graphs with Small Maximum Degrees

In this paper, we give new lower bounds for the size of Δ-critical graphs with Δ=8,9 which improve the partial results of Luo [6] and Y. Zhao [12].     

Enumeration of perfect matchings of a type of Cartesian products of graphs

Let G be a graph and let Pm(G) denote the number of perfect matchings of G.We denote the path with m vertices by P_m and the Cartesian product of graphs G and H by G×H. In this paper, as the continuance of our paper [W. Yan, F. Zhang, Enumeration of perfect matchings of graphs with reflective symmetry by Pfaffians, Adv. Appl. Math. 32 (2004) 175-188], we enumerate perfect matchings in a type of Cartesian products of graphs by the Pfaffian method, which was discovered by Kasteleyn. Here are some of our results:1. Let T be a tree and let C_n denote the cycle with n vertices. Then Pm(C₄×T)=∏(2+α²), where the product ranges over all eigenvalues α of T. Moreover, we prove that Pm(C₄×T) is always a square or double a square.2. Let T be a tree. Then Pm(P₄×T)=∏(1+3α²+α⁴), where the product ranges over all non-negative eigenvalues α of T.3. Let T be a tree with a perfect matching. Then Pm(P₃×T)=∏(2+α²), where the product ranges over all positive eigenvalues α of T. Moreover, we prove that Pm(C₄×T)=[Pm(P₃×T)]².     

Necessary conditions for multistationarity in discrete dynamical systems

R. Thomas conjectured, 20 years ago, that the presence of a positive circuit in the interaction graph of a dynamical system is a necessary condition for the presence of several stable states. Recently, E. Remy et al. stated and proved the conjecture for Boolean dynamical systems. Using a similar approach, we generalize the result to discrete dynamical systems, and by focusing on the asynchronous dynamics that R. Thomas used in the course of his analysis of genetic networks, we obtain a more general variant of R. Thomas’ conjecture. In this way, we get a necessary condition for genetic networks to lead to differentiation.