Single-source three-disjoint path covers in cubes of connected graphs

DOI10.1016/j.ipl.2013.04.012zbMath1285.05106OpenAlexW2118864569MaRDI QIDQ2444763

Insung Ihm, Jung-Heum Park

Publication date: 11 April 2014

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2013.04.012

zbMATH Keywords

combinatorial problemsHamiltonicitygraph embeddingdisjoint path covercube of a graph

Mathematics Subject Classification ID

Connectivity (05C40) Eulerian and Hamiltonian graphs (05C45)

Related Items (11)

Algorithms for finding disjoint path covers in unit interval graphs ⋮ Paired many-to-many disjoint path covers in restricted hypercube-like graphs ⋮ A linear-time algorithm for finding a one-to-many 3-disjoint path cover in the cube of a connected graph ⋮ Ore-type degree conditions for disjoint path covers in simple graphs ⋮ One-to-one disjoint path covers in digraphs ⋮ Unpaired many-to-many disjoint path covers in restricted hypercube-like graphs ⋮ Many-to-many two-disjoint path covers in restricted hypercube-like graphs ⋮ Disjoint path covers in cubes of connected graphs ⋮ A linear-time algorithm for finding a paired 2-disjoint path cover in the cube of a connected graph ⋮ One-to-one disjoint path covers on multi-dimensional tori ⋮ Many-to-many two-disjoint path covers in cylindrical and toroidal grids

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Disjoint path covers in recursive circulants \(G(2^m,4)\) with faulty elements
• Hamiltonian cycles in the square of a graph
• Many-to-many disjoint paths in faulty hypercubes
• Path partitions of hypercubes
• On graphs whose square have strong Hamiltonian properties
• A short proof of Fleischner's theorem
• In the square of graphs, Hamiltonicity and pancyclicity, Hamiltonian connectedness and panconnectedness are equivalent concepts
• The square of a block is Hamiltonian connected
• Induced \(S(K_{1,3})\) and hamiltonian cycles in the square of a graph
• The 1-fixed-endpoint path cover problem is Polynomial on interval graphs
• Disjoint path covers in cubes of connected graphs
• Graphs with 1-hamiltonian-connected cubes
• The square of every two-connected graph is Hamiltonian
• Hamiltonian Paths in the Square of a Tree
• The 2-hamiltonian cubes of graphs
• Partitions of Faulty Hypercubes into Paths with Prescribed Endvertices
• Hamiltonian properties of the cube of a 2-edge connected graph
• On Path Cover Problems in Digraphs and Applications to Program Testing
• Many-to-Many Disjoint Path Covers in the Presence of Faulty Elements
• On the Cube of a Graph
• The cube of every connected graph is 1-hamiltonian
• Trees with Hamiltonian square

This page was built for publication: Single-source three-disjoint path covers in cubes of connected graphs