Embedding an edge-colored K(a^(p);,) into a Hamiltonian decomposition of K(a^(p+r);,)

DOI10.1007/S00373-012-1164-0zbMATH Open1268.05050arXiv1710.05936OpenAlexW2103437676MaRDI QIDQ354461FDOQ354461

Authors: M. A. Bahmanian, C. A. Rodger 

Publication date: 19 July 2013

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Abstract: Let $K(a^{(p)};lambda,mu)$ be a graph with $p$ parts, each part having size $a$, in which the multiplicity of each pair of vertices in the same part (in different parts) is $lambda$ ($mu$, respectively). In this paper we consider the following embedding problem: When can a graph decomposition of $K(a^{(p)};lambda,mu)$ be extended to a Hamiltonian decomposition of $K(a^{(p+r)};lambda,mu)$ for $r>0$? A general result is proved, which is then used to solve the embedding problem for all $rgeqfraclambdamua+fracp-1a-1$. The problem is also solved when $r$ is as small as possible in two different senses, namely when $r=1$ and when $r=fraclambdamua-p+1$.

Full work available at URL: https://arxiv.org/abs/1710.05936

Recommendations

• Embedding an edge-coloring of \(K(n^r;\lambda_1,\lambda_2)\) into a Hamiltonian decomposition of \(K(n^{r+2};\lambda_1,\lambda_2)\)
• Embedding edge‐colorings into 2‐edge‐connected k‐factorizations of k_kn+1
• On the existence and embedding of edge-coloured graph decompositions.
• Coloring the edges ofkm ×km
• The Hamilton-connectivity and the coloring of \(r\)-Klee-graphs
• Publication:3470476
• scientific article; zbMATH DE number 1996256
• From edge colorings to graph decompositions -- results and problems
• Edge colorings of embedded graphs
• Coloring \(d\)-embeddable \(k\)-uniform hypergraphs

zbMATH Keywords

embeddingedge-coloringHamiltonian cyclesHamiltonian decompositionamalgamationsdetachments

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38) Graph designs and isomorphic decomposition (05C51)

Cites Work

• An existence theorem for latin squares
• Amalgamations of almost regular edge-colourings of simple graphs
• Decomposition of a complete multigraph into simple paths: nonbalanced handcuffed designs
• Title not available (Why is that?)
• Cycle decompositions of \(K_n\) and \(K_n-I\)
• Cycle decompositions. III: Complete graphs and fixed length cycles.
• Generalized latin rectangles. II: Embedding
• Amalgamations of connected \(k\)-factorizations.
• Embedding edge‐colorings into 2‐edge‐connected k‐factorizations of k_kn+1
• Hamiltonian decompositions of complete regular s-partite graphs
• Generalized latin rectangles I: Construction and decomposition
• On the decomposition of a graph into stars
• On decomposition of r-partite graphs into edge-disjoint Hamilton circuits
• Group divisible designs with two associate classes: \(n=2\) or \(m=2\)
• 4-cycle group-divisible designs with two associate classes
• Multiply balanced edge colorings of multigraphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Classification and Analysis of Partially Balanced Incomplete Block Designs with Two Associate Classes
• Hamiltonian decompositions of complete graphs

Cited In (3)

• Embedding an edge-coloring of \(K(n^r;\lambda_1,\lambda_2)\) into a Hamiltonian decomposition of \(K(n^{r+2};\lambda_1,\lambda_2)\)
• Connected Baranyai's theorem
• Title not available (Why is that?)

This page was built for publication: Embedding an edge-colored \(K(a^{(p)};\lambda,\mu)\) into a Hamiltonian decomposition of \(K(a^{(p+r)};\lambda,\mu)\)

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q354461)