排序方式: 共有13条查询结果,搜索用时 328 毫秒
1.
运用基图自同构能被提升的线性准则 ,对满足 :1覆叠变换群 K =Znp,2覆盖图的保簇变换群是点传递的 Petersen图的连通正则覆盖图进行了完全分类 .这种图共有 1 2种类型 . 相似文献
2.
For a positive integer n, does there exist a vertex-transitive graph Γ on n vertices which is not a Cayley graph, or, equivalently, a graph Γ on n vertices such that Aut Γ is transitive on vertices but none of its subgroups are regular on vertices? Previous work (by Alspach and Parsons, Frucht, Graver and Watkins, Marusic and Scapellato, and McKay and the second author) has produced answers to this question if n is prime, or divisible by the square of some prime, or if n is the product of two distinct primes. In this paper we consider the simplest unresolved case for even integers, namely for integers of the form n = 2pq, where 2 < q < p, and p and q are primes. We give a new construction of an infinite family of vertex-transitive graphs on 2pq vertices which are not Cayley graphs in the case where p ≡ 1 (mod q). Further, if p ? 1 (mod q), p ≡ q ≡ 3(mod 4), and if every vertex-transitive graph of order pq is a Cayley graph, then it is shown that, either 2pq = 66, or every vertex-transitive graph of order 2pq admitting a transitive imprimitive group of automorphisms is a Cayley graph. 相似文献
3.
Ademir Hujdurović 《Journal of Graph Theory》2020,95(4):543-564
A clique (resp, independent set) in a graph is strong if it intersects every maximal independent set (resp, every maximal clique). A graph is clique intersect stable set (CIS) if all of its maximal cliques are strong and localizable if it admits a partition of its vertex set into strong cliques. In this paper we prove that a clique in a vertex-transitive graph is strong if and only if for every maximal independent set of . On the basis of this result we prove that a vertex-transitive graph is CIS if and only if it admits a strong clique and a strong independent set. We classify all vertex-transitive graphs of valency at most 4 admitting a strong clique, and give a partial characterization of 5-valent vertex-transitive graphs admitting a strong clique. Our results imply that every vertex-transitive graph of valency at most 5 that admits a strong clique is localizable. We answer an open question by providing an example of a vertex-transitive CIS graph which is not localizable. 相似文献
4.
We study the problem of counting the number of coverings of ad-dimensional rectangular lattice by a specified number of monomers and dimers. This problem arises in several models in statistical physics, and has been widely studied. A classical technique due to Fisher, Kasteleyn, and Temperley solves the problem exactly in two dimensions when the number of monomers is zero (the dimer covering problem), but is not applicable in higher dimensions or in the presence of monomers. This paper presents the first provably polynomial-time approximation algorithms for computing the number of coverings with any specified number of monomers ind-dimensional rectangular lattices with periodic boundaries, for any fixed dimensiond, and in two-dimensional lattices with fixed boundaries. The algorithms are based on Monte Carlo simulation of a suitable Markov chain, and, in constrast to most Monte Carlo algorithms in statistical physics, have rigorously derived performance guarantees that do not rely on any assumptions. The method generalizes to counting coverings of any finite vertex-transitive graph, a class which includes most natural finite lattices with periodic boundary conditions. 相似文献
5.
HUANG Jia XU Jun-ming 《数学季刊》2005,20(4):430-434
P Kulasinghe and S Bettayeb showed that any multiply-twisted hypercube with five or more dimensions is not vertex-transitive. This note shows that any multiply-twisted hypercube with four or less dimensions is vertex-transitive, and that any multiply-twisted hypercube with three or larger dimensions is not edge-transitive. 相似文献
6.
We consider uniform random walks on finite graphs withn nodes. When the hitting times are symmetric, the expected covering time is at least 1/2n logn-O(n log logn) uniformly over all such graphs. We also obtain bounds for the covering times in terms of the eigenvalues of the transition matrix of the Markov chain. For distance-regular graphs, a general lower bound of (n-1) logn is obtained. For hypercubes and binomial coefficient graphs, the limit law of the covering time is obtained as well. 相似文献
7.
8.
Yan-quanFeng JinHoKwak Ming-yaoXu 《应用数学学报(英文版)》2003,19(1):83-86
Let X be a 4-valent connected vertex-transitive graph with odd-prime-power order p^κ(κ≥1) and let A be the full automorphism group of X.In this paper,we prove that the stabilizer Av of a vertex v in A is a 2-group if p≠5,or a {2,3}-group if p=5.Furthermore,if p=5|Av| is not divisible by 3^2.As a result ,we show that any 4-valent connected vertex-transitive graph with odd-prime-power order p^κ(κ≥1) is at most 1-arc-transitive for p≠5 and 2-arc-transitive for p=5. 相似文献
9.
A construction is given for an infinite family {n} of finite vertex-transitive non-Cayley graphs of fixed valency with the property that the order of the vertex-stabilizer in the smallest vertex-transitive group of automorphisms of n is a strictly increasing function ofn . For each n the graph is 4-valent and arc-transitive, with automorphism group a symmetric group of large prime degree
. The construction uses Sierpinski's gasket to produce generating permutations for the vertex-stabilizer (a large 2-group). 相似文献
10.
We characterize the set of planar locally finite Cayley graphs, and give a finite representation of these graphs by a special kind of finite state automata called labeling schemes. As a result, we are able to enumerate and describe all planar locally finite Cayley graphs of a given degree. This analysis allows us to solve the problem of decision of the locally finite planarity for a word-problem-decidable presentation.Mathematics Subject Classiffications (2000). 20F05, 20F10, 20F65, 05C25 相似文献