The Cayley graphs of ℤ<Superscript>d</Superscript> and the limits of vertex-primitive graphs of <Emphasis Type="Italic">HA</Emphasis>-type

We study the limits of the finite graphs that admit some vertex-primitive group of automorphisms with a regular abelian normal subgroup. It was shown in [1] that these limits are Cayley graphs of the groups ?^d. In this article we prove that for each d > 1 the set of Cayley graphs of ?^d presenting the limits of finite graphs with vertex-primitive and edge-transitive groups of automorphisms is countable (in fact, we explicitly give countable subsets of these limit graphs). In addition, for d < 4 we list all Cayley graphs of ?^d that are limits of minimal vertex-primitive graphs. The proofs rely on a connection of the automorphism groups of Cayley graphs of ?^d with crystallographic groups.     

Globally Linked Pairs of Vertices in Equivalent Realizations of Graphs

A two-dimensional framework (G,p) is a graph G = (V,E) together with a map p: V → ℝ². We view (G,p) as a straight line realization of G in ℝ². Two realizations of G are equivalent if the corresponding edges in the two frameworks have the same length. A pair of vertices {u,v} is globally linked in G if %and for all equivalent frameworks (G,q), the distance between the points corresponding to u and v is the same in all pairs of equivalent generic realizations of G. The graph G is globally rigid if all of its pairs of vertices are globally linked. We extend the characterization of globally rigid graphs given by the first two authors [13] by characterizing globally linked pairs in M-connected graphs, an important family of rigid graphs. As a byproduct we simplify the proof of a result of Connelly [6] which is a key step in the characterization of globally rigid graphs. We also determine the number of distinct realizations of an M-connected graph, each of which is equivalent to a given generic realization. Bounds on this number for minimally rigid graphs were obtained by Borcea and Streinu in [3].     

Large Cayley graphs and vertex‐transitive non‐Cayley graphs of given degree and diameter

For any d?5 and k?3 we construct a family of Cayley graphs of degree d, diameter k, and order at least k((d?3)/3)^k. By comparison with other available results in this area we show that our family gives the largest currently known Cayley graphs for a wide range of sufficiently large degrees and diameters. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 87–98, 2010     

Pooling spaces associated with finite geometry

Motivated by the works of Ngo and Du [H. Ngo, D. Du, A survey on combinatorial group testing algorithms with applications to DNA library screening, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 55 (2000) 171–182], the notion of pooling spaces was introduced [T. Huang, C. Weng, Pooling spaces and non-adaptive pooling designs, Discrete Mathematics 282 (2004) 163–169] for a systematic way of constructing pooling designs; note that geometric lattices are among pooling spaces. This paper attempts to draw possible connections from finite geometry and distance regular graphs to pooling spaces: including the projective spaces, the affine spaces, the attenuated spaces, and a few families of geometric lattices associated with the orbits of subspaces under finite classical groups, and associated with d-bounded distance-regular graphs.     

On the girth of random Cayley graphs

We prove that random d‐regular Cayley graphs of the symmetric group asymptotically almost surely have girth at least (log_d‐1|G|)^1/2/2 and that random d‐regular Cayley graphs of simple algebraic groups over ??_q asymptotically almost surely have girth at least log _d‐1|G|/dim(G). For the symmetric p‐groups the girth is between loglog |G| and (log |G|)^α with α < 1. Several conjectures and open questions are presented. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Classifying a family of edge-transitive metacirculant graphs

A characterization is given of the class of edge-transitive Cayley graphs of Frobenius groups \mathbbZ_p^d:\mathbbZ_q\mathbb{Z}_{p^{d}}{:}\mathbb{Z}_{q} with p,q odd prime, of valency coprime to p. This characterization is then used to study an isomorphism problem regarding Cayley graphs, and to construct new families of half-arc-transitive graphs.     

A characterization of ptolemaic graphs

