Covering the edges of a connected graph by paths
From MaRDI portal
An edge cover of a graph \(G\) by paths is a set of paths so that every edge of \(G\) lies in at least one path. The author proves that every graph \(G\) of order \(n\) can be edge-covered by \({n\over 2}+ O(n^{3/4})\) paths.
Recommendations
Cited in
(43)- Covering projections of graphs preserving links of vertices and edges
- Covering a graph with nontrivial vertex-disjoint paths: existence and optimization
- Gallai's path decomposition conjecture for graphs of small maximum degree
- Gallai's path decomposition conjecture for triangle-free planar graphs
- Minimal path decomposition of complete bipartite graphs
- Path decompositions and Gallai's conjecture
- Subgraph coverings and edge switchings
- The conjunction of the linear arboricity conjecture and Lovász's path partition theorem
- On computing the path number of a graph
- Path decompositions of triangle-free graphs
- An overview of graph covering and partitioning
- On Gallai's conjecture for graphs with maximum degree 6
- On path decompositions of \(2 k\)-regular graphs
- Gallai's conjecture for graphs with treewidth 3
- Path coverings with paths
- On path decompositions of 2k-regular graphs
- Embedding Graphs into Larger Graphs: Results, Methods, and Problems
- Path and cycle decompositions of dense graphs
- Path double covering number of product graphs
- scientific article; zbMATH DE number 3948328 (Why is no real title available?)
- scientific article; zbMATH DE number 4075125 (Why is no real title available?)
- Covering a graph with cycles passing through given edges
- scientific article; zbMATH DE number 6982150 (Why is no real title available?)
- Covering 2-connected 3-regular graphs with disjoint paths
- scientific article; zbMATH DE number 861353 (Why is no real title available?)
- Nordhaus-Gaddum type inequalities for tree covering numbers on unitary Cayley graphs of finite rings
- Covering paths and trees for planar grids
- Cycle packing
- Gallai's conjecture for graphs of girth at least four
- Covering Arrays Avoiding Forbidden Edges
- Gallai's conjecture on path decompositions
- Towards Gallai's path decomposition conjecture
- Edge covers of caterpillars, cycles with pendants, and spider graphs
- Towards the Erdős-Gallai cycle decomposition conjecture
- The problem of path decomposition for graphs with treewidth at most 4
- Towards the Erdős-Gallai cycle decomposition conjecture
- Gallai's conjecture for 3-degenerated graphs
- Gallai's path decomposition conjecture for graphs with maximum E-degree at most 3
- Transitive path decompositions of Cartesian products of complete graphs
- Path decompositions of Eulerian graphs
- Gallai's conjecture and the path number of odd semi-cliques
- Gallai's conjecture on certain families of bipartite graphs
- Path decomposition of graphs with given path length
This page was built for publication: Covering the edges of a connected graph by paths
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1907117)
