A linear-time algorithm for finding a paired 2-disjoint path cover in the cube of a connected graph

DOI10.1016/J.DAM.2016.10.027MaRDI QIDQ730490zbMATH OpenOpenAlexFDO

Authors Insung Ihm, Jung-Heum Park

Publication date 28 December 2016

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2016.10.027

zbMATH Keywords

Hamiltonian pathunicyclic graphspanning treelinear-time algorithmdisjoint path covercube of graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Eulerian and Hamiltonian graphs (05C45) Paths and cycles (05C38) Connectivity (05C40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• A linear-time algorithm for finding a one-to-many 3-disjoint path cover in the cube of a connected graph
• Disjoint path covers in cubes of connected graphs
• Single-source three-disjoint path covers in cubes of connected graphs
• Paired many-to-many disjoint path covers in restricted hypercube-like graphs
• scientific article; zbMATH DE number 3858436

Cites work

• scientific article; zbMATH DE number 3600075 (Why is no real title available?)
• scientific article; zbMATH DE number 6469239 (Why is no real title available?)
• scientific article; zbMATH DE number 3192675 (Why is no real title available?)
• A characterization of line graphs that are squares of graphs
• A short proof of Fleischner's theorem
• A short proof of the versatile version of Fleischner's theorem
• Algorithms for Square Roots of Graphs
• Characterization of n-path graphs and of graphs having \(n\)-th root
• Computing roots of graphs is hard
• Computing square roots of trivially perfect and threshold graphs
• Disjoint path covers in cubes of connected graphs
• Disjoint path covers in recursive circulants G(2ᵐ,4) with faulty elements
• Graph theory
• Graphs with 1-hamiltonian-connected cubes
• Hamiltonian cycles and paths with a prescribed set of edges in hypercubes and dense sets
• Hamiltonian paths with prescribed edges in hypercubes
• Hamiltonian properties of the cube of a 2-edge connected graph
• Linear-Time Algorithms for Tree Root Problems
• Many-to-Many Disjoint Path Covers in the Presence of Faulty Elements
• Many-to-many disjoint paths in faulty hypercubes
• Many-to-many two-disjoint path covers in cylindrical and toroidal grids
• On graphs whose square have strong Hamiltonian properties
• On the Cube of a Graph
• Paired Many-to-Many Disjoint Path Covers in Recursive Circulants $(G(2^m,4))$
• Paired many-to-many disjoint path covers in faulty hypercubes
• Partitions of Faulty Hypercubes into Paths with Prescribed Endvertices
• Path partitions of hypercubes
• Recognizing Powers of Proper Interval, Split, and Chordal Graphs
• Single-source three-disjoint path covers in cubes of connected graphs
• The 2-hamiltonian cubes of graphs
• The cube of every connected graph is 1-hamiltonian
• The square of a block is Hamiltonian connected
• The square of every two-connected graph is Hamiltonian
• The square root of a graph
• Tree Powers

Cited in

(8)

• Paired 2-disjoint path covers of faulty \(k\)-ary \(n\)-cubes
• Characterization of interval graphs that are unpaired 2-disjoint path coverable
• Disjoint path covers in cubes of connected graphs
• Single-source three-disjoint path covers in cubes of connected graphs
• A linear‐time algorithm for the k‐fixed‐endpoint path cover problem on cographs
• Disjoint path covers joining prescribed source and sink sets in interval graphs
• A linear-time algorithm for finding a one-to-many 3-disjoint path cover in the cube of a connected graph
• How many disjoint 2-edge paths must a cubic graph have?

Describes a project that uses

Uses Software

• Algorithm 447

This page was built for publication: A linear-time algorithm for finding a paired 2-disjoint path cover in the cube of a connected graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q730490)