A connected graph G is ptolemaic provided that for each four vertices U_i, 1 ≤ i ≤ 4, of G, the six distances d_ii = d_G (U_i, U_i), i ≠ j satisfy the inequality d₁₂d₃₄ ≤ d₁₃d₂₄ + d₁₄d₂₃ (shown by Ptolemy to hold in Euclidean spaces). Ptolemaic graphs were first investigated by Chartrand and Kay, who showed that weakly geodetic ptolemaic graphs are precisely Husimi trees (in particular, trees are ptolemaic). in the present paper several characterizations of ptolemaic graphs are given. It is shown, for example, that a connected graph G is ptolemaic if and only iffor each nondisjoint cliques P, Q of G, their intersection is a cutset of G which separates P-Q and Q-P. An operation is exhibited which generates all finite ptolemaic graphs from complete graphs.     

On a pursuit game on cayley graphs

The game cops and robbers is considered on Cayley graphs of abelian groups. It is proved that if the graph has degreed, then [(d+1)/2] cops are sufficient to catch one robber. This bound is often best possible.     

On locally primitive Cayley graphs of finite simple groups

In this paper we investigate locally primitive Cayley graphs of finite nonabelian simple groups. First, we prove that, for any valency d for which the Weiss conjecture holds (for example, d?20 or d is a prime number by Conder, Li and Praeger (2000) [1]), there exists a finite list of groups such that if G is a finite nonabelian simple group not in this list, then every locally primitive Cayley graph of valency d on G is normal. Next we construct an infinite family of p-valent non-normal locally primitive Cayley graph of the alternating group for all prime p?5. Finally, we consider locally primitive Cayley graphs of finite simple groups with valency 5 and determine all possible candidates of finite nonabelian simple groups G such that the Cayley graph Cay(G,S) might be non-normal.     

One-regular Normal Cayley Graphs on Dihedral Groups of Valency 4 or 6 with Cyclic Vertex Stabilizer

A graph G is one-regular if its automorphism group Aut（G） acts transitively and semiregularly on the arc set. A Cayley graph Cay（Г, S） is normal if Г is a normal subgroup of the full automorphism group of Cay（Г, S）. Xu, M. Y., Xu, J. （Southeast Asian Bulletin of Math., 25, 355-363 （2001）） classified one-regular Cayley graphs of valency at most 4 on finite abelian groups. Marusic, D., Pisanski, T. （Croat. Chemica Acta, 73, 969-981 （2000）） classified cubic one-regular Cayley graphs on a dihedral group, and all of such graphs turn out to be normal. In this paper, we classify the 4-valent one-regular normal Cayley graphs G on a dihedral group whose vertex stabilizers in Aut（G） are cyclic. A classification of the same kind of graphs of valency 6 is also discussed.     

On cubic non‐Cayley vertex‐transitive graphs

In 1983, the second author [D. Maru?i?, Ars Combinatoria 16B (1983), 297–302] asked for which positive integers n there exists a non‐Cayley vertex‐transitive graph on n vertices. (The term non‐Cayley numbers has later been given to such integers.) Motivated by this problem, Feng [Discrete Math 248 (2002), 265–269] asked to determine the smallest valency ?(n) among valencies of non‐Cayley vertex‐transitive graphs of order n. As cycles are clearly Cayley graphs, ?(n)?3 for any non‐Cayley number n. In this paper a goal is set to determine those non‐Cayley numbers n for which ?(n) = 3, and among the latter to determine those for which the generalized Petersen graphs are the only non‐Cayley vertex‐transitive graphs of order n. It is known that for a prime p every vertex‐transitive graph of order p, p² or p³ is a Cayley graph, and that, with the exception of the Coxeter graph, every cubic non‐Cayley vertex‐transitive graph of order 2p, 4p or 2p² is a generalized Petersen graph. In this paper the next natural step is taken by proving that every cubic non‐Cayley vertex‐transitive graph of order 4p², p>7 a prime, is a generalized Petersen graph. In addition, cubic non‐Cayley vertex‐transitive graphs of order 2p^k, where p>7 is a prime and k?p, are characterized. © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 77–95, 2012     

The topological theory of current graphs

