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

DOI10.1007/S00373-012-1164-0MaRDI QIDQ354461zbMATH OpenOpenAlexFDO

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

Publication date 19 July 2013

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

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

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)

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$.

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

Cites work

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

Cited in

(3)

• Connected Baranyai's theorem
• 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)\)
• scientific article; zbMATH DE number 1996256 (Why is no real title available?)

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)