Hamilton cycles in line graphs of 3-hypergraphs

We prove that every 52-connected line graph of a rank 3 hypergraph is Hamiltonian. This is the first result of this type for hypergraphs of bounded rank other than ordinary graphs.     

一些稀疏图的强边染色（英文）

图G的强边染色是指对图G进行正常边染色使得任意长度为3的路的三条边染不同的颜色.图G的强边色数,记为χ’_s(G),是使得图G是强k边着色的最小正整数kk.2015年,Zang [arXiv:1510.00785]证明了:最大度△(G)=5的图G,χ’_s(G)≤37.本文证明了:最大度△(G)=5且最大平均度小于8/3(或者14/5)的图G,χ’_s(G)≤13 (或者14).另外,本文证明了:最大度△(G)≥3的不含K_2,3-图子式的图G,χ’_s(G)≤4△(G)-6,这个界是紧的.     

Weak Graph Map Homotopy and Its Applications∗

The authors introduce a notion of a weak graph map homotopy (they call it M-homotopy), discuss its properties and applications. They prove that the weak graph map homotopy equivalence between graphs coincides with the graph homotopy equivalence defined by Yau et al in 2001. The difference between them is that the weak graph map homotopy transformation is defined in terms of maps, while the graph homotopy transformation is defined by means of combinatorial operations. They discuss its advantages over the graph homotopy transformation. As its applications, they investigate the mapping class group of a graph and the 1-order MP-homotopy group of a pointed simple graph. Moreover, they show that the 1-order MP-homotopy group of a pointed simple graph is invariant up to the weak graph map homotopy equivalence.     

平面图的强边染色

图$G$的强边染色是在正常边染色的基础上, 要求距离不超过$2$的任意两条边染不同的颜色, 强边染色所用颜色的最小整数称为图$G$的强边色数。本文首先给出极小反例的构型, 然后通过权转移法, 证明了$g(G)\geq5$, $\Delta(G)\geq6$且$5$-圈不相交的平面图的强边色数至多是$4\Delta(G)-1$。     

k圈图的最大Laplace分离度

设$ G $是一个$ n $阶$ k $圈图, $ k $圈图为边数等于顶点数加$ k-1 $的简单连通图。$ \mu_{1}(G) $、$ \mu_{2}(G) $分别记为图$ G $的Laplace矩阵的最大特征值和次大特征值, 图$ G $的Laplace分离度定义为$ S_{L}(G)=\mu_{1}(G)-\mu_{2}(G) $。本文研究了给定阶数的$ k $圈图的最大Laplace分离度, 并刻画了相应的极图, 其结果推广了已有当$ k=1, 2, 3 $时的结论。     

The combinatorial game Nofil played on Steiner triple systems

We introduce an impartial combinatorial game on Steiner triple systems called Next One to Fill Is the Loser (Nofil ). Players move alternately, choosing points of the triple system. If a player is forced to fill a block on their turn, they lose. By computing nim-values, we determine optimal strategies for Nofil on all Steiner triple systems up to order 15 and a sampling for orders 19, 21 and 25. The game Nofil can be thought of in terms of play on a corresponding hypergraph which will become a graph during play. At that point Nofil is equivalent to playing the game Node Kayles on the graph. We prove necessary conditions and sufficient conditions for a graph to reached playing Nofil. We conclude that the complexity of determining the outcome of the game Nofil on Steiner triple systems is PSPACE-complete for randomized reductions.     

Pseudo-orthogonality for graph 1-Laplacian eigenvectors and applications to higher Cheeger constants and data clustering

The data clustering problem consists in dividing a data set into prescribed groups of homogeneous data. This is an NP-hard problem that can be relaxed in the spectral graph theory, where the optimal cuts of a graph are related to the eigenvalues of graph 1-Laplacian. In this paper, we first give new notations to describe the paths, among critical eigenvectors of the graph 1-Laplacian, realizing sets with prescribed genus. We introduce the pseudo-orthogonality to characterize m₃(G), a special eigenvalue for the graph 1-Laplacian. Furthermore, we use it to give an upper bound for the third graph Cheeger constant h₃(G), that is, h₃(G) 6 m₃(G). This is a first step for proving that the k-th Cheeger constant is the minimum of the 1-Laplacian Raylegh quotient among vectors that are pseudo-orthogonal to the vectors realizing the previous k - 1 Cheeger constants. Eventually, we apply these results to give a method and a numerical algorithm to compute m₃(G), based on a generalized inverse power method.     

On bandwidth sums of graphs

ＯＮＢＡＮＤＷＩＤＴＨＳＵＭＳＯＦＧＲＡＰＨＳＹＡＯＢＩＮＧ（姚兵）;ＷＡＮＧＪＩＡＮＦＡＮＧ（王建方）（ＤｅｐａｒｔｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃｓ,ＮｏｒｉｈｗｅｓｔｅｔｅｒｎＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ,Ｌａｎｚｈｏｕ７３００７０,Ｃｈｉ...     

Two-Arc Transitive Graphs and Twisted Wreath Products

The paper addresses a part of the problem of classifying all 2-arc transitive graphs: namely, that of finding all groups acting 2-arc transitively on finite connected graphs such that there exists a minimal normal subgroup that is nonabelian and regular on vertices. A construction is given for such groups, together with the associated graphs, in terms of the following ingredients: a nonabelian simple group T, a permutation group P acting 2-transitively on a set , and a map F : Tsuch that x = x ^–1 for all x F() and such that Tis generated by F(). Conversely we show that all such groups and graphs arise in this way. Necessary and sufficient conditions are found for the construction to yield groups that are permutation equivalent in their action on the vertices of the associated graphs (which are consequently isomorphic). The different types of groups arising are discussed and various examples given.     

Estimations of subgraph positions in molecular graphs and their common subgraph peculiarities

Some questions emerged from electronic data processing of molecular structures (graphs) and its fragments have been considered in this work. Quantitative estimations of subgraph positions in molecular graphs are presented and some properties of their maximal common subgraphs are described.