TOPICS
Search

Unpath Number


The unpath number of a graph G (Akiyama et al. 1980, p. 415), called the apathy of G by Harary and Palmer (1973, p. 268), is the maximum number of edge-disjoint connected subgraphs of G that are not paths. It is the packing counterpart of the path number, in the same covering/packing sense that anarboricity is the packing counterpart of arboricity.


See also

Anarboricity, Path Number

Explore with Wolfram|Alpha

References

Akiyama, J.; Exoo, G.; and Harary, F. "Covering and Packing in Graphs III: Cyclic and Acyclic Invariants." Math. Slovaca 30, 405-417, 1980.Harary, F. and Palmer, E. M. "A Survey of Graphical Enumeration Problems." In A Survey of Combinatorial Theory (Ed. J. N. Srivastava). Amsterdam, Netherlands: North-Holland, pp. 259-275, 1973.Zelinka, B. "Unpath Number of a Complete Multipartite Graph." Math. Slovaca 33, 293-296, 1983.

Cite this as:

Weisstein, Eric W. "Unpath Number." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/UnpathNumber.html

Subject classifications