# Number of disjoint hamiltonian cycles in a graph

I wish to obtain the maximum number of mutually disjoint hamiltonian cycles in a given graph. Is there any command in SageMath to do it. I think of iterating over getting the hamiltonian cycle of the graph using G.hamiltonian_cycle() function, by deleting the edges of the cycles obtained at each successive iteration from the graph. However, is there a built-in function in SageMath for this? Thanks beforehand.

edit retag close merge delete

2

We don't have such method in Sagemath. This is a hard optimisation problem. You can use integer linear programming to model and solve it.

( 2022-12-02 18:16:15 +0200 )edit
1

Also, your question is not entirely clear. You want the maximal number of pairwise disjoint hamiltonian cycles? I doubt that starting with a random hamiltonian cycle (such as given by G.hamiltonian_cycle()), deleting it and repeating the procedure would give this maximum. If you want a maximal collection of pairwise disjoint hamiltonian cycles (ie such that what remains is not hamiltonian) your suggestion would certainly works.

( 2022-12-02 21:18:13 +0200 )edit

@vdelecroix yes, I want the maximum number of disjoint hamiltonian cycles in a graph. Yes, my method would work for maximal, but I actually wanted maximum of such cycles. edited the question

( 2022-12-03 16:28:10 +0200 )edit

@David Coudert thanks, but could you just slightly elaborate?

( 2022-12-03 16:28:51 +0200 )edit

Sort by ยป oldest newest most voted

This method will return the maximum number of edge disjoint Hamiltonian cycles. This is certainly not the best possible formulation.

def disjoint_hamiltonian_cycles(g, solver=None, verbose=0,
*, integrality_tolerance=1e-3):
"""
"""
from sage.numerical.mip import MixedIntegerLinearProgram
from sage.numerical.mip import MIPSolverException
from sage.graphs.graph import Graph

UB = min(g.degree()) // 2
if not UB:
raise EmptySetError("the given graph is not Hamiltonian")

eps = 1 / (2*Integer(g.order()))
x = next(g.vertex_iterator())

while True:
# Search for UB edge disjoint Hamiltonian cycles
p = MixedIntegerLinearProgram(solver=solver)

f = p.new_variable(binary=True)
r = p.new_variable(nonnegative=True)

# An edge belongs to a unique cycle
for e in g.edge_iterator(labels=False):
p.add_constraint(p.sum(f[frozenset(e), i] for i in range(UB)) <= 1)

# All the vertices of cycle i have degree 2
for i in range(UB):
for v in g:
p.add_constraint(p.sum(f[frozenset((u, v)), i] for u in g.neighbor_iterator(v)), min=2, max=2)

# Connectivity constraints based on the maximum average degree
for i in range(UB):
# r is greater than f
for u, v in g.edge_iterator(labels=None):
p.add_constraint(r[u, v, i] + r[v, u, i] - f[frozenset((u, v)), i], min=0)

# no cycle which does not contain x
for v in g:
if v != x:
p.add_constraint(p.sum(r[u, v, i] for u in g.neighbor_iterator(v)), max=1 - eps)

try:
p.solve(log=verbose)
f_val = p.get_values(f, convert=bool, tolerance=integrality_tolerance)
tsp = [Graph() for i in range(UB)]
for i in range(UB):
tsp[i].set_pos(g.get_pos())
for (e, i), b in f_val.items():
if b:
return tsp

except MIPSolverException:
UB -= 1
if not UB:
raise EmptySetError("the given graph is not Hamiltonian")


You get:

sage: G = graphs.CompleteGraph(5)
sage: T = disjoint_hamiltonian_cycles(G)
sage: T
[Graph on 5 vertices, Graph on 5 vertices]
sage: [t.edges(labels=False, sort=True) for t in T]
[[(0, 1), (0, 3), (1, 4), (2, 3), (2, 4)],
[(0, 2), (0, 4), (1, 2), (1, 3), (3, 4)]]
sage: G = graphs.CompleteGraph(7)
sage: T = disjoint_hamiltonian_cycles(G)
sage: [t.edges(labels=False, sort=True) for t in T]
[[(0, 1), (0, 4), (1, 6), (2, 3), (2, 5), (3, 6), (4, 5)],
[(0, 2), (0, 5), (1, 3), (1, 4), (2, 6), (3, 5), (4, 6)],
[(0, 3), (0, 6), (1, 2), (1, 5), (2, 4), (3, 4), (5, 6)]]

more

Thanks! that is so kind of you! Actually, I wanted just the maximum number of disjoint hamiltonian cycles, but you gave the full construction. Anyways, the len() would suffice for my needs

( 2022-12-04 20:01:25 +0200 )edit

Note that the number of edge disjoint Hamiltonian cycles is upper bounded by half the minimum degree of the graph

sage: G = graphs.CompleteGraph(5)
sage: min(G.degree()) // 2
2
sage: G = graphs.CompleteGraph(7)
sage: min(G.degree()) // 2
3

( 2023-02-18 09:33:44 +0200 )edit