Jacobsthal numbers in generalised Petersen graphs

DOI10.1016/J.ENDM.2015.06.065MaRDI QIDQ322296zbMATH OpenOpenAlexFDO

Authors Henning Bruhn, Laura Gellert, Jacob Günther

Publication date 14 October 2016

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

zbMATH Keywords

edge colouringJacobsthal numbers1-factorizationsgeneralized Petersen graphslist colouring conjecture

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: We prove that the number of $1$-factorisations of a generalised Petersen graph of the type $GP(3k,k)$ is equal to the $k$th Jacobsthal number $J(k)$ if $k$ is odd, and equal to $4J(k)$, when $k$ is even. Moreover, we verify the list colouring conjecture for $GP(3k,k)$.

Recommendations

• Jacobsthal Numbers in Generalized Petersen Graphs
• Lower bound on the number of Hamiltonian cycles of generalized Petersen graphs
• The lower bound for the number of 1-factors in generalized Petersen graphs
• On Jacobian group and complexity of the generalized Petersen graph \(\mathrm{GP}(n,k)\) through Chebyshev polynomials
• On a two-parameter generalization of Jacobsthal numbers and its graph interpretation

Cites work

• scientific article; zbMATH DE number 446487 (Why is no real title available?)
• scientific article; zbMATH DE number 2024859 (Why is no real title available?)
• scientific article; zbMATH DE number 1522329 (Why is no real title available?)
• scientific article; zbMATH DE number 1439438 (Why is no real title available?)
• scientific article; zbMATH DE number 5274215 (Why is no real title available?)
• A theorem on tait colorings with an application to the generalized Petersen graphs
• Colorings and orientations of graphs
• Every generalized Petersen graph has a Tait coloring
• Jacobsthal numbers in generalised Petersen graphs
• List edge colourings of some 1-factorable multigraphs
• Self-dual configurations and regular graphs
• The list chromatic index of a bipartite multigraph
• The number of meets between two subsets of a lattice

Cited in

(9)

• On Jacobian group and complexity of the generalized Petersen graph \(\mathrm{GP}(n,k)\) through Chebyshev polynomials
• Catalan transform of the \(k\)-Jacobsthal sequence
• Jacobsthal Numbers in Generalized Petersen Graphs
• scientific article; zbMATH DE number 7004644 (Why is no real title available?)
• scientific article; zbMATH DE number 7379953 (Why is no real title available?)
• Jacobsthal numbers in generalised Petersen graphs
• The lower bound for the number of 1-factors in generalized Petersen graphs
• On the adjacency-Jacobsthal numbers
• The Adjacency-Jacobsthal-Hurwitz type numbers

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Jacobsthal numbers in generalised Petersen graphs

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