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
Academic Journal
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

Read the Article

Courtesy of VIRGINIA BEACH PUBLIC LIBRARY AND SYSTEM

Sorry, but this item is not currently available from your library.

Try another library?
Sign out of this library

Other Topics