Jacobsthal numbers in generalised Petersen graphs

DOI10.1016/J.ENDM.2015.06.065zbMATH Open1346.05226arXiv1503.03390OpenAlexW2296304975MaRDI QIDQ322296FDOQ322296

Authors: Henning Bruhn, Laura Gellert, Jacob Günther 

Publication date: 14 October 2016

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

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

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

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)

Cites Work

• Title not available (Why is that?)
• A theorem on tait colorings with an application to the generalized Petersen graphs
• Self-dual configurations and regular graphs
• The list chromatic index of a bipartite multigraph
• Every generalized Petersen graph has a Tait coloring
• List edge colourings of some 1-factorable multigraphs
• Title not available (Why is that?)
• Colorings and orientations of graphs
• The number of meets between two subsets of a lattice
• Jacobsthal numbers in generalised Petersen graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)

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
• Title not available (Why is that?)
• Jacobsthal Numbers in Generalized Petersen Graphs
• Title not available (Why is that?)
• 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

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)