A census of semisymmetric cubic graphs on up to 768 vertices

A list is given of all semisymmetric (edge- but not vertex-transitive) connected finite cubic graphs of order up to 768. This list was determined by the authors using Goldschmidt's classification of finite primitive amalgams of index (3,3), and a computer algorithm for finding all normal subgroups of up to a given index in a finitely-presented group. The list includes several previously undiscovered graphs. For each graph in the list, a significant amount of information is provided, including its girth and diameter, the order of its automorphism group, the order and structure of a minimal edge-transitive group of automorphisms, its Goldschmidt type, stabiliser partitions, and other details about its quotients and covers. A summary of all known infinite families of semisymmetric cubic graphs is also given, together with explicit rules for their construction, and members of the list are identified with these. The special case of those graphs having K_1,3 as a normal quotient is investigated in detail. Supported in part by N.Z. Marsden Fund (grant no. UOA 124) and N.Z. Centres of Research Excellence Fund (grant no. UOA 201) Supported in part by “Ministrstvo za šolstvo, znanost in šport Slovenije”, research program no. 101-506. Supported in part by research projects no. Z1-4186-0101 and no. Z1-3124-0101. The fourth author would like to thank the University of Auckland for hospitality during his visit there in 2003.     

An infinite series of regular edge‐ but not vertex‐transitive graphs

Let n be an integer and q be a prime power. Then for any 3 ≤ n ≤ q?1, or n=2 and q odd, we construct a connected q‐regular edge‐but not vertex‐transitive graph of order 2qⁿ⁺¹. This graph is defined via a system of equations over the finite field of q elements. For n=2 and q=3, our graph is isomorphic to the Gray graph. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 249–258, 2002     

An infinite family of biprimitive semisymmetric graphs

A regular and edge-transitive graph that is not vertex-transitive is said to be semisymmetric. Every semisymmetric graph is necessarily bipartite, with the two parts having equal size and the automorphism group acting transitively on each of these two parts. A semisymmetric graph is called biprimitive, if its automorphism group acts primitively on each part. In this article, a classification of biprimitive semisymmetric graphs arising from the action of the group PSL(2, p), p ≡ ±1 (mod 8) a prime, acting on cosets of S₄ is given, resulting in several new infinite families of biprimitive semisymmetric graphs. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 217–228, 1999     

An infinite family of biquasiprimitive 2-arc transitive cubic graphs

A new infinite family of bipartite cubic 3-arc transitive graphs is constructed and studied. They provide the first known examples admitting a 2-arc transitive vertex-biquasiprimitive group of automorphisms for which the index two subgroup fixing each half of the bipartition is not quasiprimitive on either bipartite half.     

Constructing cubic edge‐ but not vertex‐transitive graphs

An infinite family of cubic edge‐transitive but not vertex‐transitive graphs with edge stabilizer isomorphic to ℤ₂ is constructed. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 152–160, 2000     

An infinite family of cubic nonnormal Cayley graphs on nonabelian simple groups

We construct a connected cubic nonnormal Cayley graph on ${\mathrm{A}}_{2^m?1}$ for each integer $m?4$ and determine its full automorphism group. This is the first infinite family of connected cubic nonnormal Cayley graphs on nonabelian simple groups.     

On the minor-minimal 2-connected graphs having a fixed minor

Let H be a graph with κ₁ components and κ₂ blocks, and let G be a minor-minimal 2-connected graph having H as a minor. This paper proves that |E(G)|−|E(H)|(κ₁−1)+β(κ₂−1) for all (,β) such that +β5,2+5β20, and β3. Moreover, if one of the last three inequalities fails, then there are graphs G and H for which the first inequality fails.     

An infinite family of subcubic graphs with unbounded packing chromatic number

Recently, Balogh et al. (2018) answered in negative the question that was posed in several earlier papers whether the packing chromatic number is bounded in the class of graphs with maximum degree 3. In this note, we present an explicit infinite family of subcubic graphs with unbounded packing chromatic number.     

Unavoidable doubly connected large graphs

A connected graph is doubly connected if its complement is also connected. The following Ramsey-type theorem is proved in this paper. There exists a function h(n), defined on the set of integers exceeding three, such that every doubly connected graph on at least h(n) vertices must contain, as an induced subgraph, a doubly connected graph, which is either one of the following graphs or the complement of one of the following graphs:

(1) P_n, a path on n vertices;

(2) K_1,n^s, the graph obtained from K_1,n by subdividing an edge once;

(3) K_2,ne, the graph obtained from K_2,n by deleting an edge;

(4) K_2,n⁺, the graph obtained from K_2,n by adding an edge between the two degree-n vertices x₁ and x₂, and a pendent edge at each x_i.

