排序方式: 共有19条查询结果,搜索用时 0 毫秒
1.
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 相似文献
2.
3.
Klavdija Kutnar Urban Borštnik Dragan Marušič Dušanka Janežič 《Journal of mathematical chemistry》2009,45(2):372-385
A class of interconnection networks for efficient parallel MD simulations based on hamiltonian cubic symmetric graphs is presented.
The cubic symmetric graphs have many desirable properties as interconnection networks since they have a low degree and are
vertex- and edge-transitive. We present a method for scheduling collective communication routines that are used in parallel
MD and are based on the property that the graphs in question have a Hamilton cycle, that is, a cycle going through all vertices
of the graph. Analyzing these communication routines shows that hamiltonian cubic symmetric graphs of small diameter are good
candidates for a topology that gives rise to an interconnection network with excellent properties, allowing faster communication
and thus speeding up parallel MD simulation. 相似文献
4.
A graph X is said to be distance-balanced if for any edge uv of X, the number of vertices closer to u than to v is equal to the number of vertices closer to v than to u. A graph X is said to be strongly distance-balanced if for any edge uv of X and any integer k, the number of vertices at distance k from u and at distance k+1 from v is equal to the number of vertices at distance k+1 from u and at distance k from v. Exploring the connection between symmetry properties of graphs and the metric property of being (strongly) distance-balanced is the main theme of this article. That a vertex-transitive graph is necessarily strongly distance-balanced and thus also distance-balanced is an easy observation. With only a slight relaxation of the transitivity condition, the situation changes drastically: there are infinite families of semisymmetric graphs (that is, graphs which are edge-transitive, but not vertex-transitive) which are distance-balanced, but there are also infinite families of semisymmetric graphs which are not distance-balanced. Results on the distance-balanced property in product graphs prove helpful in obtaining these constructions. Finally, a complete classification of strongly distance-balanced graphs is given for the following infinite families of generalized Petersen graphs: GP(n,2), GP(5k+1,k), GP(3k±3,k), and GP(2k+2,k). 相似文献
5.
Conder Marston D. E. Hujdurović Ademir Kutnar Klavdija Marušič Dragan 《Journal of Algebraic Combinatorics》2021,53(3):881-895
Journal of Algebraic Combinatorics - Properties of symmetric cubic graphs are described via their rigid cells, which are maximal connected subgraphs fixed pointwise by some involutory automorphism... 相似文献
6.
Symmetry properties of a class of toroidal molecular graphs, arising as covers of certain bipartite cubic Cayley graphs of dihedral groups, are studied. Although these symmetries make all vertices and all edges indistinguishable, they imply intrinsic chirality. 相似文献
7.
8.
Edward Dobson Ademir Hujdurović Klavdija Kutnar Joy Morris 《Journal of Algebraic Combinatorics》2017,45(2):407-422
An automorphism \(\alpha \) of a Cayley graph \(\mathrm{Cay}(G,S)\) of a group G with connection set S is color-preserving if \(\alpha (g,gs) = (h,hs)\) or \((h,hs^{-1})\) for every edge \((g,gs)\in E(\mathrm{Cay}(G,S))\). If every color-preserving automorphism of \(\mathrm{Cay}(G,S)\) is also affine, then \(\mathrm{Cay}(G,S)\) is a Cayley color automorphism (CCA) graph. If every Cayley graph \(\mathrm{Cay}(G,S)\) is a CCA graph, then G is a CCA group. Hujdurovi? et al. have shown that every non-CCA group G contains a section isomorphic to the non-abelian group \(F_{21}\) of order 21. We first show that there is a unique non-CCA Cayley graph \(\Gamma \) of \(F_{21}\). We then show that if \(\mathrm{Cay}(G,S)\) is a non-CCA graph of a group G of odd square-free order, then \(G = H\times F_{21}\) for some CCA group H, and \(\mathrm{Cay}(G,S) = \mathrm{Cay}(H,T)\mathbin {\square }\Gamma \). 相似文献
9.
It is shown that every connected vertex-transitive graph of order 6p, where p is a prime, contains a Hamilton path. Moreover, it is shown that, except for the truncation of the Petersen graph, every connected vertex-transitive graph of order 6p which is not genuinely imprimitive contains a Hamilton cycle. 相似文献
10.
The Anti-Kekulé number of a connected graph G is the smallest number of edges that have to be removed from G in such way that G remains connected but it has no Kekulé structures. In this paper it is proved that the Anti-Kekulé number of all fullerenes
is either 3 or 4 and that for each leapfrog fullerene the Anti-Kekulé number can be established by observing finite number
of cases not depending on the size of the fullerene. 相似文献