Almost all quartic half-arc-transitive weak metacirculants of Class II are of Class IV

A half-arc-transitive graph is a vertex- and edge- but not arc-transitive graph. A weak metacirculant is a graph admitting a transitive metacyclic group that is a group generated by two automorphisms ρ and σ, where ρ is (m,n)-semiregular for some integers m≥1 and n≥2, and where σ normalizes ρ. It was shown in [D. Maruši?, P. Šparl, On quartic half-arc-transitive metacirculants, J. Algebr. Comb. 28 (2008) 365-395] that each connected quartic half-arc-transitive weak metacirculant X belongs to one (or possibly more) of four classes of such graphs, reflecting the structure of the quotient graph X_ρ relative to the semiregular automorphism ρ. The first of these classes, called Class I, coincides with the class of so-called tightly attached graphs. Class II consists of the quartic half-arc-transitive weak metacirculants for which the quotient graph X_ρ is a cycle with a loop at each vertex. Class III consists of those graphs for which each vertex of the quotient graph X_ρ is connected to three other vertices, to one with a double edge. Finally, Class IV consists of those graphs for which X_ρ is a simple quartic graph.This paper consists of two results concerning graphs of Class II. It is shown that, with the exception of the Doyle-Holt graph and its canonical double cover, each quartic half-arc-transitive weak metacirculant of Class II is also of Class IV. It is also shown that although quartic half-arc-transitive weak metacirculants of Class II which are not tightly attached exist they are “almost tightly attached”. More precisely, their radius is at most four times their attachment number.     

On the classification of quartic half-arc-transitive metacirculants

A half-arc-transitive graph is a vertex- and edge- but not arc-transitive graph. Following Alspach and Parsons, a metacirculant graph is a graph admitting a transitive group generated by two automorphisms ρ and σ, where ρ is (m,n)-semiregular for some integers m≥1 and n≥2, and where σ normalizes ρ, cyclically permuting the orbits of ρ in such a way that σ^m has at least one fixed vertex. In a recent paper Maruši? and the author showed that each connected quartic half-arc-transitive metacirculant belongs to one (or possibly more) of four classes of such graphs, reflecting the structure of the quotient graph relative to the semiregular automorphism ρ. One of these classes coincides with the class of the so-called tightly-attached graphs, which have already been completely classified. In this paper a complete classification of the second of these classes, that is the class of quartic half-arc-transitive metacirculants for which the quotient graph relative to the semiregular automorphism ρ is a cycle with a loop at each vertex, is given.     

Constructing even radius tightly attached half-arc-transitive graphs of valency four

A finite graph X is half-arc-transitive if its automorphism group is transitive on vertices and edges, but not on arcs. When X is tetravalent, the automorphism group induces an orientation on the edges and a cycle of X is called an alternating cycle if its consecutive edges in the cycle have opposite orientations. All alternating cycles of X have the same length and half of this length is called the radius of X. The graph X is said to be tightly attached if any two adjacent alternating cycles intersect in the same number of vertices equal to the radius of X. Marušič (J. Comb. Theory B, 73, 41–76, 1998) classified odd radius tightly attached tetravalent half-arc-transitive graphs. In this paper, we classify the half-arc-transitive regular coverings of the complete bipartite graph K _4,4 whose covering transformation group is cyclic of prime-power order and whose fibre-preserving group contains a half-arc-transitive subgroup. As a result, two new infinite families of even radius tightly attached tetravalent half-arc-transitive graphs are constructed, introducing the first infinite families of tetravalent half-arc-transitive graphs of 2-power orders.      

A classification of tightly attached half-arc-transitive graphs of valency 4

