Hamiltonian图的泛圈性的一个充分条件

设Ｇ是一个ｎ阶图,若对于每一个ｋ（３≤ｋ≤ｎ）,Ｇ都含有长度为ｋ的圈,则称Ｇ为泛圈图． 在［１］中, Ｒ．Ｊ, Ｆａｕｄｒｅｅ等证明了如下结果： 定理Ａ设Ｇ是一个ｎ－阶２－连通图,δ（Ｇ）≥ｔ．若对于Ｇ中任意两个不相邻的点ｕ和ｖ,均有 ｜Ｎ（ｕ） ∪ Ｎ（ｖ）｜≥ｎ－ｔ,则 Ｇ是 Ｈａｍｉｌｔｏｎｉａｎ图． 根据 Ｂｏｎｄｙ在［４］中的想法：几乎任何一个 Ｈａｍｉｌｔｏｎｉａｎ图的非平凡的充分条件都可能蕴含着图的泛圈性质,自然有如下猜测：设图Ｇ满足定理Ａ的条件,则Ｇ是泛圈圈或者 ｎ＝２ｔ; Ｇ≌Ｋ_（ｔ,ｔ）…     

关于可重构的局部子图

一个图Ｇ在一顶点ｘ处的局部子图Ｌ｛ｘ｝是由Ｇ的给定性质定义的包含ｘ的子图Ｌ１，并以ｘ为根，例如在点ｘ处的ｋ－局部子图是以ｘ为根，以所有到ｘ距离不超过ｋ的顶点集合｛ｕ∈Ｖ（Ｇ）：ｄＧ（ｖ，ｘ）≤ｋ｝为顶点集；以｛ｕｖ∈Ｅ（Ｇ）：ｄＧ（ｕ，ｘ）〈ｋ，或ｄＧ（ｖ，ｘ）〈ｋ｝为边集的带根子图。本文证明了：对于Ｇ的局部子图Ｌ｛ｘ｝，如果每个Ｌ｛ｘ｝，ｘ∈Ｖ（Ｇ），的顶点数（或边数）都小于Ｇ的顶点数（边数）减     

具有固定价的结合概型：（I）

结合概型的分类，是件十分重要而又非常困难的工作。在结合概型中，价是很重要的参数，有较强的组合意义。利用价来给出某些结合概型的分类，是一个常用的方法。Ａ０，Ａ１，Ａｄ和Ｋ０，Ｋ１，Ｋｄ分别是的邻接矩阵和价，且ｋ１＝ｋ２＝ｋｄ〉２，本文证明了若某个Гｉ＝（Ｘ，Ｒｉ）是无向连通图且Ｖ（Ａ＾２１）≤２ｖ（Ａｉ），１≤ｉ≤ｄ，则ｄ＝１，即是平凡的结合概型。     

Camina—Gagen定理的一个推广

在这篇文章中，我们考虑２－（ｖ，ｋ，１）设计Ｄ上的自同构群，得到了如下结果：若Ｇ≤ＡｕｔＤ，且Ｇ是线一本原的，则当（ｋ，ｖ）＝ｋ／ｋ２时（ｋ２≤４），Ｇ也是点一本原的。ｋ２＝１是Ｃａｍｉｎａ－Ｇａｇ－ｅｎ的结果。     

关于余直径的一个充分条件

本文给出了一个关于长圈和长路的新的充分条件．主要结果是：设在３－连通图Ｇ中，任一对距离为２的顶点ｕ，ｖ，都满足ｍａｘ｛ｄ（ｕ），ｄ（ｖ）｝≥ｍ/２，那么ｄ^＊（Ｇ）≥ｍｉｎ｛ｎ－１，ｍ－２｝．     

一类泛圈图

本文证明了如果 Ｇ 是 ２ 连通无爪图, Ｇ 不是圈,ｎ＝ ｜ Ｖ（ Ｇ）｜≥９, Ｇ 的每个导出子图 Ａ都满足φ（ａ１,ａ２ ）,且 Ｇ 中不含同构于 Ｚ＋２ 的导出子图,则 Ｇ是泛圈图     

线图泛圈性的一个充分条件

本文证明了如果Ｇ是２连通线图,Ｇ不是圈,ｎ＝｜Ｖ（Ｇ）｜≥９且Ｇ的每个同构于Ａ的导出子图都满足（ａ１,ａ２）,则Ｇ是泛圈图     

2-连通图的Hamilton圈的一个充分条件