W. Gustin's introduction of combinatorial current graphs as a device for obtaining orientable imbeddings of Cayley “color” graphs was fundamental to the solution of the Heawood map-coloring problem by G. Ringel, J. W. T. Youngs, C. M. Terry, and L. R. Welch. The topological current graphs of this paper lead to a construction that generalizes the method of Gustin and its augmentation to “vortex” graphs by Youngs, extending the scope of current graph theory from Cayley graphs alone to the much larger class of graphs that are covering spaces.     

Isomorphisms of Connected Cayley Digraphs

 Let G be a finite group and let Cay() be a Cayley graph of G. The graph Cay() is called a CI-graph of G if, for any for some Aut(G) only when CayCay(). In this paper, we study the isomorphism problem of connected Cayley graphs: to determine the groups G (or the types of Cayley graphs for a given group G) for which all connected Cayley graphs for G are CI-graphs.     

Generalized Cayley graphs of semigroups II

Following Zhu (Semigroup Forum, 2011, doi:), we study generalized Cayley graphs of semigroups. The Cayley D-saturated property, a particular combinatorial property, of generalized Cayley graphs of semigroups is considered and most of the results in Kelarev and Quinn (Semigroup Forum 66:89–96, 2003), Yang and Gao (Semigroup Forum 80:174–180, 2010) are extended. In addition, for some basic graphs and their complete fission graphs, we describe all semigroups whose universal Cayley graphs are isomorphic to these graphs.     

On the Wiener Index of Graphs

The Wiener index of a graph G is defined as W(G)=∑ _u,v d _G (u,v), where d _G (u,v) is the distance between u and v in G and the sum goes over all the pairs of vertices. In this paper, we first present the 6 graphs with the first to the sixth smallest Wiener index among all graphs with n vertices and k cut edges and containing a complete subgraph of order n−k; and then we construct a graph with its Wiener index no less than some integer among all graphs with n vertices and k cut edges.     

Conformal Theories–AdS Branes Transform,or One More Face of AdS/CFT

The AdS/CFT transformation relates two nonlinear realizations of (super)conformal groups: their realization in the appropriate field theories in Minkowski space with a Goldstone dilaton field and their realization as (super)isometry groups of AdS (super)spaces. It already exists at the classical level and maps the field variables and space–time coordinates of the given (super)conformal field theory in d-dimensional Minkowski space _d to the variables of a scalar codimension-one (super)brane in AdS _d+1 in a static gauge, the dilaton being mapped onto the transverse AdS brane coordinate. We explain the origin of this coordinate mapping and describe some its implications, in particular, in d=1 models of conformal and superconformal mechanics. We also give a suggestive geometric interpretation of this AdS/CFT transformation in the purely bosonic case in the framework of an extended (2d+1)-dimensional conformal space involving extra coordinates associated with the generators of dilatations and conformal boosts.     

Edge‐decompositions of Kn,n into isomorphic copies of a given tree

We construct an incidence structure using certain points and lines in finite projective spaces. The structural properties of the associated bipartite incidence graphs are analyzed. These n × n bipartite graphs provide constructions of C₆‐free graphs with Ω(n^4/3 edges, C₁₀‐free graphs with Ω(n^6/5) edges, and Θ(7,7,7)‐free graphs with Ω(n^8/7) edges. Each of these bounds is sharp in order of magnitude. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 1–10, 2005     

On the Cayley graphs of completely simple semigroups

In this paper, the Cayley graphs of completely simple semigroups are investigated. The basic structure and properties of this kind of Cayley graph are given, and a condition is given for a Cayley graph of a completely simple semigroup to be a disjoint union of complete graphs. We also describe all pairs (S,A) such that S is a completely simple semigroup, A⊆S, and Cay (S,A) is a strongly connected bipartite Cayley graph.     

Vertex-transitive graphs that are not Cayley graphs. II

The Petersen graph on 10 vertices is the smallest example of a vertex-transitive graph that is not a Cayley graph. In 1983, D. Marus˘ic˘ asked, “For what values of n does there exist such a graph on n vertices?” We give several new constructions of families of vertex-transitive graphs that are not Cayley graphs and complete the proof that, if n is divisible by p² for some prime p, then there is a vertex-transitive graph on n vertices that is not a Cayley graph unless n is p², p³, or 12. © 1996 John Wiley & Sons, Inc.