消去图、覆盖图和均匀图的若干结果

设 G是一个图 ,g,f是定义在图 G的顶点集上的两个整数值函数 ,且g≤f.图 G的一个 ( g,f) -因子是 G的一个支撑子图 F,使对任意的 x∈V( F)有g( x)≤ d F( x)≤ f ( x) .文中推广了 ( g,f) -消去图、( g,f ) -覆盖图和 ( g,f) -均匀图的概念 ,给出了在 g相似文献   

书本图Bm的协调和相继标号

本文给出了书本图Ｂ２ｍ的ｍ种不同的相继标号和Ｂ４ｍ＋１的ｍ种不同的相继标号。因而，书本图Ｂｍ是相继图的充分条件为：ｍ＞１且ｍ≠（３ｍｏｄ４）。这一条件也是书本图Ｂｍ是协调图的充要条件。     

One-step模糊图及相关的分解定理

主要研究一种特殊的模糊图(即one-step模糊图)的性质。提出了one-step模糊图、Hamiltonian模糊图、r-正则模糊图、二部模糊图、连通模糊图等概念,给出了强one-step Hamiltonian模糊图、强one-step r-正则模糊图、强one-step二部模糊图、强one-step连通模糊图的构造、强one-step模糊图在笛卡尔积、合成、补运算下的的简易表达式、one-step模糊图的分解定理以及强one-step模糊图在笛卡尔积运算下保持不变的一些性质,证明了任意模糊图可以分解为one-step模糊图。     

关于n-可扩图的一些结果

本文讨论了关于m-可扩图的两个极值问题；并考查了下述图类的n-可扩性；正则偶图，单位区间图和分裂图。     

紧图的两个结果及其应用

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

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

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

（a,b,k）—临界图

设Ｇ是一个图且设ａ，ｂ是非负整数，ａ〈ｂ。如果消去Ｇ的任意ｋ个顶点剩下的图有〔ａ，ｂ〕因子，则称图Ｇ是（ａ，ｂ，ｋ）－临界图。本文给出了一个图是（ａ，ｂ，ｋ）－临界图的一个充分必要条件。讨论了该条件的一些应用，研究了（ａ，ｂ，ｋ）－临界图的性质。     

平面对偶图哈密顿性的一个充分条件

提出了平面单图的对偶图是哈密顿图的一个充分条件     

正则图的变换图的谱

设G是一个图,类似全图的定义,可以定义G的8种变换图.如果G是正则图,那么图G的变换图的谱都可以由图G的谱计算得到.     

探针区间图和STS-探针区间图的刻划

该文首先引入了探针区间序来刻划探针区间图;接着给出STS-探针区间图的探针区间完备的一种构造方法,并借此得到二部图G是相对于给定顶点划分的STS-探针区间图的一个充要条件;同时也说明了STS-探针区间图其实就是其他文献中被独立研究的凸二部图.最后基于前面给出的STS-探针区间图的刻划结果提供了两种简单的O(V E)时间的STS-探针区间图的判别算法.     

Hexavalent symmetric graphs of order 9p

A graph is symmetric if its automorphism group acts transitively on the set of arcs of the graph. In this paper, we classify hexavalent symmetric graphs of order $9p$ for each prime $p$.     

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

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

Classification of a family of symmetric graphs with complete 2-arc-transitive quotients

In this paper we give a classification of a family of symmetric graphs with complete 2-arc-transitive quotients. Of particular interest are two subfamilies of graphs which admit an arc-transitive action of a projective linear group. The graphs in these subfamilies can be defined in terms of the cross ratio of certain 4-tuples of elements of a finite projective line, and thus may be called the second type ‘cross ratio graphs’, which are different from the ‘cross ratio graphs’ studied in [A. Gardiner, C. E. Praeger, S. Zhou, Cross-ratio graphs, J. London Math. Soc. (2) 64 (2001), 257–272]. We also give a combinatorial characterisation of such second type cross ratio graphs.     

Semisymmetric cubic graphs as regular covers of K 3,3

A regular graph X is called semisymmetric if it is edge-transitive but not vertex-transitive. For G ≤ AutX, we call a G-cover X semisymmetric if X is semisymmetric, and call a G-cover X one-regular if Aut X acts regularly on its arc-set. In this paper, we give the sufficient and necessary conditions for the existence of one-regular or semisymmetric Zn-Covers of K3,3. Also, an infinite family of semisymmetric Zn×Zn-covers of K3,3 are constructed.     

关于一类边裂图的k-边幻性

通常没有有效的方法判别一般图G的k-边幻性.本文采用分析方法,讨论了一类非均匀边裂图SPE(Cn,h)的边幻性和k-边幻性,得到一些新的结果.     

任意n个完备二分图的并图的k－优美性和算术性

证明了对于正整数k,n,si,ti（si,ti≥2,i=1,2,…,n）,图n/U/i=1,Ksi,ti是k-优美图;对于正整数k,d（d≥2）,k≠0（roodd）及n,si,ti（si,ti≥2,i=1,2,…,n）,图n/U/i=1,Ksi,ti是（k,d）-算术图,前一结论推广了文[6]的相应结果。     

Entire choosability of near-outerplane graphs

It is proved that if G is a plane embedding of a K₄-minor-free graph with maximum degree Δ, then G is entirely 7-choosable if Δ≤4 and G is entirely (Δ+2)-choosable if Δ≥5; that is, if every vertex, edge and face of G is given a list of max{7,Δ+2} colours, then every element can be given a colour from its list such that no two adjacent or incident elements are given the same colour. It is proved also that this result holds if G is a plane embedding of a K_2,3-minor-free graph or a -minor-free graph. As a special case this proves that the Entire Coluring Conjecture, that a plane graph is entirely (Δ+4)-colourable, holds if G is a plane embedding of a K₄-minor-free graph, a K_2,3-minor-free graph or a -minor-free graph.     

A Local Analysis of Imprimitive Symmetric Graphs

Let Г be a G-symmetric graph admitting a nontrivial G-invariant partition . Let Г be the quotient graph of Г with respect to . For each block B ∊ , the setwise stabiliser G_B of B in G induces natural actions on B and on the neighbourhood Г (B) of B in Г . Let G_(B) and G_[B] be respectively the kernels of these actions. In this paper we study certain “local actions" induced by G_(B) and G_[B], such as the action of G_[B] on B and the action of G_(B) on Г (B), and their influence on the structure of Г. Supported by a Discovery Project Grant (DP0558677) from the Australian Research Council and a Melbourne Early Career Researcher Grant from The University of Melbourne.     

New constructions of hypohamiltonian and hypotraceable graphs

A graph G is hypohamiltonian/hypotraceable if it is not hamiltonian/traceable, but all vertex‐deleted subgraphs of G are hamiltonian/traceable. All known hypotraceable graphs are constructed using hypohamiltonian graphs; here we present a construction that uses so‐called almost hypohamiltonian graphs (nonhamiltonian graphs, whose vertex‐deleted subgraphs are hamiltonian with exactly one exception, see [15]). This construction is an extension of a method of Thomassen [11]. As an application, we construct a planar hypotraceable graph of order 138, improving the best‐known bound of 154 [8]. We also prove a structural type theorem showing that hypotraceable graphs possessing some connectivity properties are all built using either Thomassen's or our method. We also prove that if G is a Grinbergian graph without a triangular region, then G is not maximal nonhamiltonian and using the proof method we construct a hypohamiltonian graph of order 36 with crossing number 1, improving the best‐known bound of 46 [14].