关于{P2, Ci| i≥3}-覆盖图

设 Ｇ是一个图,若对于 Ｇ的任意一边 Ｇ都有｛Ｐ_２,Ｃｉ｜ｉ－＞３｝－因子含有这条边,则称Ｇ是｛Ｐ_２,Ｃｉ｜ｉ－＞３｝－覆盖图．本文给出连通非二分图Ｇ是｛Ｐ２,Ｃｉ｜ｉ－＞３｝－覆盖图的充要条件为任给Ｓ■Ｖ（Ｇ）,Ｖ（Ｇ）≠Ｓ≠■有ｉ（Ｇ－Ｓ）＿＞｜Ｓ｜－１成立．     

Dirac定理的局部化与Hamilton图

设Ｇ为一个ｎ阶２－连通图，ｎ≥３．若｜Ｄ_ｎ／２（Ｋ_１，３）｜≥２且满足下述条件之一：ｉ）｜Ｄ_ｎ／２（Ｋ_１，３＋ｅ）｜≥２，ii）若Ｋ_１，３＋ｅ→Ｇ，ｘｙ(?)Ｅ（Ｋ_１，３＋ｅ），则ｍａｘ｛ｄＧ（ｘ），ｄＧ（ｙ）｝≥ｎ／２，则Ｇ是一个Ｈａｍｉｌｔｏｎｉａｎ图或其闭包为ｓＰ|⊕Ｈ，这里ｓＰ⊕Ｈ是一类极小２－边连通图．     

关于无爪Hamilton图的一个泛圈性结果

一个图Ｇ是泛圈的，如果它含有长为３，４，…，ｎ（＝｜Ｖ（Ｇ）｜）的圈．本文探讨了一类无爪Ｈａｍｉｌｔｏｎ图的圈结构，主要结果为：设Ｇ＝（Ｖ，Ｅ）是ｎ阶无爪Ｈａｍｉｌｔｏｎ图．如果Ｇ中有节点ｘ使ｄ（ｘ）≧ｎ／２且Ｎ（ｘ）连通，则除少数几个例外，Ｇ是泛圈的．     

完全图圈分解的一种新方法

本文给出完全图圈分解的一种新方法，设Ｋｎ（ｎ≥３）是一个ｎ阶完全图，我们得到下列结果：（１）若ｎ为奇数，Ｇ是ｎ阶群，并且｛ｏ（ｘ）│∈Ｇ，ｏ（ｘ）≥３｝＝｛ａ１，…，ａｔ｝，则Ｋｎ＝ｍ１Ｃａ１＋…＋ｍｔＣａｔ。（２）若ｎ为偶数，Ｇ是ｎ阶群，Ｔ＝｛ｘ│ｘ∈Ｇ，ｏ（ｘ）＝２｝＝｛ｘ０，ｘ１，ｙ１，…，ｘｓ，ｙｓ｝，ｏ（ｘｉｙｉ）＝ｂｉ，ｉ＝１，…，ｓ及｛ｏ（ｘ）│ｘ∈Ｇ，ｏ（ｘ）≥｝＝｛ａ１，…，ａｔ     

代数综合测试题

一、选择题１．设集合Ｍ＝｛ｘ｜２２－ｘ≥１｝,集合Ｎ＝｛ｘ｜ｘ２－２ｘ－３＜０｝,集合Ｍ∩Ｎ＝（）（Ａ）｛ｘ｜０≤ｘ＜１｝（Ｂ）｛ｘ｜０≤ｘ＜２｝（Ｃ）｛ｘ｜０≤ｘ≤１｝（Ｄ）｛ｘ｜０≤ｘ≤２｝２．已知函数ｆ（ｘ）＝２ｘ,则函数ｙ＝｜ｆ－１（ｘ－１...     

关于｛P2,Ci│i≥3｝—覆盖图

