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     

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.     

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.     

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

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

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

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.     

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.     

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 Rooted Packings,Decompositions, and Factors of Graphs

In this article, we study so‐called rooted packings of rooted graphs. This concept is a mutual generalization of the concepts of a vertex packing and an edge packing of a graph. A rooted graph is a pair , where G is a graph and . Two rooted graphs and are isomorphic if there is an isomorphism of the graphs G and H such that S is the image of T in this isomorphism. A rooted graph is a rooted subgraph of a rooted graph if H is a subgraph of G and . By a rooted ‐packing into a rooted graph we mean a collection of rooted subgraphs of isomorphic to such that the sets of edges are pairwise disjoint and the sets are pairwise disjoint. In this article, we concentrate on studying maximum ‐packings when H is a star. We give a complete classification with respect to the computational complexity status of the problems of finding a maximum ‐packing of a rooted graph when H is a star. The most interesting polynomial case is the case when H is the 2‐edge star and S contains the center of the star only. We prove a min–max theorem for ‐packings in this case.     

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

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

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

Cubic one-regular graphs of order twice a square-free integer

A graph is one-regular if its automorphism group acts regularly on the set of its arcs.Let n be a square-free integer.In this paper,we show that a cubic one-regular graph of order 2n exists if and only if n=3~tp1p2…p_s≥13,where t≤1,s≥1 and p_i's are distinct primes such that 3|(P_i—1). For such an integer n,there are 2~(s-1) non-isomorphic cubic one-regular graphs of order 2n,which are all Cayley graphs on the dihedral group of order 2n.As a result,no cubic one-regular graphs of order 4 times an odd square-free integer exist.     

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.     

On magic and supermagic circulant graphs

A graph is called magic (supermagic) if it admits a labelling of the edges by pairwise different (and consecutive) integers such that the sum of the labels of the edges incident with a vertex is independent of the particular vertex. In the paper, we characterize magic circulant graphs and 3-regular supermagic circulant graphs. We establish some conditions for supermagic circulant graphs.     

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

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

On the Dot Product Graph of a Commutative Ring

Let A be a commutative ring with nonzero identity, 1 ≤ n < ∞ be an integer, and R = A × A × … ×A (n times). The total dot product graph of R is the (undirected) graph TD(R) with vertices R* = R?{(0, 0,…, 0)}, and two distinct vertices x and y are adjacent if and only if x·y = 0 ∈ A (where x·y denote the normal dot product of x and y). Let Z(R) denote the set of all zero-divisors of R. Then the zero-divisor dot product graph of R is the induced subgraph ZD(R) of TD(R) with vertices Z(R)* = Z(R)?{(0, 0,…, 0)}. It follows that each edge (path) of the classical zero-divisor graph Γ(R) is an edge (path) of ZD(R). We observe that if n = 1, then TD(R) is a disconnected graph and ZD(R) is identical to the well-known zero-divisor graph of R in the sense of Beck–Anderson–Livingston, and hence it is connected. In this paper, we study both graphs TD(R) and ZD(R). For a commutative ring A and n ≥ 3, we show that TD(R) (ZD(R)) is connected with diameter two (at most three) and with girth three. Among other things, for n ≥ 2, we show that ZD(R) is identical to the zero-divisor graph of R if and only if either n = 2 and A is an integral domain or R is ring-isomorphic to ?₂ × ?₂ × ?₂.     

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.