2-Edge Hamiltonian connectedness: Characterization and results in data center networks

Mei-Li Wang, Rong-Xia Hao, Jou-Ming Chang and Sejeong Bang

Applied Mathematics and Computation, 2025, vol. 490, issue C

Abstract: A graph G is 2-edge Hamiltonian connected if for any edge set E⊆{uv:u,v∈V(G),u≠v} with |E|≤2, G∪E has a Hamiltonian cycle containing all edges of E, where G∪E is the graph obtained from G by including all edges of E. The problem of determining whether a graph is 2-edge Hamiltonian connected is challenging, as it is known to be NP-complete. This property is stronger than Hamiltonian connectedness, which indicates the existence of a Hamiltonian path between every pair of vertices in a graph. This paper first provides a characterization and a sufficiency for 2-edge Hamiltonian connectedness. Through this, we shed light on the fact that many well-known networks are 2-edge Hamiltonian connected, including BCube data center networks and some variations of hypercubes, and so on. Additionally, we demonstrate that DCell data center networks and Cartesian product graphs containing almost all generalized hypercubes are 2-edge Hamiltonian connected.

Keywords: Data center networks; Hamiltonian cycle; Hamiltonian connectedness; k-Edge Hamiltonian connectedness; Disjoint path cover (search for similar items in EconPapers)
Date: 2025
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300324006581
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:490:y:2025:i:c:s0096300324006581

DOI: 10.1016/j.amc.2024.129197

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().