Enumeration of cubic Cayley graphs on dihedral groups

Let p be an odd prime, and D_2p =<a, b|a^p = b² = 1, bab = a^-1 the dihedral group of order 2p. In this paper, we completely classify the cubic Cayley graphs on D_2p up to isomorphism by means of spectral method. By the way, we show that two cubic Cayley graphs on D_2p are isomorphic if and only if they are cospectral. Moreover, we obtain the number of isomorphic classes of cubic Cayley graphs on D_2p by using Gauss' celebrated law of quadratic reciprocity.     

Nowhere-zero 3-flows in Cayley graphs on generalized dihedral group and generalized quaternion group

Tutte conjectured that every 4-edge-connected graph admits a nowhere-zero 3-flow. In this paper, we show that this conjecture is true for Cayley graph on generalized dihedral groups and generalized quaternion groups, which generalizes the result of F. Yang and X. Li [Inform. Process. Lett., 2011, 111: 416–419]. We also generalizes an early result of M. Nánásiová and M. ?koviera [J. Algebraic Combin., 2009, 30: 103–110].     

Vertex-minimal graphs with dihedral symmetry I

Let $D_{2n}$ denote the dihedral group of order $2n$, where $n\ge 3$. In this article, we build upon the findings of Haggard and McCarthy who, for certain values of $n$, produced a vertex-minimal graph with dihedral symmetry. Specifically, Haggard considered the situation when $\frac{n}{2}$ or $n$ is a prime power, and McCarthy investigated the case when $n$ is not divisible by $2$, $3$ or $5$. In this article, we assume $n$ is not divisible by $4$ and construct a vertex-minimal graph whose automorphism group is isomorphic to $D_{2n}$.     

On factor-invariant graphs

We classify trivalent vertex-transitive graphs whose edge sets have a partition into a Hamilton cycle and a 1-factor that is invariant under the action of the full automorphism group.     

Connected cubic s-arc-regular Cayley graphs of finite nonabelian simple groups

A graph is said to be s-arc-regular if its full automorphism group acts regularly on the set of its s-arcs. In this paper, we investigate connected cubic s-arc-regular Cayley graphs of finite nonabelian simple groups. Two suffcient and necessary conditions for such graphs to be 1- or 2-arc-regular are given and based on the conditions, several infinite families of 1-or 2-arc-regular cubic Cayley graphs of alternating groups are constructed.     

On Symmetric Cayley Graphs of Valency Eleven

A Cayley graph Γ=Cay(G,S)is said to be normal if G is normal in Aut Γ.In this paper,we investigate the normality problem of the connected 11-valent symmetric Cayley graphs Γ of finite nonabelian simple groups G,where the vertex stabilizer Av is soluble for A=Aut Γ and v ∈ VΓ.We prove that either Γ is normal or G=A5,A10,A54,A274,A549 or A1099.Further,11-valent symmetric nonnormal Cayley graphs of A5,A54 and A274 are constructed.This provides some more examples of nonnormal 11-valent symmetric Cayley graphs of finite nonabelian simple groups after the first graph of this kind(of valency 11)was constructed by Fang,Ma and Wang in 2011.     

Connected cubic <Emphasis Type="Italic">s</Emphasis>-arc-regular Cayley graphs of finite nonabelian simple groups

A graph is said to be s-arc-regular if its full automorphism group acts regularly on the set of its s-arcs. In this paper, we investigate connected cubic s-arc-regular Cayley graphs of finite nonabelian simple groups. Two sufficient and necessary conditions for such graphs to be 1- or 2-arcregular are given and based on the conditions, several infinite families of 1- or 2-arc-regular cubic Cayley graphs of alternating groups are constructed. This work was supported by Guangxi Science Foundations (Grant No. 0832054) and Guangxi Postgraduate Education Innovation Research (Grant No. 2008105930701M102)     

Stereology of dihedral angles

The paper presents a short survey of stereological problems concerning dihedral angles, their solutions and applications, and introduces a graph for determining the distribution functions of planar angles under the hypothesis that dihedral angles in ³ are of the same size and create a random field.     

A structural theorem on embedded graphs and its application to colorings

In this paper, a Lebesgue type theorem on the structure of graphs embedded in the surface of characteristic σ≤ 0 is given, that generalizes a result of Borodin on plane graphs. As a consequence, it is proved that every such graph without i-circuits for 4 ≤ i ≤ 11 - 3σ is 3-choosable, that offers a new upper bound to a question of Y. Zhao.     

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.     

Antisymmetric flows on planar graphs

We prove that every oriented planar graph admits a homomorphism to the Paley tournament P₂₇₁ and hence that every oriented planar graph has an antisymmetric flow number and a strong oriented chromatic number of at most 271. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 200–210, 2006     

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.     

