共查询到20条相似文献,搜索用时 15 毫秒
1.
It is shown that every connected vertex and edge transitive graph has a normal multicover that is a connected normal edge transitive Cayley graph. Moreover, every chiral or regular map has a normal cover that is a balanced chiral or regular Cayley map, respectively. As an application, a new family of half-transitive graphs is constructed as 2-fold covers of a family of 2-arc transitive graphs admitting Suzuki groups. 相似文献
2.
《Discrete Mathematics》2004,280(1-3):133-148
An infinite family of cubic edge- but not vertex-transitive graphs is constructed. The graphs are obtained as regular
-covers of K3,3 where n=p1e1p2e2pkek where pi are distinct primes congruent to 1 modulo 3, and ei1. Moreover, it is proved that the Gray graph (of order 54) is the smallest cubic edge- but not vertex-transitive graph. 相似文献
3.
4.
5.
A factorisation of a complete graph K
n
is a partition of its edges with each part corresponding to a spanning subgraph (not necessarily connected), called a factor.
A factorisation is called homogeneous if there are subgroups M<G≤S
n
such that M is vertex-transitive and fixes each factor setwise, and G permutes the factors transitively. We classify the homogeneous factorisations of K
n
for which there are such subgroups G,M with M transitive on the edges of a factor as well as the vertices. We give infinitely many new examples.
This paper forms part of an Australian Research Council Discovery Grant project, and was a major part of the PhD project of
the second author. 相似文献
6.
Kim A.S. Factor 《Discrete Mathematics》2008,308(1):34-43
A domination graph of a digraph D, dom(D), is created using the vertex set of D and edge {u,v}∈E[dom(D)] whenever (u,z)∈A(D) or (v,z)∈A(D) for every other vertex z∈V(D). The underlying graph of a digraph D, UG(D), is the graph for which D is a biorientation. We completely characterize digraphs whose underlying graphs are identical to their domination graphs, UG(D)=dom(D). The maximum and minimum number of single arcs in these digraphs, and their characteristics, is given. 相似文献
7.
This paper deals with the Cayley graph , where the generating set consists of all block transpositions. A motivation for the study of these particular Cayley graphs comes from current research in Bioinformatics. As the main result, we prove that is the product of the left translation group and a dihedral group of order . The proof uses several properties of the subgraph of induced by the set . In particular, is a -regular graph whose automorphism group is
has as many as maximal cliques of size , and its subgraph whose vertices are those in these cliques is a 3-regular, Hamiltonian, and vertex-transitive graph. A relation of the unique cyclic subgroup of of order with regular Cayley maps on is also discussed. It is shown that the product of the left translation group and the latter group can be obtained as the automorphism group of a non--balanced regular Cayley map on . 相似文献
8.
In this paper, we describe the generation of all nonorientable triangular embeddings of the complete graphs K12 and K13. (The 59 nonisomorphic orientable triangular embeddings of K12 were found in 1996 by Altshuler, Bokowski, and Schuchert, and K13 has no orientable triangular embeddings.) There are 182,200 nonisomorphic nonorientable triangular embeddings for K12, and 243,088,286 for K13. Triangular embeddings of complete graphs are also known as neighborly maps and are a type of twofold triple system. We also use methods of Wilson to provide an upper bound on the number of simple twofold triple systems of order n, and thereby on the number of triangular embeddings of Kn. We mention an application of our results to flexibility of embedded graphs. © 2005 Wiley Periodicals, Inc. J Combin Designs 相似文献
9.
Cai Heng Li 《Transactions of the American Mathematical Society》2006,358(10):4605-4635
This paper aims to develop a theory for studying Cayley graphs, especially for those with a high degree of symmetry. The theory consists of analysing several types of basic Cayley graphs (normal, bi-normal, and core-free), and analysing several operations of Cayley graphs (core quotient, normal quotient, and imprimitive quotient). It provides methods for constructing and characterising various combinatorial objects, such as half-transitive graphs, (orientable and non-orientable) regular Cayley maps, vertex-transitive non-Cayley graphs, and permutation groups containing certain regular subgroups.
In particular, a characterisation is given of locally primitive holomorph Cayley graphs, and a classification is given of rotary Cayley maps of simple groups. Also a complete classification is given of primitive permutation groups that contain a regular dihedral subgroup.
10.
11.
Adriana Hansberg 《Discrete Mathematics》2008,308(11):2277-2281
Let G be a simple graph, and let p be a positive integer. A subset D⊆V(G) is a p-dominating set of the graph G, if every vertex v∈V(G)-D is adjacent to at least p vertices in D. The p-domination numberγp(G) is the minimum cardinality among the p-dominating sets of G. Note that the 1-domination number γ1(G) is the usual domination numberγ(G). This definition immediately leads to the inequality γ(G)?γ2(G).In this paper we present some sufficient as well as some necessary conditions for graphs G with the property that γ2(G)=γ(G). In particular, we characterize all cactus graphs H with γ2(H)=γ(H). 相似文献
12.
13.
Jie-hua MAI~ Tai-xiang SUN~ 《中国科学A辑(英文版)》2007,50(12):1818-1824
Let G be a graph and f:G→G be continuous.Denote by R(f) andΩ(f) the set of recurrent points and the set of non-wandering points of f respectively.LetΩ_0(f) = G andΩ_n(f)=Ω(f|_(Ω_(n-1)(f))) for all n∈N.The minimal m∈NU {∞} such thatΩ_m(f)=Ω_(m 1)(f) is called the depth of f.In this paper,we show thatΩ_2 (f)=(?) and the depth of f is at most 2.Furthermore,we obtain some properties of non-wandering points of f. 相似文献
14.
Given a group of order at most six, we characterize the graphs that have -antivoltages and also determine the list of minor-minimal graphs that have no -antivoltage. Our characterizations yield polynomial-time recognition algorithms for such graphs. 相似文献
15.
16.
图的超常边连通度是图的边连通度概念的推广,对于n阶点可迁或正则边可迁的简单连通图来说,它的h阶超常边连通度λ_h一定存在(1≤h≤n/2)。本文证明了:当d_-正则的n_-阶点可迁简单连通图满足n≥6,d≥4且围长g≥5时,或d_-正则的n_-阶边可迁简单连通图满足n≥6,d≥4且围长g≥4时,对于任何的h:1≤h≤min{g-1,n/2},λ_h达到其最大可能值,即λ_h=hd-2(h-1)。 相似文献
17.
The structure of equicontinuous maps 总被引:1,自引:0,他引:1
Jie-Hua Mai 《Transactions of the American Mathematical Society》2003,355(10):4125-4136
Let be a metric space, and be a continuous map. In this paper we prove that if is compact, and for all , then is equicontinuous if and only if there exist a pointwise recurrent isometric homeomorphism and a non-expanding map that is pointwise convergent to a fixed point such that is uniformly conjugate to a subsystem of the product map . In addition, we give some still simpler necessary and sufficient conditions of equicontinuous graph maps.
18.
Marston Conder Aleksander Malnič Dragan Marušič Primž Potočnik 《Journal of Algebraic Combinatorics》2006,23(3):255-294
A list is given of all semisymmetric (edge- but not vertex-transitive) connected finite cubic graphs of order up to 768. This
list was determined by the authors using Goldschmidt's classification of finite primitive amalgams of index (3,3), and a computer
algorithm for finding all normal subgroups of up to a given index in a finitely-presented group. The list includes several
previously undiscovered graphs. For each graph in the list, a significant amount of information is provided, including its
girth and diameter, the order of its automorphism group, the order and structure of a minimal edge-transitive group of automorphisms,
its Goldschmidt type, stabiliser partitions, and other details about its quotients and covers. A summary of all known infinite
families of semisymmetric cubic graphs is also given, together with explicit rules for their construction, and members of
the list are identified with these. The special case of those graphs having K1,3 as a normal quotient is investigated in detail.
Supported in part by N.Z. Marsden Fund (grant no. UOA 124) and N.Z. Centres of Research Excellence Fund (grant no. UOA 201)
Supported in part by “Ministrstvo za šolstvo, znanost in šport Slovenije”, research program no. 101-506.
Supported in part by research projects no. Z1-4186-0101 and no. Z1-3124-0101. The fourth author would like to thank the University
of Auckland for hospitality during his visit there in 2003. 相似文献
19.
Bo-Jr Li 《Discrete Mathematics》2008,308(11):2075-2079
A clique in a graph G is a complete subgraph of G. A clique covering (partition) of G is a collection C of cliques such that each edge of G occurs in at least (exactly) one clique in C. The clique covering (partition) numbercc(G) (cp(G)) of G is the minimum size of a clique covering (partition) of G. This paper gives alternative proofs, using a unified approach, for the results on the clique covering (partition) numbers of line graphs obtained by McGuinness and Rees [On the number of distinct minimal clique partitions and clique covers of a line graph, Discrete Math. 83 (1990) 49-62]. We also employ the proof techniques to give an alternative proof for the De Brujin-Erd?s Theorem. 相似文献
20.
A regular Cayley map for a finite group A is an orientable map whose orientation-preserving automorphism group G acts regularly on the directed edge set and has a subgroup isomorphic to A that acts regularly on the vertex set. This paper considers the problem of determining which abelian groups have regular
Cayley maps. The analysis is purely algebraic, involving the structure of the canonical form for A. The case when A is normal in G involves the relationship between the rank of A and the exponent of the automorphism group of A, and the general case uses Ito's theorem to analyze the factorization G = AY, where Y is the (cyclic) stabilizer of a vertex.
Supported in part by the N.Z. Marsden Fund (grant no. UOA0124). 相似文献