Sums and differences along Hamiltonian cycles

DOI10.1016/J.DISC.2009.03.045MaRDI QIDQ5900544zbMATH OpenOpenAlexFDO

Authors Vsevolod F. Lev

Publication date 29 March 2010

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disc.2009.03.045

zbMATH Keywords

addition Cayley graphdirected terraceharmonious grouprainbow differencerainbow sumsequenceable group

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Eulerian and Hamiltonian graphs (05C45) Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Review text

Let \(G\) be a finite abelian group, and let \(\mathcal{C}(G)\) be the set of all hamiltonian cycles in the complete digraph on the vertex set \(G\). Given a cycle \(C\in\mathcal{C}(G)\), label each arc \((g_1,g_2)\in C\) with the sum \(g_1+g_2\in G\), and let \(S(C)\) be the set of labels of all arcs in \(C\). The author studies the value of the maximum and the minimum of the cardinalities \(|S(C)|\) with \(C\in\mathcal{C}(G)\), and the expected value \({\text{E}}(|S(C)|)\) when \(C\in \mathcal{C}(G)\) is chosen randomly. Analogous problems arise when each arc \((g_1,g_2)\) is labeled with the difference \(g_2-g_1\). The author finds the exact value or establishes tight bounds for these six quantities.

Recommendations

• Sums and differences along Hamiltonian cycles
• scientific article; zbMATH DE number 2148763
• scientific article; zbMATH DE number 2077681
• Zero sum cycles in complete digraphs
• Absolute differences along Hamiltonian paths

Cites work

• \(R\)-sequenceability and \(R^*\)-sequenceability of Abelian 2-groups
• A note on finite abelian groups
• Complete mappings of finite groups
• Counting sets with small sumset, and the clique number of random Cayley graphs
• Hamiltonian circuits in Cayley graphs
• Harmonious groups
• scientific article; zbMATH DE number 3632772 (Why is no real title available?)
• scientific article; zbMATH DE number 3453892 (Why is no real title available?)
• scientific article; zbMATH DE number 874504 (Why is no real title available?)
• On terraces for Abelian groups.
• Sequences in groups with distinct partial products

Cited in

(19)

• Zero sum cycles in complete digraphs
• Perfect codes in Cayley sum graphs
• On some graph-cordial abelian groups
• On random permutations of finite groups
• On integral Cayley sum graphs
• Unitary addition Cayley signed graphs
• scientific article; zbMATH DE number 2148763 (Why is no real title available?)
• scientific article; zbMATH DE number 6957160 (Why is no real title available?)
• Cayley sum color and anti-circulant graphs
• Absolute differences along Hamiltonian paths
• Unitary Addition Cayley Ring Signed Graphs *
• Sums and differences along Hamiltonian cycles
• On Cayley sum graphs of non-abelian groups
• On the subgraphs of Cayley sum graphs
• On subgroup perfect codes in Cayley sum graphs
• On Cayley sum signed graphs-I
• On the cop number and the weak Meyniel conjecture for algebraic graphs
• E_A-cordial labeling of graphs and its implications for A-antimagic labeling of trees
• Subgroup perfect codes in Cayley sum graphs

This page was built for publication: Sums and differences along Hamiltonian cycles

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