Two applications of this result are also discussed in the paper.     

Connected but not path-connected subspaces of infinite graphs

Solving a problem of Diestel [9] relevant to the theory of cycle spaces of infinite graphs, we show that the Freudenthal compactification of a locally finite graph can have connected subsets that are not path-connected. However we prove that connectedness and path-connectedness to coincide for all but a few sets, which have a complicated structure.     

A construction of an infinite family of 2-arc transitive polygonal graphs of arbitrary odd girth

A near-polygonal graph is a graph Γ which has a set C of m-cycles for some positive integer m such that each 2-path of Γ is contained in exactly one cycle in C. If m is the girth of Γ then the graph is called polygonal. We provide a construction of an infinite family of polygonal graphs of arbitrary odd girth with 2-arc transitive automorphism groups.     

An infinite family of tetravalent half-arc-transitive graphs

A graph is half-arc-transitive if its automorphism group acts transitively on vertices and edges, but not on arcs. In this paper, a new infinite family of tetravalent half-arc-transitive graphs with girth 4 is constructed, each of which has order 16m such that m>1 is a divisor of 2t²+2t+1 for a positive integer t and is tightly attached with attachment number 4m. The smallest graph in the family has order 80.     

Consequences of an algorithm for bridged graphs

Chepoi showed that every breadth first search of a bridged graph produces a cop-win ordering of the graph. We note here that Chepoi's proof gives a simple proof of the theorem that G is bridged if and only if G is cop-win and has no induced cycle of length four or five, and that this characterization together with Chepoi's proof reduces the time complexity of bridged graph recognition. Specifically, we show that bridged graph recognition is equivalent to (C₄,C₅)-free graph recognition, and reduce the best known time complexity from O(n⁴) to O(n^3.376).     

Degree conditions for Hamiltonian graphs to have [a,b]-factors containing a given Hamiltonian cycle

Let 1a<b be integers and G a Hamiltonian graph of order |G|(a+b)(2a+b)/b. Suppose that δ(G)a+2 and max{deg_G(x), deg_G(y)}a|G|/(a+b)+2 for each pair of nonadjacent vertices x and y in G. Then G has an [a,b]-factor which is edge-disjoint from a given Hamiltonian cycle. The lower bound on the degree condition is sharp. For the case of odd a=b, there exists a graph satisfying the conditions of the theorem but having no desired factor. As consequences, we have the degree conditions for Hamiltonian graphs to have [a,b]-factors containing a given Hamiltonian cycle.     

A characterization of level planar graphs

We present a characterization of level planar graphs in terms of minimal forbidden subgraphs called minimal level non-planar (MLNP) subgraph patterns. We show that an MLNP subgraph pattern is completely characterized by either a tree, a level non-planar cycle or a level planar cycle with certain path augmentations.     

A note on the approximability of the toughness of graphs

We show that, if NP≠ZPP, for any >0, the toughness of a graph with n vertices is not approximable in polynomial time within a factor of . We give a 4-approximation for graphs with toughness bounded by and we show that this result cannot be generalized to graphs with a bounded toughness. More exactly we prove that there is no constant approximation for graphs with bounded toughness, unless P=NP.     

An explicit characterization of cubic symmetric bi-Cayley graphs on nonabelian simple groups

One of the remarkable contributions in the study of symmetric Cayley graphs on nonabelian simple groups is the complete classification of such graphs that are cubic and nonnormal. This naturally motivates the study of cubic (normal and nonnormal) symmetric bi-Cayley graphs on nonabelian simple groups. In this paper, the full automorphism groups of these graphs are determined, and necessary and sufficient conditions are given for a graph being a cubic normal symmetric Cayley or bi-Cayley graph on a nonabelian simple group (one may then find many examples). As an application, we also prove that cubic symmetric Cayley graphs on nonabelian simple groups are stable.     

Sum coloring and interval graphs: a tight upper bound for the minimum number of colors

The SUM COLORING problem consists of assigning a color c(v_i)Z⁺ to each vertex v_iV of a graph G=(V,E) so that adjacent nodes have different colors and the sum of the c(v_i)'s over all vertices v_iV is minimized. In this note we prove that the number of colors required to attain a minimum valued sum on arbitrary interval graphs does not exceed min{n;2χ(G)−1}. Examples from the papers [Discrete Math. 174 (1999) 125; Algorithmica 23 (1999) 109] show that the bound is tight.     

一类点传递但边不传递的正则图及其覆盖图

利用轮子图构造出一类图,证明了这类图都是点传递但边不传递的正则图,并证明了通过覆盖的方法,可以使一类2m²(m>3,m为正整数)阶非边传递图变成对称图,这类对称图实际上是亚循环图.