拟顶点可迁图上简单随机游走的切割点

证明了体积增长不低于5次多项式的拟顶点可迁图上的简单随机游走几乎处处有无穷多个切割时,从而有无穷多个切割点.该结论在所论情形下肯定了Benjamini,Gurel-Gurevich和Schramm在文[2011,Cutpoints and resistance of random walk paths,Ann.Probab.,39(3):1122-1136]中提出的猜想:顶点可迁图上暂留简单随机游走几乎处处有无穷多个切割点.     

紧图的两个结果及其应用

双随机矩阵有许多重要的应用,紧图族可以看作是组合矩阵论中关于双随机矩阵的著名的Birkhoff定理的拓广,具有重要的研究价值.确定一个图是否紧图是个困难的问题,目前已知的紧图族尚且不多.给出了两个重要结果:任意紧图与任意多个孤立点的不交并是紧图;任意紧图的每一个顶点上各增加一条悬挂边的图是紧图.利用这两个结果,从已知紧图可构造出无穷多个紧图族.     

6—桥图的色唯一性

由连接两个顶点的S条内部不交的路组成的图叫S-桥图。本文讨论了6-桥图F（a,b,c,d,e,f)(a≤6≤c≤d≤e≤f)的色性，给出了此类图色唯一的一个充分条件；并证明6-桥图F(2,2,2,a,b)（a≥b≥3)是色唯一的。     

若干Mycielski图的均匀染色

如果图G的一个正常顶点染色满足任两个色类中的顶点数相差不超过1,则称为G的均匀染色.研究了一些Mycielski图的均匀染色,给出了路、圈、完全图和广义星图的Mycielski图的均匀色数.     

关于图的子着色

本文主要讨论了子色唯一图的结构，并给出了唯一k-子色图、最大子色图的边临界子色图的特征．     

G_(v_i)~*型图的伴随多项式的因式分解及其色性分析

通过研究图的伴随多项式的因式分解 ,给出了证明非色唯一图的一种新的途径 ,并且得到了色等价图簇的结构特征 .     

S~s一类图簇的伴随多项式的因式分解及色性分析

通过研究图的伴随多项式的因式分解 ,给出了证明非色唯一图的一种新方法 ,并且得到了色等价图的一些结构特性 .     

若干图簇的伴随多项式的因式分解及色性分析

我们通过研究图的伴随多项式的因式分解,给出了证明非色唯一图的一种新方法,同时得到若干图簇的色等价图的结构定理.     

几类图簇的伴随多项式的因式分解及色性分析

我们通过研究图的伴随多项式的因式分解，给出了证明非色唯一图的一种新方法，并得到了几类图簇的色等价图的结构特征．     

关于完全三部图K(n,n,n+4)的色唯一性

通过比较两个图的色多项式的系数(本文使用了五独立集数)、顶点集、边集、三角形和四圈的个数,证明了K(2,2,6)是色唯一图,从而部分地回答了文[5],[7]中遗留的一个问题,并得到图K(n,n,n 4)(n=2或n 4)是色唯一的.     

Independent packings in structured graphs

Packing a maximum number of disjoint triangles into a given graph G is NP-hard, even for most classes of structured graphs. In contrast, we show that packing a maximum number of independent (that is, disjoint and nonadjacent) triangles is polynomial-time solvable for many classes of structured graphs, including weakly chordal graphs, asteroidal triple-free graphs, polygon-circle graphs, and interval-filament graphs. These classes contain other well-known classes such as chordal graphs, cocomparability graphs, circle graphs, circular-arc graphs, and outerplanar graphs. Our results apply more generally to independent packings by members of any family of connected graphs. Research of both authors is supported by the Natural Sciences and Engineering Research Council of Canada.     

Mock threshold graphs

Mock threshold graphs are a simple generalization of threshold graphs that, like threshold graphs, are perfect graphs. Our main theorem is a characterization of mock threshold graphs by forbidden induced subgraphs. Other theorems characterize mock threshold graphs that are claw-free and that are line graphs. We also discuss relations with chordality and well-quasi-ordering as well as algorithmic aspects.     