A graph is said to be half-arc-transitive if its automorphism group acts transitively on the set of its vertices and edges but not on the set of its arcs. With each half-arc-transitive graph of valency 4 a collection of the so-called alternating cycles is associated, all of which have the same even length. Half of this length is called the radius of the graph in question. Moreover, any two adjacent alternating cycles have the same number of common vertices. If this number, the so-called attachment number, coincides with the radius, we say that the graph is tightly attached. In [D. Marušič, Half-transitive group actions on finite graphs of valency 4, J. Combin. Theory Ser. B 73 (1998) 41–76], Marušič gave a classification of tightly attached half-arc-transitive graphs of valency 4 with odd radius. In this paper the even radius tightly attached graphs of valency 4 are classified, thus completing the classification of all tightly attached half-arc-transitive graphs of valency 4.     

On graphs without crowns with regularμ-subgraphs

Anm-crown is the complete tripartite graphK _{1, 1,m} with parts of order 1, 1,m, and anm-claw is the complete bipartite graphK _1,m with parts of order 1,m, wherem ≥ 3. A vertexa of a graph Γ is calledweakly reduced iff the subgraph {x є Γ ‖a ^⊥ =x ^⊥} consists of one vertex. A graph Γ is calledweakly reduced iff all its vertices are weakly reduced. In the present paper we classify all connected weakly reduced graphs without 3-crowns, all of whose μ-subgraphs are regular graphs of constant nonzero valency. In particular, we generalize the characterization of Grassman and Johnson graphs due to Numata, and the characterization of connected reduced graphs without 3-claws due to Makhnev. Translated fromMatematicheskie Zametki, Vol. 67, No. 6, pp. 874–881, June, 2000. This research was supported by the Russian Foundation for Basic Research under grant No. 99-01-00462.     

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.     

On Non-Cayley Tetravalent Metacirculant Graphs

 In connection with the classification problem for non-Cayley tetravalent metacirculant graphs, three families of special tetravalent metacirculant graphs, denoted by Φ₁, Φ₂ and Φ₃, have been defined [11]. It has also been shown [11] that any non-Cayley tetravalent metacirculant graph is isomorphic to a union of disjoint copies of a non-Cayley graph in one of the families Φ₁, Φ₂ or Φ₃. A natural question raised from the result is whether all graphs in these families are non-Cayley. We have proved recently in [12] that every graph in Φ₂ is non-Cayley. In this paper, we show that every graph in Φ₁ is also a connected non-Cayley graph and find an infinite class of connected non-Cayley graphs in the family Φ₃. Received: October, 2001 Final version received: July 29, 2002     

The binding number of line graphs and total graphs

D.R. Woodall [7] introduced the concept of the binding number of a graphG, bind (G), and proved that bind(G)≦(|V(G)|−1)/(|V(G)|−ρ(G)). In this paper, some properties of a graph with bind(G)=(|V(G)|−1)/(|V(G)|−ρ(G)) are given, and the binding number of some line graphs and total graphs are determined.     

Tetravalent half-arc-transitive graphs of order 2<Emphasis Type="Italic">pq</Emphasis>

A graph is half-arc-transitive if its automorphism group acts transitively on its vertex set, edge set, but not arc set. Let p and q be primes. It is known that no tetravalent half-arc-transitive graphs of order 2p ² exist and a tetravalent half-arc-transitive graph of order 4p must be non-Cayley; such a non-Cayley graph exists if and only if p−1 is divisible by 8 and it is unique for a given order. Based on the constructions of tetravalent half-arc-transitive graphs given by Marušič (J. Comb. Theory B 73:41–76, 1998), in this paper the connected tetravalent half-arc-transitive graphs of order 2pq are classified for distinct odd primes p and q.     

The Crossing Number of Cartesian Products of Complete Bipartite Graphs K 2, m with Paths P n

Most results on the crossing number of a graph focus on the special graphs, such as Cartesian products of small graphs with paths P_n, cycles C_n or stars S_n. In this paper, we extend the results to Cartesian products of complete bipartite graphs K_2,m with paths P_n for arbitrary m ≥ 2 and n ≥ 1. Supported by the NSFC (No. 10771062) and the program for New Century Excellent Talents in University.     

On a graph property generalizing planarity and flatness