本文给出了２－连通图有Ｈａｍｉｌｔｏｎ圈的又一个充分条件．定理设Ｇ为有ｎ（ｎ＞３）个顶点的２－连通图，如果对Ｇ中任意两个顶点ｕ、ｖ，当ｄ（ｕ，ｖ）＝２时，都有ｍａｘ（ｄ（ｕ），ｄ（ｖ））≥ｎ／２，则Ｇ有Ｈａｍｉｌｔｏｎ圈．证用反证法．假设Ｇ没有Ｈａｍ...     

Suzuhi单群作用在2－（v．k．1）上的一个特性

在本文，我们证明了：若群Ｇ满足Ｓｚ（２２ｍ＋１）≤Ｇ≤ＡｕｔＳｚ（２２ｍ＋１）ｍ≥１，且Ｇ作用在２－（ｖ．ｋ．１）设计上是线本原的，则Ｇ也是点本原的．     

平衡二部图的四圈覆盖

对任意的正整数ｋ,如果每部２ｋ个点的平衡二部图Ｇ＝（ｖ１,ｖ２;Ｅ）的最小度大于等于４ｋ／３,那么Ｇ恰好被ｋ个相互独立的四圈覆盖。     

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图构造三度边正则图的方法，并且构造了边正则图的三个无限族．     

Edge-primitive Cayley graphs on abelian groups and dihedral groups

A graph is called edge-primitive if its automorphism group acts primitively on its edge set. In 1973, Weiss (1973) determined all edge-primitive graphs of valency three, and recently Guo et al. (2013,2015) classified edge-primitive graphs of valencies four and five. In this paper, we determine all edge-primitive Cayley graphs on abelian groups and dihedral groups.     

Hypohamiltonian Planar Cubic Graphs with Girth 5

A graph is called hypohamiltonian if it is not hamiltonian but becomes hamiltonian if any vertex is removed. Many hypohamiltonian planar cubic graphs have been found, starting with constructions of Thomassen in 1981. However, all the examples found until now had 4‐cycles. In this note we present the first examples of hypohamiltonian planar cubic graphs with cyclic connectivity 5, and thus girth 5. We show by computer search that the smallest members of this class are three graphs with 76 vertices.     

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.     

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.     

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.     

On triconnected and cubic plane graphs on given point sets

Let S be a set of n4 points in general position in the plane, and let h<n be the number of extreme points of S. We show how to construct a 3-connected plane graph with vertex set S, having max{3n/2,n+h−1} edges, and we prove that there is no 3-connected plane graph on top of S with a smaller number of edges. In particular, this implies that S admits a 3-connected cubic plane graph if and only if n4 is even and hn/2+1. The same bounds also hold when 3-edge-connectivity is considered. We also give a partial characterization of the point sets in the plane that can be the vertex set of a cubic plane graph.     

Polygon-circle and word-representable graphs

We describe work on the relationship between the independently-studied polygon-circle graphs and word-representable graphs.A graph G = (V, E) is word-representable if there exists a word w over the alpha-bet V such that letters x and y form a subword of the form xyxy ⋯ or yxyx ⋯ iff xy is an edge in E. Word-representable graphs generalise several well-known and well-studied classes of graphs [S. Kitaev, A Comprehensive Introduction to the Theory of Word-Representable Graphs, Lecture Notes in Computer Science 10396 (2017) 36–67; S. Kitaev, V. Lozin, “Words and Graphs”, Springer, 2015]. It is known that any word-representable graph is k-word-representable, that is, can be represented by a word having exactly k copies of each letter for some k dependent on the graph. Recognising whether a graph is word-representable is NP-complete ([S. Kitaev, V. Lozin, “Words and Graphs”, Springer, 2015, Theorem 4.2.15]). A polygon-circle graph (also known as a spider graph) is the intersection graph of a set of polygons inscribed in a circle [M. Koebe, On a new class of intersection graphs, Ann. Discrete Math. (1992) 141–143]. That is, two vertices of a graph are adjacent if their respective polygons have a non-empty intersection, and the set of polygons that correspond to vertices in this way are said to represent the graph. Recognising whether an input graph is a polygon-circle graph is NP-complete [M. Pergel, Recognition of polygon-circle graphs and graphs of interval filaments is NP-complete, Graph-Theoretic Concepts in Computer Science: 33rd Int. Workshop, Lecture Notes in Computer Science, 4769 (2007) 238–247]. We show that neither of these two classes is included in the other one by showing that the word-representable Petersen graph and crown graphs are not polygon-circle, while the non-word-representable wheel graph W₅ is polygon-circle. We also provide a more refined result showing that for any k ≥ 3, there are k-word-representable graphs which are neither (k −1)-word-representable nor polygon-circle.