三度边正则图的三个无限族

图X称为边正则图，若X的自同构群Aut(X)在X的边集上的作用是正则的．本文考察了三度边正则图与四度Cayley图的关系，给出了一个由四度Cayley图构造三度边正则图的方法，并且构造了边正则图的三个无限族．     

Equistable graphs, general partition graphs, triangle graphs, and graph products

In this paper we examine the connections between equistable graphs, general partition graphs and triangle graphs. While every general partition graph is equistable and every equistable graph is a triangle graph, not every triangle graph is equistable, and a conjecture due to Jim Orlin states that every equistable graph is a general partition graph. The conjecture holds within the class of chordal graphs; if true in general, it would provide a combinatorial characterization of equistable graphs.Exploiting the combinatorial features of triangle graphs and general partition graphs, we verify Orlin’s conjecture for several graph classes, including AT-free graphs and various product graphs. More specifically, we obtain a complete characterization of the equistable graphs that are non-prime with respect to the Cartesian or the tensor product, and provide some necessary and sufficient conditions for the equistability of strong, lexicographic and deleted lexicographic products. We also show that the general partition graphs are not closed under the strong product, answering a question by McAvaney et al.     

Cover-incomparability graphs and chordal graphs

The problem of recognizing cover-incomparability graphs (i.e. the graphs obtained from posets as the edge-union of their covering and incomparability graph) was shown to be NP-complete in general [J. Maxová, P. Pavlíkova, A. Turzík, On the complexity of cover-incomparability graphs of posets, Order 26 (2009) 229-236], while it is for instance clearly polynomial within trees. In this paper we concentrate on (classes of) chordal graphs, and show that any cover-incomparability graph that is a chordal graph is an interval graph. We characterize the posets whose cover-incomparability graph is a block graph, and a split graph, respectively, and also characterize the cover-incomparability graphs among block and split graphs, respectively. The latter characterizations yield linear time algorithms for the recognition of block and split graphs, respectively, that are cover-incomparability graphs.     

Tetravalent one-regular graphs of order 2<Emphasis Type="Italic">pq</Emphasis>

A graph is one-regular if its automorphism group acts regularly on the set of its arcs. In this article a complete classification of tetravalent one-regular graphs of order twice a product of two primes is given. It follows from this classification that with the exception of four graphs of orders 12 and 30, all such graphs are Cayley graphs on Abelian, dihedral, or generalized dihedral groups.     

A note on vertex-transitive non-Cayley graphs from Cayley graphs generated by involutions

We show that the result of Watkins (1990) [19] on constructing vertex-transitive non-Cayley graphs from line graphs yields a simple method that produces infinite families of vertex-transitive non-Cayley graphs from Cayley graphs generated by involutions. We also prove that the graphs arising this way are hamiltonian provided that their valency is at least six.     

Bubble-sort图和Modified Bubble-sort图的自同构群

Bubble-Sort图和Modified Bubble-Sort图是两类特殊的Cayley图,由于其在网络构建中的应用而受到广泛关注.本文完全确定了这两类图的自同构群.     

A Characterization of Mixed Unit Interval Graphs

We give a complete characterization of mixed unit interval graphs, the intersection graphs of closed, open, and half‐open unit intervals of the real line. This is a proper superclass of the well‐known unit interval graphs. Our result solves a problem posed by Dourado, Le, Protti, Rautenbach, and Szwarcfiter (Mixed unit interval graphs, Discrete Math 312, 3357–3363 (2012)).     

Powers of cycles, powers of paths, and distance graphs

In 1988, Golumbic and Hammer characterized the powers of cycles, relating them to circular arc graphs. We extend their results and propose several further structural characterizations for both powers of cycles and powers of paths. The characterizations lead to linear-time recognition algorithms of these classes of graphs. Furthermore, as a generalization of powers of cycles, powers of paths, and even of the well-known circulant graphs, we consider distance graphs. While the colorings of these graphs have been intensively studied, the recognition problem has been so far neglected. We propose polynomial-time recognition algorithms for these graphs under additional restrictions.