Tetravalent half‐edge‐transitive graphs and non‐normal Cayley graphs

Let X be a vertex‐transitive graph, that is, the automorphism group Aut(X) of X is transitive on the vertex set of X. The graph X is said to be symmetric if Aut(X) is transitive on the arc set of X. suppose that Aut(X) has two orbits of the same length on the arc set of X. Then X is said to be half‐arc‐transitive or half‐edge‐transitive if Aut(X) has one or two orbits on the edge set of X, respectively. Stabilizers of symmetric and half‐arc‐transitive graphs have been investigated by many authors. For example, see Tutte [Canad J Math 11 (1959), 621–624] and Conder and Maru?i? [J Combin Theory Ser B 88 (2003), 67–76]. It is trivial to construct connected tetravalent symmetric graphs with arbitrarily large stabilizers, and by Maru?i? [Discrete Math 299 (2005), 180–193], connected tetravalent half‐arc‐transitive graphs can have arbitrarily large stabilizers. In this article, we show that connected tetravalent half‐edge‐transitive graphs can also have arbitrarily large stabilizers. A Cayley graph Cay(G, S) on a group G is said to be normal if the right regular representation R(G) of G is normal in Aut(Cay(G, S)). There are only a few known examples of connected tetravalent non‐normal Cayley graphs on non‐abelian simple groups. In this article, we give a sufficient condition for non‐normal Cayley graphs and by using the condition, infinitely many connected tetravalent non‐normal Cayley graphs are constructed. As an application, all connected tetravalent non‐normal Cayley graphs on the alternating group A₆ are determined. © 2011 Wiley Periodicals, Inc. J Graph Theory     

1/2-Transitive Graphs of Order 3p

A graph X is called vertex-transitive, edge-transitive, or arc-transitive, if the automorphism group of X acts transitively on the set of vertices, edges, or arcs of X, respectively. X is said to be 1/2-transitive, if it is vertex-transitive, edge-transitive, but not arc-transitive.In this paper we determine all 1/2-transitive graphs with 3p vertices, where p is an odd prime. (See Theorem 3.4.)     

A class of symmetric graphs with 2‐arc transitive quotients

Let Γ be an X‐symmetric graph admitting an X‐invariant partition ?? on V(Γ) such that Γ_?? is connected and (X, 2)‐arc transitive. A characterization of (Γ, X, ??) was given in [S. Zhou Eur J Comb 23 (2002), 741–760] for the case where |B|>|Γ(C)∩B|=2 for an arc (B, C) of Γ_??.We con‐sider in this article the case where |B|>|Γ(C)∩B|=3, and prove that Γ can be constructed from a 2‐arc transitive graph of valency 4 or 7 unless its connected components are isomorphic to 3 K ₂, C ₆ or K _{3, 3}. As a byproduct, we prove that each connected tetravalent (X, 2)‐transitive graph is either the complete graph K ₅ or a near n‐gonal graph for some n?4. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 232–245, 2010     

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.     

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.     

Normal Cayley graphs of finite groups

LetG be a finite group and let S be a nonempty subset of G not containing the identity element 1. The Cayley (di) graph X = Cay(G, S) of G with respect to S is defined byV (X)=G, E (X)={(g,sg)|g∈G, s∈S} A Cayley (di) graph X = Cay (G,S) is said to be normal ifR(G) ◃A = Aut (X). A group G is said to have a normal Cayley (di) graph if G has a subset S such that the Cayley (di) graph X = Cay (G, S) is normal. It is proved that every finite group G has a normal Cayley graph unlessG≅ℤ₄×ℤ₂ orG≅Q ₈×ℤ ₂ ^r (r⩾0) and that every finite group has a normal Cayley digraph, where Z_m is the cyclic group of orderm and Q₈ is the quaternion group of order 8. Project supported by the National Natural Science Foundation of China (Grant No. 10231060) and the Doctorial Program Foundation of Institutions of Higher Education of China.     

Graphs with Least Eigenvalue −2: The Star Complement Technique

Let G be a connected graph with least eigenvalue –2, of multiplicity k. A star complement for –2 in G is an induced subgraph H = G – X such that |X| = k and –2 is not an eigenvalue of H. In the case that G is a generalized line graph, a characterization of such subgraphs is used to decribe the eigenspace of –2. In some instances, G itself can be characterized by a star complement. If G is not a generalized line graph, G is an exceptional graph, and in this case it is shown how a star complement can be used to construct G without recourse to root systems.     

Half‐transitive graphs of valency 4 with prescribed attachment numbers

A graph X is said to be ½‐transitive if its automorphism group Aut X acts vertex‐ and edge‐, but not arc‐transitively on X. Then Aut X induces an orientation of the edges of X. If X has valency 4, then this orientation gives rise to so‐called alternating cycles, that is even length cycles in X whose every other vertex is the head and every other vertex is the tail of its two incident edges in the above orientation. All alternating cycles have the same length 2r(X), where r(X) is the radius of X, and any two adjacent alternating cycles intersect in the same number of vertices, called the attachment number a(X) of X. All known examples of ½‐transitive graphs have attachment number 1, r or 2r, where r is the radius of the graph. In this article, we construct ½‐transitive graphs with all other possible attachment numbers. The case of attachment number 2 is dealt with in more detail. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 89–99, 2000     

THE TOTAL CHROMATIC NUMBER OF PSEUDO-OUTERPLANAR GRAPHS

A Planar graph g is called a ipseudo outerplanar graph if there is a subset v.∈V(G),[V.]=i,such that G-V. is an outerplanar graph in particular when G-V.is a forest ,g is called a i-pseudo-tree .in this paper.the following results are proved;(1)the conjecture on the total coloring is true for all 1-pseudo-outerplanar graphs;(2)X1(G) 1 fo any 1-pseudo outerplanar graph g with △(G)≥3,where x4(G)is the total chromatic number of a graph g.     