We introduce a topological graph parameter σ(G), defined for any graph G. This parameter characterizes subgraphs of paths, outerplanar graphs, planar graphs, and graphs that have a flat embedding as those graphs G with σ(G)≤1,2,3, and 4, respectively. Among several other theorems, we show that if H is a minor of G, then σ(H)≤σ(G), that σ(K _n )=n−1, and that if H is the suspension of G, then σ(H)=σ(G)+1. Furthermore, we show that μ(G)≤σ(G) + 2 for each graph G. Here μ(G) is the graph parameter introduced by Colin de Verdière in [2].     

The smallest degree sum that yields potentially Kr,r-graphic sequences

We consider a variation of a classical Turán-type extremal problem as follows: Determine the smallest even integer σ(K_r,r,n) such that every n-term graphic sequence π = (d₁,d₂,...,d_n) with term sum σ(π) = d₁ + d₂ + ... + d_n ≥ σ(K_r,r,n) is potentially K_r,r-graphic, where K_r,r is an r × r complete bipartite graph, i.e. π has a realization G containing K_r,r as its subgraph. In this paper, the values σ(K_r,r,n) for even r and n ≥ 4r² - r - 6 and for odd r and n ≥ 4r² + 3r - 8 are determined.     

Survey of Double Vertex Graphs

 Let G be a (V,E) graph of order p≥2. The double vertex graph U ₂ (G) is the graph whose vertex set consists of all 2-subsets of V such that two distinct vertices {x,y} and {u,v} are adjacent if and only if |{x,y}∩{u,v}|=1 and if x=u, then y and v are adjacent in G. For this class of graphs we discuss the regularity, eulerian, hamiltonian, and bipartite properties of these graphs. A generalization of this concept is n-tuple vertex graphs, defined in a manner similar to double vertex graphs. We also review several recent results for n-tuple vertex graphs. Received: October, 2001 Final version received: September 20, 2002 Dedicated to Frank Harary on the occasion of his Eightieth Birthday and the Manila International Conference held in his honor     

Distance-transitive dihedrants

The main result of this article is a classification of distance-transitive Cayley graphs on dihedral groups. We show that a Cayley graph X on a dihedral group is distance-transitive if and only if X is isomorphic to one of the following graphs: the complete graph K _2n ; a complete multipartite graph K _t×m with t anticliques of size m, where t m is even; the complete bipartite graph without 1-factor K _n,n − nK ₂; the cycle C _2n ; the incidence or the non-incidence graph of the projective geometry PG _d-1(d,q), d ≥ 2; the incidence or the non-incidence graph of a symmetric design on 11 vertices.     

On Small World Semiplanes with Generalised Schubert Cells

The well known “real-life examples” of small world graphs, including the graph of binary relation: “two persons on the earth know each other” contains cliques, so they have cycles of order 3 and 4. Some problems of Computer Science require explicit construction of regular algebraic graphs with small diameter but without small cycles. The well known examples here are generalised polygons, which are small world algebraic graphs i.e. graphs with the diameter d≤clog  _k−1(v), where v is order, k is the degree and c is the independent constant, semiplanes (regular bipartite graphs without cycles of order 4); graphs that can be homomorphically mapped onto the ordinary polygons. The problem of the existence of regular graphs satisfying these conditions with the degree ≥k and the diameter ≥d for each pair k≥3 and d≥3 is addressed in the paper. This problem is positively solved via the explicit construction. Generalised Schubert cells are defined in the spirit of Gelfand-Macpherson theorem for the Grassmanian. Constructed graph, induced on the generalised largest Schubert cells, is isomorphic to the well-known Wenger’s graph. We prove that the family of edge-transitive q-regular Wenger graphs of order 2q ⁿ , where integer n≥2 and q is prime power, q≥n, q>2 is a family of small world semiplanes. We observe the applications of some classes of small world graphs without small cycles to Cryptography and Coding Theory.     

EMBEDDINGS OF ONE KIND OF GRAPHS

The purpose of this paper is to display a new kind of simple graphs which belong to B. inwhich any graph has its orientable genus n,n≥3. Furthermore, for any integer k,1≤k≤n,there exists a graph B^kn of B. such that the non-orientable genus of B^kn is k.     

