共查询到20条相似文献,搜索用时 31 毫秒
1.
K. V. Kostousov 《Siberian Mathematical Journal》2007,48(3):489-499
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. 相似文献
2.
A two-dimensional framework (G,p) is
a graph G = (V,E) together with a map p: V → ℝ2. We view (G,p) as a straight line realization of G in ℝ2. 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]. 相似文献
3.
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 相似文献
4.
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. 相似文献
5.
A. Gamburd S. Hoory M. Shahshahani A. Shalev B. Virág 《Random Structures and Algorithms》2009,35(1):100-117
We prove that random d‐regular Cayley graphs of the symmetric group asymptotically almost surely have girth at least (logd‐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 相似文献
6.
A characterization is given of the class of edge-transitive Cayley graphs of Frobenius groups
\mathbbZpd:\mathbbZq\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. 相似文献
7.
8.
Edward Howorka 《Journal of Graph Theory》1981,5(3):323-331
A connected graph G is ptolemaic provided that for each four vertices Ui, 1 ≤ i ≤ 4, of G, the six distances dii = dG (Ui, Ui), i ≠ j satisfy the inequality d12d34 ≤ d13d24 + d14d23 (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. 相似文献
9.
Peter Frankl 《Combinatorica》1987,7(1):67-70
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. 相似文献
10.
Xingui Fang 《Journal of Combinatorial Theory, Series A》2011,118(3):1039-1051
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. 相似文献
11.
Jin Ho KWAK Ju Mok OH 《数学学报(英文版)》2006,22(5):1305-1320
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. 相似文献
12.
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, p2 or p3 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 2p2 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 4p2, p>7 a prime, is a generalized Petersen graph. In addition, cubic non‐Cayley vertex‐transitive graphs of order 2pk, where p>7 is a prime and k?p, are characterized. © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 77–95, 2012 相似文献
13.
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. 相似文献
14.
Cai Heng Li 《Graphs and Combinatorics》1998,14(1):37-44
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. 相似文献
15.
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. 相似文献
16.
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. 相似文献
17.
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. 相似文献
18.
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 C6‐free graphs with Ω(n4/3 edges, C10‐free graphs with Ω(n6/5) edges, and Θ(7,7,7)‐free graphs with Ω(n8/7) edges. Each of these bounds is sharp in order of magnitude. © 2005 Wiley Periodicals, Inc. J Graph Theory 49: 1–10, 2005 相似文献
19.
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. 相似文献
20.
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 p2 for some prime p, then there is a vertex-transitive graph on n vertices that is not a Cayley graph unless n is p2, p3, or 12. © 1996 John Wiley & Sons, Inc. 相似文献