On non-normal arc-transitive 4-valent dihedrants

Let X be a connected non-normal 4-valent arc-transitive Cayley graph on a dihedral group Dn such that X is bipartite, with the two bipartition sets being the two orbits of the cyclic subgroup within Dn. It is shown that X is isomorphic either to the lexicographic product Cn[2K1] with n 〉 4 even, or to one of the five sporadic graphs on 10, 14, 26, 28 and 30 vertices, respectively.     

Free Wreath Product by the Quantum Permutation Group

Let A be a compact quantum group, let nN ^* and let A _aut(X _n ) be the quantum permutation group on n letters. A free wreath product construction A*_w A _aut(X _n ) is introduced. This construction provides new examples of quantum groups, and is useful to describe the quantum automorphism group of the n-times disjoint union of a finite connected graph.     

Divisibility Graph for Symmetric and Alternating Groups

Let X be a nonempty set of positive integers and X* = X?{1}. The divisibility graph D(X) has X* as the vertex set, and there is an edge connecting a and b with a, b ∈ X* whenever a divides b or b divides a. Let X = cs(G) be the set of conjugacy class sizes of a group G. In this case, we denote D(cs(G)) by D(G). In this paper, we will find the number of connected components of D(G) where G is the symmetric group S _n or is the alternating group A _n .     

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     

Perfect Matchings of Regular Bipartite Graphs

Let G be a regular bipartite graph and . We show that there exist perfect matchings of G containing both, an odd and an even number of edges from X if and only if the signed graph , that is a graph G with exactly the edges from X being negative, is not equivalent to . In fact, we prove that for a given signed regular bipartite graph with minimum signature, it is possible to find perfect matchings that contain exactly no negative edges or an arbitrary one preselected negative edge. Moreover, if the underlying graph is cubic, there exists a perfect matching with exactly two preselected negative edges. As an application of our results we show that each signed regular bipartite graph that contains an unbalanced circuit has a 2‐cycle‐cover such that each cycle contains an odd number of negative edges.     

Cores of Imprimitive Symmetric Graphs of Order a Product of Two Distinct Primes

A retract of a graph Γ is an induced subgraph Ψ of Γ such that there exists a homomorphism from Γ to Ψ whose restriction to Ψ is the identity map. A graph is a core if it has no nontrivial retracts. In general, the minimal retracts of a graph are cores and are unique up to isomorphism; they are called the core of the graph. A graph Γ is G‐symmetric if G is a subgroup of the automorphism group of Γ that is transitive on the vertex set and also transitive on the set of ordered pairs of adjacent vertices. If in addition the vertex set of Γ admits a nontrivial partition that is preserved by G, then Γ is an imprimitive G‐symmetric graph. In this paper cores of imprimitive symmetric graphs Γ of order a product of two distinct primes are studied. In many cases the core of Γ is determined completely. In other cases it is proved that either Γ is a core or its core is isomorphic to one of two graphs, and conditions on when each of these possibilities occurs is given.     

Weak Borel chromatic numbers

Given a graph G whose set of vertices is a Polish space X, the weak Borel chromatic number of G is the least size of a family of pairwise disjoint G ‐independent Borel sets that covers all of X. Here a set of vertices of a graph G is independent if no two vertices in the set are connected by an edge. We show that it is consistent with an arbitrarily large size of the continuum that every closed graph on a Polish space either has a perfect clique or has a weak Borel chromatic number of at most ?₁. We observe that some weak version of Todorcevic's Open Coloring Axiom for closed colorings follows from MA. Slightly weaker results hold for F_σ‐graphs. In particular, it is consistent with an arbitrarily large size of the continuum that every locally countable F_σ‐graph has a Borel chromatic number of at most ?₁. We refute various reasonable generalizations of these results to hypergraphs (© 2011 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Closed graph and open mapping theorems for normed cones

A quasi-normed cone is a pair (X, p) such that X is a (not necessarily cancellative) cone and q is a quasi-norm on X. The aim of this paper is to prove a closed graph and an open mapping type theorem for quasi-normed cones. This is done with the help of appropriate notions of completeness, continuity and openness that arise in a natural way from the setting of bitopological spaces.     

On almost self-complementary graphs

A graph is called almost self-complementary if it is isomorphic to one of its almost complements X^c-I, where X^c denotes the complement of X and I a perfect matching (1-factor) in X^c. Almost self-complementary circulant graphs were first studied by Dobson and Šajna [Almost self-complementary circulant graphs, Discrete Math. 278 (2004) 23-44]. In this paper we investigate some of the properties and constructions of general almost self-complementary graphs. In particular, we give necessary and sufficient conditions on the order of an almost self-complementary regular graph, and construct infinite families of almost self-complementary regular graphs, almost self-complementary vertex-transitive graphs, and non-cyclically almost self-complementary circulant graphs.     

Bound on <Emphasis Type="Italic">m</Emphasis>-restricted Edge Connectivity

An m-restricted edge cut is an edge cut that separates a connected graph into a disconnected one with no components having order less than m. m-restrict edge connectivity λm is the cardinality of a minimum m-restricted edge cut. Let G be a connected k-regular graph of order at least 2m that contains m-restricted edge cuts and X be a subgraph of G. Let θ(X) denote the number of edges with one end in X and the other not in X and ξm=min{θ(X) ;X is a connected vertex-induced subgraph of order m}.It is proved in this paper that if G has girth at least m/2 2,then λm≤ξm.The upper bound of λm is sharp.