Complexes of graph homomorphisms

Hom(G, H) is a polyhedral complex defined for any two undirected graphsG andH. This construction was introduced by Lovász to give lower bounds for chromatic numbers of graphs. In this paper we initiate the study of the topological properties of this class of complexes. We prove that Hom(K _m, K_n) is homotopy equivalent to a wedge of (n−m)-dimensional spheres, and provide an enumeration formula for the number of the spheres. As a corollary we prove that if for some graphG, and integersm≥2 andk≥−1, we have ϖ ₁ ^k (Hom(K _m, G))≠0, thenχ(G)≥k+m; here ℤ₂-action is induced by the swapping of two vertices inK _m, and ϖ₁ is the first Stiefel-Whitney class corresponding to this action. Furthermore, we prove that a fold in the first argument of Hom(G, H) induces a homotopy equivalence. It then follows that Hom(F, K _n) is homotopy equivalent to a direct product of (n−2)-dimensional spheres, while Hom(F, K _n) is homotopy equivalent to a wedge of spheres, whereF is an arbitrary forest andF is its complement. The second author acknowledges support by the University of Washington, Seattle, the Swiss National Science Foundation Grant PP002-102738/1, the University of Bern, and the Royal Institute of Technology, Stockholm.     

The Erdös-Jacobson-Lehel conjecture on potentiallyP k-graphic sequence is true

A variation in the classical Turan extrernal problem is studied. A simple graphG of ordern is said to have propertyPk if it contains a clique of sizek+1 as its subgraph. Ann-term nonincreasing nonnegative integer sequence π=(d₁, d₂,⋯, d₂) is said to be graphic if it is the degree sequence of a simple graphG of ordern and such a graphG is referred to as a realization of π. A graphic sequence π is said to be potentiallyP _k-graphic if it has a realizationG having propertyP _k . The problem: determine the smallest positive even number σ(k, n) such that everyn-term graphic sequence π=(d₁, d₂,…, d₂) without zero terms and with degree sum σ(π)=(d ₁+d ₂+ …+d ₂) at least σ(k,n) is potentially P_k-graphic has been proved positive. Project supported by the National Natural Science Foundation of China (Grant No. 19671077) and the Doctoral Program Foundation of National Education Department of China.     

Tight Distance-Regular Graphs and the Q-Polynomial Property

 Let Γ denote a distance-regular graph with diameter d≥3, and assume Γ is tight (in the sense of Jurišić, Koolen and Terwilliger). Let θ denote the second largest or smallest eigenvalue of Γ, and let σ₀,σ₁,…,σ _d denote the associated cosine sequence. We obtain an inequality involving σ₀,σ₁,…,σ _d for each integer i (1≤i≤d−1), and we show equality for all i is closely related to Γ being Q-polynomial with respect to θ. We use this idea to investigate the Q-polynomial structures in tight distance-regular graphs. Received: January 30, 1998 Final version received: August 14, 1998     

List Point Arboricity of Dense Graphs

Let G be a simple graph. The point arboricity ρ(G) of G is defined as the minimum number of subsets in a partition of the point set of G so that each subset induces an acyclic subgraph. The list point arboricity ρ _l (G) is the minimum k so that there is an acyclic L-coloring for any list assignment L of G which |L(v)| ≥ k. So ρ(G) ≤ ρ _l (G) for any graph G. Xue and Wu proved that the list point arboricity of bipartite graphs can be arbitrarily large. As an analogue to the well-known theorem of Ohba for list chromatic number, we obtain ρ _l (G + K _n ) = ρ(G + K _n ) for any fixed graph G when n is sufficiently large. As a consequence, if ρ(G) is close enough to half of the number of vertices in G, then ρ _l (G) = ρ(G). Particularly, we determine that , where K _2(n) is the complete n-partite graph with each partite set containing exactly two vertices. We also conjecture that for a graph G with n vertices, if then ρ _l (G) = ρ(G). Research supported by NSFC (No.10601044) and XJEDU2006S05.