共查询到20条相似文献,搜索用时 15 毫秒
1.
Given a finite abelian group G, consider the complete graph on the set of all elements of G. Find a Hamiltonian cycle in this graph and for each pair of consecutive vertices along the cycle compute their sum. What are the smallest and the largest possible number of distinct sums that can emerge in this way? What is the expected number of distinct sums if the cycle is chosen randomly? How the answers change if an orientation is given to the cycle and differences (instead of sums) are computed? We give complete solutions to some of these problems and establish reasonably sharp estimates for the rest. 相似文献
2.
Let D be the circulant digraph with n vertices and connection set {2,3,c}. (Assume D is loopless and has outdegree 3.) Work of S. C. Locke and D. Witte implies that if n is a multiple of 6, c{(n/2)+2,(n/2)+3}, and c is even, then D does not have a hamiltonian cycle. For all other cases, we construct a hamiltonian cycle in D. 相似文献
3.
4.
5.
关于Abel群上Cayley图的Hamilton圈分解 总被引:3,自引:0,他引:3
设G(F,T∩T^-1)是有限Abel群F上的Cayley图,T∩T^-1只含2阶元,此文证明了当T是F的极小生成元集时,若d(G)=2k,则G是k个边不相交的Hamilton圈的并,若d(G)=2k+1,则G是k个边不相交的Hamilton圈与一个1-因子的并。 相似文献
6.
WangShiying ZhangYuren LiuYan 《高校应用数学学报(英文版)》1999,14(4):492-494
Abstract. Let Sn be the symmetric group 相似文献
7.
《Discrete Mathematics》2019,342(4):1186-1190
8.
A graph G of order at least 2n+2 is said to be n‐extendable if G has a perfect matching and every set of n independent edges extends to a perfect matching in G. We prove that every pair of nonadjacent vertices x and y in a connected n‐extendable graph of order p satisfy degG x+degG y ≥ p ? n ? 1, then either G is hamiltonian or G is isomorphic to one of two exceptional graphs. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 75–82, 2002 相似文献
9.
4度Cayley图的Hamilton圈分解的新方法与理论证明 总被引:2,自引:0,他引:2
王艳芳 《纯粹数学与应用数学》2010,26(3):380-386
给出了"Hamilton圈侧枝循环"等四个定理.它揭示了Abel群上4度Cayley图的Hamilton圈分解的特点及规律.同时,提出了Hamilton圈上"单向通道"的"离合"理论.在此基础上给出了Abel群上4度Cayley图的Hamilton圈分解的新方法-"离合法",此方法具有简明、快捷、分解方案多的特点.另外,Hamilton圈"单向通道"的"离合"理论还为解决6度Cayley图的Hamilton圈分解奠定了理论基础. 相似文献
10.
The existence problem for a Hamiltonian cycle decomposition of (the so called cocktail party graph) with a dihedral automorphism group acting sharply transitively on the vertices is completely solved. Such Hamiltonian cycle decompositions exist for all even n while, for n odd, they exist if and only if the following conditions hold: (i) n is not a prime power; (ii) there is a suitable ? such that (mod 2?) for all prime factors p of n and the number of the prime factors (counted with their respective multiplicities) such that (mod ) is even. Thus in particular one has a dihedral Hamiltonian cycle decomposition of the cocktail party graph on 8k vertices for all k, while it is known that no such cyclic Hamiltonian cycle decomposition exists. Finally, this paper touches on a recently introduced symmetry requirement by proving that there exists a dihedral and symmetric Hamiltonian cycle system of if and only if (mod 4). 相似文献
11.
12.
MENGJIXIANG HUANGQIONGXIANG 《高校应用数学学报(英文版)》1997,12(3):259-266
In this paper, Hamiltonian cycles and decompositions of Cayley digraphs are investigat-ed. Sufficient conditions are given for these two problems respectively. Furthermore, the conditions are also necesaary for 2-regular Cayley disraphs, In addition, some known results about theCartesian products of two directed cycles are also deduced. 相似文献
13.
Let G be an (m+2)-graph on n vertices, and F be a linear forest in G with |E(F)|=m and ω1(F)=s, where ω1(F) is the number of components of order one in F. We denote by σ3(G) the minimum value of the degree sum of three vertices which are pairwise non-adjacent. In this paper, we give several σ3 conditions for a dominating cycle or a hamiltonian cycle passing through a linear forest. We first prove that if σ3(G)≥n+2m+2+max{s−3,0}, then every longest cycle passing through F is dominating. Using this result, we prove that if σ3(G)≥n+κ(G)+2m−1 then G contains a hamiltonian cycle passing through F. As a corollary, we obtain a result that if G is a 3-connected graph and σ3(G)≥n+κ(G)+2, then G is hamiltonian-connected. 相似文献
14.
15.
16.
K. V. Kostousov 《Algebra and Logic》2008,47(2):118-124
We point out a countable set of pairwise nonisomorphic Cayley graphs of the group ℤ4 that are limit for finite minimal vertex-primitive graphs admitting a vertex-primitive automorphism group containing a regular
Abelian normal subgroup.
Supported by RFBR grant No. 06-01-00378.
__________
Translated from Algebra i Logika, Vol. 47, No. 2, pp. 203–214, March–April, 2008. 相似文献
17.
In this article current directions in solving Lovász’s problem about the existence of Hamilton cycles and paths in connected vertex-transitive graphs are given. 相似文献
18.
We study a family of digraphs (directed graphs) that generalises the class of Cayley digraphs. For nonempty subsets of a group G, we define the two‐sided group digraph to have vertex set G, and an arc from x to y if and only if for some and . In common with Cayley graphs and digraphs, two‐sided group digraphs may be useful to model networks as the same routing and communication scheme can be implemented at each vertex. We determine necessary and sufficient conditions on L and R under which may be viewed as a simple graph of valency , and we call such graphs two‐sided group graphs. We also give sufficient conditions for two‐sided group digraphs to be connected, vertex‐transitive, or Cayley graphs. Several open problems are posed. Many examples are given, including one on 12 vertices with connected components of sizes 4 and 8. 相似文献
19.
Michael Z. Spivey 《Discrete Mathematics》2007,307(24):3130-3146
We present a new approach to evaluating combinatorial sums by using finite differences. Let and be sequences with the property that Δbk=ak for k?0. Let , and let . We derive expressions for gn in terms of hn and for hn in terms of gn. We then extend our approach to handle binomial sums of the form , , and , as well as sums involving unsigned and signed Stirling numbers of the first kind, and . For each type of sum we illustrate our methods by deriving an expression for the power sum, with ak=km, and the harmonic number sum, with ak=Hk=1+1/2+?+1/k. Then we generalize our approach to a class of numbers satisfying a particular type of recurrence relation. This class includes the binomial coefficients and the unsigned Stirling numbers of the first kind. 相似文献
20.
Bubble-Sort图和Modified Bubble-Sort图是两类特殊的Cayley图,由于其在网络构建中的应用而受到广泛关注.本文完全确定了这两类图的自同构群. 相似文献