Nonvertex‐Balanced Factors in Random Graphs

We prove part of a conjecture by Johansson, Kahn, and Vu (Factors in random graphs, Random Struct. Algorithms 33 (2008), 1, 1–28.) regarding threshold functions for the existence of an H‐factor in a random graph . We prove that the conjectured threshold function is correct for any graph H which is not covered by its densest subgraphs. We also demonstrate that the main result of Johansson, Kahn, and Vu (Factors in random graphs, Random Struct. Algorithms 33 (2008), 1, 1–28) generalizes to multigraphs, digraphs, and a multipartite model.     

On independent sets in random graphs

The independence number of a sparse random graph G(n,m) of average degree d = 2m/n is well‐known to be with high probability, with in the limit of large d. Moreover, a trivial greedy algorithm w.h.p. finds an independent set of size , i.e., about half the maximum size. Yet in spite of 30 years of extensive research no efficient algorithm has emerged to produce an independent set with size for any fixed (independent of both d and n). In this paper we prove that the combinatorial structure of the independent set problem in random graphs undergoes a phase transition as the size k of the independent sets passes the point . Roughly speaking, we prove that independent sets of size form an intricately rugged landscape, in which local search algorithms seem to get stuck. We illustrate this phenomenon by providing an exponential lower bound for the Metropolis process, a Markov chain for sampling independent sets. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 436–486, 2015     

关于图的同构判定方法的探讨

对于两图的同构的判定方法进行较深入的探讨,给出判定两图同构和判定两图不同构的几种方法,并对其判定方法的优劣进行比较.     

关于两个图的一类新连接图的谱

给定2个图G1和G2,设G1的边集E(G1)={e1,e2,?,em1},则图G1⊙G2可由一个G1,m1个G2通过在G1对应的每条边外加一个孤立点,新增加的点记为U={u1,u2,?,um1},将ui分别与第i个G2的所有点以及G1中的边ei的端点相连得到,其中i=?1,2,?,m1。得到：（i）当G1是正则图,G2是正则图或完全二部图时,确定了G1⊙G2的邻接谱（A-谱）。（ii）当G1是正则图,G2是任意图时,给出了G1⊙G2的拉普拉斯谱（L-谱）。（iii）当G1和G2都是正则图时,给出了G1⊙G2的无符号拉普拉斯谱（Q-谱）。作为以上结论的应用,构建了无限多对A-同谱图、L-同谱图和Q-同谱图;同时当G1是正则图时,确定了G1⊙G2支撑树的数量和Kirchhoff指数。     

Fundamental Groups of Graphs of Cyclic Subgroup Separable and Weakly Potent Groups

We give a characterization of the cyclic subgroup separability and weak potency of the fundamental group of a graph of polycyclic-by-finite groups and free-by-finite groups amalgamating edge subgroups of the form × D,where h has infinite order and D is finite.     

An Improved Plotting Package Applied to Chemical Graphing Problems

Abstract

A plotting package, written in LINC assembly language, is described. It produces high quality graphs and labels the graphs for direct submission to professional journals. A μ-LINC (Laboratory INstrument (Computer) is used to compute least-squares fitted curves and lines from data entered either on-or off-line and to draw the graphs directly on an incremental plotter. Bar graphs, line graphs, and fitted data can be plotted with options to suppress the lines and/or the points.     

Perpetual cutoff method and CDE′(K,N) condition on graphs

By using the perpetual cutoff method, we prove two discrete versions of gradient estimates for bounded Laplacian on locally finite graphs with exception sets under the condition of CD{E}^{\prime }(K,N). This generalizes a main result of F. Münch who considers the case of CD(K, \infty) curvature. Hence, we answer a question raised by Münch. For that purpose, we characterize some basic properties of radical form of the perpetual cutoff semigroup and give a weak commutation relation between bounded Laplacian \text{Δ} and perpetual cutoff semigroup P_t^W in our setting.     

A survey on book-embedding of planar graphs

The book-embedding problem arises in several area, such as very large scale integration (VLSI) design and routing multilayer printed circuit boards (PCBs). It can be used into various practical application fields. A book embedding of a graph G is an embedding of its vertices along the spine of a book, and an embedding of its edges to the pages such that edges embedded on the same page do not intersect. The minimum number of pages in which a graph G can be embedded is called the pagenumber or book-thickness of the graph G. It is an important measure of the quality for book-embedding. It is NP-hard to research the pagenumber of book-embedding for a graph G. This paper summarizes the studies on the book-embedding of planar graphs in recent years.     

Convergent sequences of sparse graphs: A large deviations approach

Models based on sparse graphs are of interest to many communities: they appear as basic models in combinatorics, probability theory, optimization, statistical physics, information theory, and more applied fields of social sciences and economics. Different notions of similarity (and hence convergence) of sparse graphs are of interest in different communities. In probability theory and combinatorics, the notion of Benjamini‐Schramm convergence, also known as left‐convergence, is used quite frequently. Statistical physicists are interested in the the existence of the thermodynamic limit of free energies, which leads naturally to the notion of right‐convergence. Combinatorial optimization problems naturally lead to so‐called partition convergence, which relates to the convergence of optimal values of a variety of constraint satisfaction problems. The relationship between these different notions of similarity and convergence is, however, poorly understood. In this paper we introduce a new notion of convergence of sparse graphs, which we call Large Deviations or LD‐convergence, and which is based on the theory of large deviations. The notion is introduced by “decorating” the nodes of the graph with random uniform i.i.d. weights and constructing corresponding random measures on and . A graph sequence is defined to be converging if the corresponding sequence of random measures satisfies the Large Deviations Principle with respect to the topology of weak convergence on bounded measures on . The corresponding large deviations rate function can be interpreted as the limit object of the sparse graph sequence. In particular, we can express the limiting free energies in terms of this limit object. We then establish that LD‐convergence implies the other three notions of convergence discussed above, and at the same time establish several previously unknown relationships between the other notions of convergence. In particular, we show that partition‐convergence does not imply left‐ or right‐convergence, and that right‐convergence does not imply partition‐convergence. © 2016 Wiley Periodicals, Inc. Random Struct. Alg., 51, 52–89, 2017