Augmentation quotients for complex representation rings of dihedral groups

Denote by D _m the dihedral group of order 2m. Let ℛ(D _m ) be its complex representation ring, and let Δ(D _m ) be its augmentation ideal. In this paper, we determine the isomorphism class of the n-th augmentation quotient Δ ⁿ (D _m )/Δ ⁿ⁺¹(D _m ) for each positive integer n.     

On Cayley graphs of rectangular groups

In this paper, we first give a characterization of Cayley graphs of rectangular groups. Then, vertex-transitivity of Cayley graphs of rectangular groups is considered. Further, it is shown that Cayley graphs Cay(S,C) which are automorphism-vertex-transitive, are in fact Cayley graphs of rectangular groups, if the subsemigroup generated by C is an orthodox semigroup. Finally, a characterization of vertex-transitive graphs which are Cayley graphs of finite semigroups is concluded.     

Path factors in cubic graphs

Let ? be a set of connected graphs. An ?‐factor of a graph is its spanning subgraph such that each component is isomorphic to one of the members in ?. Let P_k denote the path of order k. Akiyama and Kano have conjectured that every 3‐connected cubic graph of order divisible by 3 has a {P₃}‐factor. Recently, Kaneko gave a necessary and sufficient condition for a graph to have a {P₃, P₄, P₅}‐factor. As a corollary, he proved that every cubic graph has a {P₃, P₄, P₅}‐factor. In this paper, we prove that every 2‐connected cubic graph of order at least six has a {P_k ∣ k ≥ , 6}‐factor, and hence has a {P₃, P₄}‐factor. © 2002 Wiley Periodicals, Inc. J Graph Theory 39: 188–193, 2002; DOI 10.1002/jgt.10022     

Cubic graphs with most automorphisms

We give a sharp bound for the order of the automorphism group of a connected simple cubic graph on a given number of vertices. For each number of vertices we construct a graph, unique in special cases, attaining the bound. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 99–115, 2010     

Bounded-excess flows in cubic graphs

An (r, α)-bounded-excess flow ((r, α)-flow) in an orientation of a graph G = (V, E) is an assignment f : E → [1, r−1], such that for every vertex x ∈ V, $|{\sum }_{e\in E^{+}\left(x\right)}f\left(e\right)-{\sum }_{e\in E^{-}\left(x\right)}f\left(e\right)|\le \alpha$. E⁺(x), respectively E⁻(x), is the set of edges directed from, respectively toward x. Bounded-excess flows suggest a generalization of Circular nowhere-zero flows (cnzf), which can be regarded as (r, 0)-flows. We define (r, α) as Stronger or equivalent to (s, β), if the existence of an (r, α)-flow in a cubic graph always implies the existence of an (s, β)-flow in the same graph. We then study the structure of the bounded-excess flow strength poset. Among other results, we define the Trace of a point in the r − α plane by $tr\left(r,\alpha \right)=\frac{r-2\alpha }{1-\alpha }$ and prove that among points with the same trace the stronger is the one with the smaller α (and larger r). For example, if a cubic graph admits a k-nzf (trace k with α = 0), then it admits an $(r,\frac{k-r}{k-2})$-flow for every r, 2 ≤ r ≤ k. A significant part of the article is devoted to proving the main result: Every cubic graph admits a $(3\frac{1}{2},\frac{1}{2})$-flow, and there exists a graph which does not admit any stronger bounded-excess flow. Notice that $tr(3\frac{1}{2},\frac{1}{2})=5$ so it can be considered a step in the direction of the 5-flow Conjecture. Our result is the best possible for all cubic graphs while the seemingly stronger 5-flow Conjecture relates only to bridgeless graphs. We also show that if the circular-flow number of a cubic graph is strictly less than 5, then it admits a $(3\frac{1}{3},\frac{1}{3})$-flow (trace 4). We conjecture such a flow to exist in every cubic graph with a perfect matching, other than the Petersen graph. This conjecture is a stronger version of the Ban-Linial Conjecture [1]. Our work here strongly relies on the notion of Orientable k-weak bisections, a certain type of k-weak bisections. k-Weak bisections are defined and studied by L. Esperet, G. Mazzuoccolo, and M. Tarsi [4].     

On distance-regular Cayley graphs of generalized dicyclic groups

Let G be a generalized dicyclic group with identity 1. An inverse closed subset S of $G?\{1\}$ is called minimal if $〈S〉=G$ and there exists some $s\in S$ such that $〈S?\{s,s^{?1}\}〉\ne G$. In this paper, we characterize distance-regular Cayley graphs $\mathrm{Cay}(G,S)$ of G under the condition that S is minimal.