TITLE

Symmetric Hamilton Cycle Decompositions of Complete Graphs Plus a 1-Factor

AUTHOR(S)
Akwu, Abolape D.; Ajayi, Deborah O. A.
PUB. DATE
September 2013
SOURCE
International Journal of Mathematical Combinatorics;Sep2013, Vol. 3, p91
SOURCE TYPE
DOC. TYPE
Article
ABSTRACT
Let n â‰¥ 2 be an integer. The complete graph Kn with 1-factor I added has a decomposition into Hamilton cycles if and only if n is even. We show that Kn + I has a decomposition into Hamilton cycles which are symmetric with respect to the 1-factor I added. We also show that the complete bipartite graph Kn,n plus a 1-factor has a symmetric Hamilton decomposition, where n is odd.
ACCESSION #
91942096

Related Articles

• Graphs Containing Every 2-Factor. Kostochka, Alexandr; Yu, Gexin // Graphs & Combinatorics;Sep2012, Vol. 28 Issue 5, p687

For a graph G, let $${\sigma_2(G)=\min\{d(u)+d(v):uv\notin E(G)\}}$$ . We prove that every n-vertex graph G with Ïƒ( G) â‰¥ 4 n/3 âˆ’ 1 contains each 2-regular n-vertex graph. This extends a theorem due to Aigner and Brandt and to Alon and Fisher.

• Hamilton Cycle Rich 2-Factorization of Complete Equipartite Graphs-II. Sangeetha, R.; Muthusamy, A. // Graphs & Combinatorics;Nov2012, Vol. 28 Issue 6, p877

For any given two 2-factors G and H of a complete p-partite graph K( m, p), with m vertices in each partite set, we prove the existence of a 2-factorization of K( m, p), in which one 2-factor is isomorphic to G, another 2-factor is isomorphic to H and the remaining 2-factors are hamilton cycles....

• Cycle Lengths of Hamiltonian $$P_\ell$$ -free Graphs. Meierling, Dirk; Rautenbach, Dieter // Graphs & Combinatorics;Nov2015, Vol. 31 Issue 6, p2335

For an integer $$\ell$$ at least three, we prove that every Hamiltonian $$P_\ell$$ -free graph $$G$$ on $$n>\ell$$ vertices has cycles of at least $$\frac{2}{\ell }n-1$$ different lengths. For small values of $$\ell$$ , we can improve the bound as follows. If $$4\le \ell \le 7$$ , then $$G$$...

• On the Extremal Number of Edges in Hamiltonian Graphs. TUNG-YANG HO; CHENG-KUAN LIN; TAN, JIMMY J. M.; HSU, D. FRANK; LIH-HSING HSU // Journal of Information Science & Engineering;Sep2011, Vol. 27 Issue 5, p1659

Assume that n and Î´ are positive integers with 2 â‰¤ Î´ < n. Let h(n, Î´) be the minimum number of edges required to guarantee an n-vertex graph with minimum degree Î´(G) â‰¥ Î´ to be hamiltonian, i.e., any n-vertex graph G with Î´(G) â‰¥ Î´ is hamiltonian if |E(G)|...

• Large Sets of Hamilton Cycle and Path Decompositions of Complete Bipartite Graphs. Zhao, Hongtao; Kang, Qingde // Graphs & Combinatorics;Jan2013, Vol. 29 Issue 1, p145

In this paper, we determine the existence spectrums for large sets of Hamilton cycle and path (resp. directed Hamilton cycle and path) decompositions of Î»K (resp. $${\lambda K^{*}_{m,n}}$$).

• DECOMPOSITIONS OF A COMPLETE MULTIDIGRAPH INTO ALMOST ARBITRARY PATHS. MESZKA, MARIUSZ; SKUPIÉ, ZDZISŁAW // Discussiones Mathematicae: Graph Theory;2012, Vol. 32 Issue 2, p357

For n = 4, the complete n-vertex multidigraph with arc multiplicity ? is proved to have a decomposition into directed paths of arbitrarily prescribed lengths = n-1 and different from n-2, unless n = 5, ? = 1, and all lengths are to be n-1 = 4. For ? = 1, a more general decomposition exists;...

• Decomposing Various Graphs into Short Even-Length Cycles. Horsley, Daniel // Annals of Combinatorics;Sep2012, Vol. 16 Issue 3, p571

We prove that a complete bipartite graph can be decomposed into cycles of arbitrary specified lengths provided that the obvious necessary conditions are satisfied, the length of each cycle is at most the size of the smallest part, and the longest cycle is at most three times as long as the...

• On Orthogonal Double Covers of Complete Bipartite Graphs by an Infinite Certain Graph-Path and Graph-Cycle. El-Shanawany, R. A. // British Journal of Mathematics & Computer Science;2014, Vol. 4 Issue 16, p2320

Let F be a certain graph, the graph F-Path denoted by â„™ d+1(F) path of length d with d + 1 vertices (i.e. Every edge of this path is one-to-one corresponding to an isomorphic to the graph F). In the same manner, we define the graph F-Cycle as â„‚d(F) cycle on d vertices. In this...

• DECOMPOSITIONS OF A COMPLETE MULTIDIGRAPH INTO ALMOST ARBITRARY PATHS. Meszka, Mariusz; Skupień, Zdzisław // Discussiones Mathematicae: Graph Theory;2012, Vol. 32 Issue 3, p357

For n â‰¥ 4, the complete n-vertex multidigraph with arc multiplicity Î» is proved to have a decomposition into directed paths of arbitrarily prescribed lengths â‰¤ n--1 and different from n--2, unless n = 5, Î» = 1, and all lengths are to be n--1 = 4. For Î»= 1, a more general...

Share