Characterizing k-edge Hamiltonian connectedness for enhancing network structures

Huimei Guo

doi:10.1016/j.ic.2026.105461

Characterizing k-edge Hamiltonian connectedness for enhancing network structures

2026-06-01

0

PRE

AI

DOI：10.1016/j.ic.2026.105461

Original

Original request for help

Save

Abstract

En 中文

Let G = (V, E) be a graph and let K|V| denote the complete graph on the same vertex set as G. A potential edge set of G is a subset of E(K|V|) such that the subgraph it induced in K|V| forms a set of paths. A graph G is k-edge Hamiltonian-connected (k-EHC) if, for any potential edge set E with 1 <= |E| <= k, G U E contains a Hamiltonian cycle that includes every edge of E. This notion generalizes the concept of Hamiltonian connectedness. Determining whether a graph is k-EHC is NP-complete, even for k = 2. In [J. Graph Theory 69 (2012) 241-250], a characterization of 2-EHC graphs was provided. This paper expands upon that result by characterizing graphs that are k-EHC for k >= 1. As an application of this characterization, we further demonstrate that a series of network classes based on the enhanced structure of hypercubes, known as augmented cubes, meet the k-EHC property for k = 2, 3.

Keywords:

Hamiltonian connectedness

k-edge Hamiltonian connectedness

Disjoint path cover

Characterizing k-edge Hamiltonian connectedness for enhancing network structures

Abstract

Journal

Organization