Fold‐2‐covering triangular embeddings

For a graph G and a positive integer m, G_(m) is the graph obtained from G by replacing every vertex by an independent set of size m and every edge by m² edges joining all possible new pairs of ends. If G triangulates a surface, then it is easy to see from Euler's formula that G_(m) can, in principle, triangulate a surface. For m prime and at least 7, it has previously been shown that in fact G_(m) does triangulate a surface, and in fact does so as a “covering with folds” of the original triangulation. For m = 5, this would be a consequence of Tutte's 5‐Flow Conjecture. In this work, we investigate the case m = 2 and describe simple classes of triangulations G for which G₍₂₎ does have a triangulation that covers G “with folds,” as well as providing a simple infinite class of triangulations G of the sphere for which G₍₂₎ does not triangulate any surface. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 79–92, 2003     

Bounds for the Least Laplacian Eigenvalue of a Signed Graph

A signed graph is a graph with a sign attached to each edge. This paper extends some fundamental concepts of the Laplacian matrices from graphs to signed graphs. In particular, the relationships between the least Laplacian eigenvalue and the unbalancedness of a signed graph are investigated.     

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.     

全固态多波长飞秒脉冲激光系统

利用棱镜对引进频谱空间啁啾来补偿飞秒脉冲激光二次谐波产生中的相位失配,提高了倍频效率建立了一套全固态、多波长(1065nm, 532nm,823.1nm, 402nm)飞秒脉冲激光系统自制的Nd:YVO4激光器输出532nm绿光激光,最高平均功率可达5.6W当用2.5W绿光激光泵浦时,从自制的钛宝石激光器及经BBO倍频可分别输出中心波长为823.1nm和402nm,平均功率300mW和73mW,谱宽32.3nm和5.1nm,脉宽22fs和33.3fs、重复率108MHz的近红外和蓝光激光整个系统具有结构紧凑、倍频效率高、运行稳定的特点.     

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.