Non-bipartite Graphs with Third Largest Laplacian Eigenvalue Less Than Three

All bipartite graphs whose third largest Laplacian eigenvalue is less than 3 have been characterized by Zhang. In this paper, all connected non-bipartite graphs with third largest Laplacian eigenvalue less than three are determined.     

关于局部子图可重构性的一个新结果

本文研究局部子图的可重构性。一个图Ｇ在一顶点ｖ处的ｋ－局部子图是到ｖ距离小于等于ｋ的顶点导出且以ｖ为根的子图，记为ＬＧ＾ｋ（ｖ）。本文通过引进核子图的结构证明了ｋ－局部子图是可重构的，如果每一个ｋ－局部子图所含的顶点数都小于等于│Ｖ（Ｇ）│－１。这个结果改进了原有的结果。由这个新结果可知，图的半径这个参数是可重构的。本文还提出了点距序列的概念，并进一步讨论了点距序列与局部子图的关系和一些未解决的问     

几类可升分解的图

Ａｌａｖｉ等人在文献［１］中定义了图的一种新分解，即“升分解”，并且猜想：任意有正数条边的图都可升分解。本文证明了下面三类图可升分解，并得到了一些有意义的推论。１设Ｒｎ是一个至多含有ｎ个顶点和至多含有ｎ条边的图，Ｋｎ－Ｒｎ可升分解（ｎ≥５）；２对称图可升分解；３对称图Ｇ的混合积（Ｇ；ｋ）可升分解。     

Then-component cubic model and flows: Subgraph break-collapse method

We specialize to then-component cubic model the subgraph break-collapse method which we recently developed for theZ() model. The cubic model has less symmetry than the Potts model, for which the method was originally developed, but nevertheless it is still possible to reduce considerably the computational complexity of the generalZ() model. Our recursive algorithm is similar, forn=2, to the break-collapse method for theZ(4) model proposed by Mariz and co-workers. It allows the exact calculation for the partition function and correlation functions forn-component cubic clusters, withn as a variable, without the need to examine all of the spin configurations. An important application is therefore in real-space renormalization-group calculations.     

Upperbound procedures for the identification of similar three-dimensional chemical structures

Summary This paper describes techniques for calculating the degree of similarity between an input query molecule and each of the molecules in a database of 3-D chemical structures. The inter-molecular similarity measure used is the number of atoms in the 3-D common substructure (CS) between the two molecules which are being compared. The identification of 3-D CSs is very demanding of computational resources, even when an efficient clique detection algorithm is used for this purpose. Two types of upperbound calculation are described which allow reductions in the number of exact CS searches which need to be carried out to identify those molecules from a database which are similar to a 3-D target molecule.     

HC-HDSD: A method of hypergraph construction and high-density subgraph detection for inferring high-order epistatic interactions

Detecting epistatic interactions, or nonlinear interactive effects of Single Nucleotide Polymorphisms (SNPs), has gained increasing attention in explaining the “missing heritability” of complex diseases. Though much work has been done in mapping SNPs underlying diseases, most of them constrain to 2-order epistatic interactions. In this paper, a method of hypergraph construction and high-density subgraph detection, named HC-HDSD, is proposed for detecting high-order epistatic interactions. The hypergraph is constructed by low-order epistatic interactions that identified using the normalized co-information measure and the exhaustive search. The hypergraph consists of two types of vertices: real ones representing main effects of SNPs and virtual ones denoting interactive effects of epistatic interactions. Then, both maximal clique centrality algorithm and near-clique mining algorithm are employed to detect high-density subgraphs from the constructed hypergraph. These high-density subgraphs are inferred as high-order epistatic interactions in the HC-HDSD. Experiments are performed on several simulation data sets, results of which show that HC-HDSD is promising in inferring high-order epistatic interactions while substantially reducing the computation cost. In addition, the application of HC-HDSD on a real Age-related Macular Degeneration (AMD) data set provides several new clues for the exploration of causative factors of AMD.     

Limit theorems for monochromatic stars

Let T(K_1,r,G_n) be the number of monochromatic copies of the r‐star K_1,r in a uniformly random coloring of the vertices of the graph G_n. In this paper we provide a complete characterization of the limiting distribution of T(K_1,r,G_n), in the regime where is bounded, for any growing sequence of graphs G_n. The asymptotic distribution is a sum of mutually independent components, each term of which is a polynomial of a single Poisson random variable of degree at most r. Conversely, any limiting distribution of T(K_1,r,G_n) has a representation of this form. Examples and connections to the birthday problem are discussed.