完全图的谱

本文通过组合数学和矩阵论的方法获得了完全图的特征多项式和谱,指出完全图的特征多项式的系数与图的结构之间的关系,并证明了邻接谱、拉谱拉斯谱和无符号拉谱拉斯谱三者之间的关系.     

Every planar graph without 4-cycles adjacent to two triangles is DP-4-colorable

Wang and Lih (2002) conjectured that every planar graph without adjacent triangles is 4-choosable. In this paper, we prove that every planar graph without any 4-cycle adjacent to two triangles is DP-4-colorable, which improves the results of Lam et al. (1999), Cheng et al. (2016) and Kim and Yu [ arXiv:1709.09809v1].     

Strong edge-coloring for planar graphs with large girth

A strong edge-coloring of a graph $G=(V,E)$ is a partition of its edge set $E$ into induced matchings. Let $G$ be a connected planar graph with girth $k\ge 26$ and maximum degree $\Delta$. We show that either $G$ is isomorphic to a subgraph of a very special $\Delta$-regular graph with girth $k$, or $G$ has a strong edge-coloring using at most $2\Delta +\lceil \frac{12(\Delta -2)}{k}\rceil$ colors.     

蕴含W5可图序列的最小度和

Gould,Jacobson和Lehel考虑了下述经典Tur偄n型极值问题的变形:对于给定的图H,确定最小的正偶数σ(H,n),使得对于每一个n项可图序列π=(d1,d2,…,dn),当σ(π)=d1+d2+…+dn≥σ(H,n)时,π有一个实现G包含H作为可图的.本文确定了当n≥11时,σ(W5,n)之值,其中Wr是r个顶点的轮图.     

关于图的第二特征标R2(G)

对任意图G，h(G，x)表示图G的伴随多项式，R2(G)表示图G的第二特征标，本文刻画了R2(G)=-2，-1，0，1，2的全部连通图。     

Hamilton线图中的泛圈性

对于图Ｇ的边ｅ＝ｕｖ，定义ｄ（ｅ）－ｄ（ｕ）＋ｄ（ｖ），这里ｄ（ｕ）和ｄ（ｖ）分分别表示ｕ和ｖ的度，该文的主要结果是：对阶为ｎ（ｎ≥４０）的简单连通图Ｇ，如果对Ｇ中任意两条边距离为２的边ｅ１，ｅ２都有ｄ（ｅ１）＋ｄ（ｅ２）≥ｎ，并且线图Ｌ（Ｇ）是Ｈａｍｉｌｔｏｎ的，则Ｌ（Ｇ）是泛圈的，并且条件Ｌ（Ｇ）是Ｈａｍｉｌｔｏｎ是必要的。     

图族S_(r(k+m)+1)~ψ∪(rk-1)K_1的补图的色等价性定理

设ψ( k,m)表示把星图 Sk+ 1的 k度点与路 Pm的一个 1度点重迭后得到的图 ,Sψ*r(k+ m) + 1表示把星图 Srk+ 1的 rk个 1度点分别与 rψ( k,m)的每个分支的 k个 1度点 (均邻接于ψ( k,m)的 k +1度点 )依次重迭后得到的图。证明了图族 Sψ*r(k+ m) + 1∪ ( rk -1 ) K1的补图的色等价性及非色唯一性 ,进而推广了这一结果     

Cycle and circle tests of balance in gain graphs: Forbidden minors and their groups

We examine two criteria for balance of a gain graph, one based on binary cycles and one on circles. The graphs for which each criterion is valid depend on the set of allowed gain groups. The binary cycle test is invalid, except for forests, if any possible gain group has an element of odd order. Assuming all groups are allowed, or all abelian groups, or merely the cyclic group of order 3, we characterize, both constructively and by forbidden minors, the graphs for which the circle test is valid. It turns out that these three classes of groups have the same set of forbidden minors. The exact reason for the importance of the ternary cyclic group is not clear. © 2005 Wiley Periodicals, Inc. J Graph Theory