设Ｇ是一个图,若对于Ｇ的任意一边Ｇ都有｛Ｐ２,Ｃｉ│ｉ≥３｝－因子含有这条边,则称Ｇ是｛Ｐ２,Ｃｉ│ｉ≥３｝－覆盖图。本文给出连通非二分图Ｇ是｛Ｐ２,Ｃｉ│ｉ≥３｝－覆盖图的充要条件为任给Ｓ包含于Ｖ（Ｇ）,Ｖ（Ｇ）≠Ｓ≠ф有ｉ（Ｇ－Ｓ）≤│Ｓ│－１成立。     

大次和1—坚韧图中的最长圈

给一个图Ｇ，定义σ３（Ｇ）＝ｍｉｎ｛Σ＾３ｉ＝１ｄ（ｖｉ）│｛ｖ１，ｖ２，ｖ３｝｝是Ｇ的无关集｝，ｐ３（Ｇ）＝ｍｉｎ｛│Ｕ＾３ｉ＝１Ｎ（ｖｉ）‖｛ｖ１，ｖ２，ｖ３｝是Ｇ中使│ｎ＾３ｉ＝１Ｎ（ｖｉ）│≠０｝的无关集｝。本文证明了：设Ｇ是ｎ阶１－坚韧图，如果σ３（Ｇ）≥ｎ，则Ｇ包含长度至少为ｍｉｎ｛ｎ，２ｐ３（Ｇ）＋４｝的圈，为个结果推广了若干已知结果，也解决了Ｂｒｏｅｒｓｍａ－Ｈｅｕｖｅｌ－Ｖｅｌｄ     

△(G)=3的外平面图的邻强边染色

对图Ｇ（Ｖ,Ｅ）,一正常ｋ－边染色ｆ称为Ｇ（Ｖ,Ｅ）的一邻强边染色,当且仅当对任意ｕｖ∈Ｅ（Ｇ）有ｆ［ｕ］≠ｆ［ｖ］．其中ｆ［ｕ］＝｛ｆ（ｕｗ）｜ｕｗ∈Ｅ（Ｇ）｝,ｆ（ｕｗ）表示染边ｕｗ的色,并称ｘａｓ（Ｇ）＝ｍｉｎ｛ｋ｜存在Ｃ的一ｋ种色的郁强边染色｝为Ｇ的邻强边色数．本文证明了对△（Ｇ）＝３的２－连通外平面图,有ｘａｓ（Ｇ）＝４．     

图的独立数的一个新下界

设α（Ｇ）表示简单图Ｇ＝（Ｖ，Ｅ）的独立数．本文给出了α（Ｇ）的一个新的下界：α（Ｇ）≥∑ｖ∈Ｖ（λｄ（ｖ）＋１）／（ｄ（ｖ）＋λｄ（ｖ）＋１），其中λｄ（ｖ）＝ｍａｘ｛０，βＮ（ｖ）－ｄ（ｖ）｝，ｄ（ｖ）＝｜Ｎ（ｖ）｜，Ｎ（ｖ）＝｛ｗ∈Ｖ｜（ｖ，ｗ）∈Ｅ｝，βＮ（ｖ）＝ｍｉｎｗ∈Ｎ（ｖ）ｄ（ｗ）．     

一类泛连通无爪图

本文证明了如果Ｇ是３连通无爪图，且Ｇ的每个导出子图Ａ，Ａ＋都满足（ａ１，ａ２），则Ｇ是泛连通图（除了当ｕ，ｖ∈Ｖ（Ｇ），ｄ（ｕ，ｖ）＝１时，Ｇ中可能不存在（ｕ，ｖ）－ｋ路外，这里２≤ｋ≤４）．     

The Gray graph revisited

Certain graph‐theoretic properties and alternative definitions of the Gray graph, the smallest known cubic edge‐ but not vertex‐transitive graph, are discussed in detail. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 1–7, 2000     

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$.     

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.     

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

图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.     

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.