A linear-time algorithm for finding a paired 2-disjoint path cover in the cube of a connected graph
From MaRDI portal
Publication:730490
DOI10.1016/j.dam.2016.10.027zbMath1352.05175MaRDI QIDQ730490
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
spanning tree; Hamiltonian path; unicyclic graph; linear-time algorithm; disjoint path cover; cube of graph
05C38: Paths and cycles
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
05C40: Connectivity
05C45: Eulerian and Hamiltonian graphs
Related Items
A linear-time algorithm for finding a one-to-many 3-disjoint path cover in the cube of a connected graph, Disjoint path covers joining prescribed source and sink sets in interval graphs
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A short proof of the versatile version of Fleischner's theorem
- Paired many-to-many disjoint path covers in faulty hypercubes
- A characterization of line graphs that are squares of graphs
- Disjoint path covers in recursive circulants \(G(2^m,4)\) with faulty elements
- 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
- Computing roots of graphs is hard
- The square of a block is Hamiltonian connected
- Many-to-many two-disjoint path covers in cylindrical and toroidal grids
- Hamiltonian paths with prescribed edges in hypercubes
- Single-source three-disjoint path covers in cubes of connected graphs
- Computing square roots of trivially perfect and threshold graphs
- Disjoint path covers in cubes of connected graphs
- Graphs with 1-hamiltonian-connected cubes
- The square of every two-connected graph is Hamiltonian
- Characterization of n-path graphs and of graphs having \(n\)-th root
- Hamiltonian cycles and paths with a prescribed set of edges in hypercubes and dense sets
- 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
- Tree Powers
- Recognizing Powers of Proper Interval, Split, and Chordal Graphs
- Algorithms for Square Roots of Graphs
- Many-to-Many Disjoint Path Covers in the Presence of Faulty Elements
- Paired Many-to-Many Disjoint Path Covers in Recursive Circulants $(G(2^m,4))$
- The square root of a graph
- On the Cube of a Graph
- The cube of every connected graph is 1-hamiltonian
- Linear-Time Algorithms for Tree Root Problems
