×

zbMATH — the first resource for mathematics

2-starters, graceful labelings, and a doubling construction for the Oberwolfach problem. (English) Zbl 1258.05099
Summary: Every 1-rotational solution of a classic or twofold Oberwolfach problem (OP) of order n is generated by a suitable 2-factor (starter) of \(K_n\) or \(2K_n\), respectively. It is shown that any starter of a twofold OP of order n gives rise to a starter of a classic OP of order \(2n-1\) (doubling construction). It is also shown that by suitably modifying the starter of a classic OP, one may obtain starters of some other OPs of the same order but having different parameters. The combination of these two constructions leads to lots of new infinite classes of solvable OPs. Still more classes can be obtained with the help of a third construction making use of the possible gracefulness of a graph whose connected components are cycles and at most one path. As one of the many applications, Hilton and Johnson’s bound [A. J. W. Hilton and M. Johnson, J. Lond. Math. Soc., II. Ser. 64, No. 3, 513–522 (2001; Zbl 1012.05135)] \(s\geq 5r-1\) about the solvability of OP\((r,s)\) is improved to \(s\geq \lfloor r/4\rfloor+10\) in the case of \(r\) even.

MSC:
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C78 Graph labelling (graceful graphs, bandwidth, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Abrham, Existence theorems for certain types of graceful valuations of snakes, Congr Numer 93 pp 17– (1993) · Zbl 0801.05024
[2] Abrham, Graceful valuations of 2-regular graphs with two components, Discrete Math 150 pp 3– (1996) · Zbl 0856.05086 · doi:10.1016/0012-365X(95)00171-R
[3] Alspach, The Oberwolfach problem and factors of uniform odd length cycles, J Combin Theory Ser A 52 pp 20– (1989) · Zbl 0684.05035 · doi:10.1016/0097-3165(89)90059-9
[4] Anderson, Sequencings of dicyclic groups, Ars Combin 23 pp 131– (1987) · Zbl 0617.20010
[5] Bonvicini, On 2-factorizations of the complete graph: From the k-pyramidal to the universal property, J Combin Des 17 pp 211– (2009) · Zbl 1171.05039 · doi:10.1002/jcd.20205
[6] Bryant, On the Oberwolfach problem with two similar length cycles, Graphs Combin 17 pp 199– (2001) · Zbl 0978.05058 · doi:10.1007/s003730170033
[7] Bryant, On bipartite 2-factorizations of Kn-I and the Oberwolfach problem, J Graph Theory 68 pp 22– (2011) · Zbl 1230.05231 · doi:10.1002/jgt.20538
[8] Bryant, Cycle decompositions, in: The CRC Handbook of Combinatorial Designs pp 373– (2007)
[9] Bryant, Complete solutions to the Oberwolfach problem for an infinite set of orders, J Combin Theory Ser B 99 pp 904– (2009) · Zbl 1218.05121 · doi:10.1016/j.jctb.2009.03.003
[10] Buratti, Existence of cyclic k-cycle systems of the complete graph, Discrete Math 261 pp 113– (2003) · Zbl 1013.05023 · doi:10.1016/S0012-365X(02)00463-6
[11] Buratti, Cyclic Hamiltonian cycle systems of the complete graph, Discrete Math 279 pp 107– (2004) · Zbl 1034.05030 · doi:10.1016/S0012-365X(03)00267-X
[12] Buratti, Some constructions for cyclic perfect cycle systems, Discrete Math 299 pp 33– (2005) · Zbl 1073.05017 · doi:10.1016/j.disc.2004.07.021
[13] Buratti, 1-rotational k-factorizations of the complete graph and new solutions to the Oberwolfach problem, J Combin Des 16 pp 87– (2008) · Zbl 1135.05058 · doi:10.1002/jcd.20163
[14] Buratti, A non-existence result on cyclic cycle-decompositions of the cocktail party graph, Discrete Math 309 pp 4722– (2009) · Zbl 1214.05114 · doi:10.1016/j.disc.2008.05.042
[15] Buratti, G-invariantly resolvable Steiner 2-designs which are 1-rotational over G, Bulletin Belg Math Soc 5 pp 221– (1998) · Zbl 0922.05007
[16] Buratti, Explicit constructions for 1-rotational Kirkman triple systems, Utilitas Math 59 pp 27– (2001) · Zbl 0987.05022
[17] Deza, Solutions to the Oberwolfach problem for orders 18 to 40, J Combin Math Combin Comput 74 pp 95– (2010) · Zbl 1225.05200
[18] Evans, Complete mappings and sequencings of finite groups, in: The CRC Handbook of Combinatorial Designs pp 345– (2007)
[19] Gallian, A dynamic survey of graph labelings, Electron J Combin 17 (2010)
[20] Gao, On gracefulness of CmP2, J Hebei Teachers College 3 pp 13– (1993)
[21] Gvozdjak, On the Oberwolfach problem for complete multigraphs, Discrete Math 173 pp 61– (1997) · Zbl 0908.05073 · doi:10.1016/S0012-365X(96)00096-9
[22] P. Gvozdjak 2004
[23] Häggkvist, A lemma on cycle decompositions, Ann Discrete Math 27 pp 227– (1985) · Zbl 0577.05045
[24] Hilton, Some results on the Oberwolfach problem, J London Math Soc 64 pp 513– (2001) · Zbl 1012.05135 · doi:10.1112/S0024610701002666
[25] Hoffman, The existence of Ck-factorizations of K2n-F, Discrete Math 97 pp 243– (1991) · Zbl 0756.05089 · doi:10.1016/0012-365X(91)90440-D
[26] Huang, On a variation of the Oberwolfach problem, Discrete Math 27 pp 261– (1979) · Zbl 0435.05038 · doi:10.1016/0012-365X(79)90162-6
[27] Ollis, Some cyclic solutions to the three table Oberwolfach problem, Electron J Combin 12 (2005) · Zbl 1082.05072
[28] Ollis, Sectionable terraces and the (generalised) Oberwolfach problem, Discrete Math 266 pp 399– (2003) · Zbl 1020.05058 · doi:10.1016/S0012-365X(02)00822-1
[29] Ollis, From graceful labellings of paths to cyclic solutions of the Oberwolfach problem, Discrete Math 309 pp 4877– (2009) · Zbl 1211.05154 · doi:10.1016/j.disc.2008.07.023
[30] Ollis, On twizzler, zigzag and graceful terraces, Australas J Combin 51 pp 243– (2011) · Zbl 1233.05061
[31] Rinaldi, Graph products and new solutions to Oberwolfach problems, Electron J Combin 18 pp P52– (2011) · Zbl 1217.05189
[32] Rosa, On certain valuations of the vertices of a graph, Theory of Graphs (International Symposium, Rome, 1966) pp 349– (1967)
[33] Traetta, Some new results on 1-rotational 2-factorizations of the complete graph, J Combin Des 18 pp 237– (2010) · Zbl 1218.05154
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.