Path Covering Number

Author

Eric W. Weisstein
August 9, 2021

This notebook downloaded from http://mathworld.wolfram.com/notebooks/GraphTheory/PathCoveringNumber.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/PathCoveringNumber.html.

©2021 Wolfram Research, Inc. except for portions noted otherwise

Missing

Tree by VertexCount

missingtrees=SortBy[Select[GraphData["Tree"],MissingQ[GraphData[#,"PathCoveringNumber"]]&],GraphData[#,"V"]&]

by PathCount

missing=SortBy[Select[GraphData[All],MissingQ[GraphData[#,"PathCoveringNumber"]]&],Total[GraphData[#,{"V","PathCount"}]]&]

Cyclic by VertexCount

missing=SortBy[Select[GraphData["Cyclic"],MissingQ[GraphData[#,"PathCoveringNumber"]]&],GraphData[#,"V"]&]

Parametrized families

Note: for traceable graphs, "PathCoveringNumber" == 1

GraphDataCountTable["PathCoveringNumber"]

Alkane

Computed up to n=3; inferred for rest

Table[GraphData[{"Alkane",n},"PathCoveringNumber"],{n,10}]

Table[
HighlightGraph[g=GraphData[{"Alkane",n},"Graph","Labeled"],Replace[
Join@@(UndirectedEdge@@@Partition[#,2,1,1]&/@FindPathCovering[g]),
UndirectedEdge[x_,x_]:>x,
{1}
]],{n,3}]

Andrasfai

seq=Table[GraphData[{"Andrasfai",n},"PathCoveringNumber"],{n,10}]

Antiprism

Entity["Graph",{"Antiprism",n}]["PathCoveringNumber"]

Table[GraphData[{"Antiprism",n},"PathCoveringNumber"],{n,3,25}]

Apollonian

seq=Table[GraphData[{"Apollonian",n},"PathCoveringNumber"],{n,6}]

seq=Table[GraphData[{"Apollonian",n},"Traceable"],{n,6}]

Table[
HighlightGraph[g=GraphData[{"Apollonian",n},"Graph","Labeled"],Replace[
Join@@(UndirectedEdge@@@Partition[#,2,1,1]&/@FindPathCovering[g]),
UndirectedEdge[x_,x_]:>x,
{1}
]],{n,2}]

Barbell

seq=Table[GraphData[{"Barbell",n},"PathCoveringNumber"],{n,3,20}]

Bishop n×n

Table[GraphData[{"Bishop",{n,n}},"PathCoveringNumber"],{n,10}]

BlackBishop n×n

seq=Table[GraphData[{"BlackBishop",{n,n}},"PathCoveringNumber"],{n,10}]

Book

seq=Table[GraphData[{"Book",n},"PathCoveringNumber"],{n,20}]

Table[
HighlightGraph[g=GraphData[{"Book",n},"Graph","Labeled"],Replace[
Join@@(UndirectedEdge@@@Partition[#,2,1,1]&/@FindPathCovering[g]),
UndirectedEdge[x_,x_]:>x,
{1}
]],{n,5}]

Centipede

Computed up to n=8; extrapolated beyond

seq=Table[GraphData[{"Centipede",n},"PathCoveringNumber"],{n,10}]

Table[Ceiling[n/2],{n,10}]

Table[
HighlightGraph[g=GraphData[{"Centipede",n},"Graph","Labeled"],Replace[
Join@@(UndirectedEdge@@@Partition[#,2,1,1]&/@FindPathCovering[g]),
UndirectedEdge[x_,x_]:>x,
{1}
]],{n,7}]

CocktailParty

seq=Table[GraphData[{"CocktailParty",n},"PathCoveringNumber"],{n,20}]

Complete

Entity["Graph",{"Complete",n}]["PathCoveringNumber"]

Table[GraphData[{"Complete",n},"PathCoveringNumber"],{n,30}]

CompleteBipartite m×n

Entity["Graph",{"CompleteBipartite",{m,n}}]["PathCoveringNumber"]

Boesch, F.~T.; Chen, S.; and McHugh, J.~A.~M.  ``On Covering the Points of a Graph with Point Disjoint Paths.'' In Graphs and Combinatorics (Ed.\ R.~A.~Bari and F.~Harary).  Berlin: Springer-Verlag, pp.~201--212, 1974.

DeleteCases[Flatten[Table[{{m,n},GraphData[{"CompleteBipartite",{m,n}},"PathCoveringNumber"],Max[1,Abs[n-m]]},{n,20},{m,n}],1],{_,x_,x_}]

CompleteBipartite n×n

Entity["Graph",{"CompleteBipartite",{n,n}}]["PathCoveringNumber"]

Table[GraphData[{"CompleteBipartite",{n,n}},"PathCoveringNumber"],{n,20}]

CompleteKPartite

Boesch, F.~T.; Chen, S.; and McHugh, J.~A.~M.  ``On Covering the Points of a Graph with Point Disjoint Paths.'' In Graphs and Combinatorics (Ed.\ R.~A.~Bari and F.~Harary).  Berlin: Springer-Verlag, pp.~201--212, 1974.

If[Length[#]==1,1,Max[1,Last[#]-Total[Most[#]]]]&@GraphData[g,"NotationRules","CompleteKPartite"]}}]

CompleteTripartite k×m×n

Entity["Graph",{"CompleteTripartite",{k,m,n}}]["PathCoveringNumber"]

DeleteCases[Flatten[Table[
{
{k,m,n},
GraphData[{"CompleteTripartite",{k,m,n}},"PathCoveringNumber"],
Max[1,2Max[k,m,n]-(k+m+n)]
},{n,10},{m,n},{k,m}],2],{_,x_,x_}]

CompleteTripartite n×n×n

Entity["Graph",{"CompleteTripartite",{n,n,n}}]["PathCoveringNumber"]

Table[GraphData[{"CompleteTripartite",{n,n,n}},"PathCoveringNumber"],{n,10}]

CrossedPrism

seq=Table[GraphData[{"CrossedPrism",2n},"PathCoveringNumber"],{n,2,10}]

Crown

seq=Table[GraphData[{"Crown",n},"PathCoveringNumber"],{n,3,20}]

CubeConnectedCycle

Entity["Graph",{"CubeConnectedCycle",n}]["PathCoveringNumber"]

Table[GraphData[{"CubeConnectedCycle",n},"PathCoveringNumber"],{n,3,8}]

Cycle

Entity["Graph",{"Cycle",n}]["PathCoveringNumber"]

Table[GraphData[{"Cycle",n},"PathCoveringNumber"],{n,3,20}]

CycleComplement

Table[GraphData[{"CycleComplement",n},"PathCoveringNumber"],{n,3,20}]

DiagonalIntersection

seq=Table[GraphData[{"DiagonalIntersection",n},"PathCoveringNumber"],{n,3,10}]

Empty

Entity["Graph",{"Empty",n}]["PathCoveringNumber"]

Table[GraphData[{"Empty",n},"PathCoveringNumber"],{n,30}]

FibonacciCube

Table[GraphData[{"FibonacciCube",n},"PathCoveringNumber"],{n,15}]

FoldedCube

Table[GraphData[{"FoldedCube",n},"PathCoveringNumber"],{n,2,10}]

Gear

seq=Table[GraphData[{"Gear",n},"PathCoveringNumber"],{n,3,20}]

Grid m×n

Entity["Graph",{"Grid",{m,n}}]["PathCoveringNumber"]

DeleteCases[Flatten[Table[{{m,n},GraphData[{"Grid",{m,n}},"PathCoveringNumber"],1},{n,10},{m,n}],1],{_,x_,x_}]

Grid n×n

Entity["Graph",{"Grid",{n,n}}]["PathCoveringNumber"]

Table[GraphData[{"Grid",{n,n}},"PathCoveringNumber"],{n,10}]

Grid k×m×n

Entity["Graph",{"Grid",{k,m,n}}]["PathCoveringNumber"]

DeleteCases[Flatten[Table[{{k,m,n},GraphData[{"Grid",{k,m,n}},"PathCoveringNumber"],1},{n,5},{m,n},{k,m}],2],{_,x_,x_}]

Grid n×n×n

Entity["Graph",{"Grid",{n,n,n}}]["PathCoveringNumber"]

Table[GraphData[{"Grid",{n,n,n}},"PathCoveringNumber"],{n,10}]

HalvedCube

Table[GraphData[{"HalvedCube",n},"PathCoveringNumber"],{n,2,10}]

Hanoi

Table[GraphData[{"Hanoi",n},"PathCoveringNumber"],{n,5}]

Helm

Table[GraphData[{"Helm",n},"PathCoveringNumber"],{n,3,20}]

Table[
HighlightGraph[g=GraphData[{"Helm",n},"Graph","Labeled"],Replace[
Join@@(UndirectedEdge@@@Partition[#,2,1,1]&/@FindPathCovering[g]),
UndirectedEdge[x_,x_]:>x,
{1}
]],{n,3,5}]

Hypercube

Entity["Graph",{"Hypercube",n}]["PathCoveringNumber"]

Table[GraphData[{"Hypercube",n},"PathCoveringNumber"],{n,0,10}]

Keller

Entity["Graph",{"Keller",n}]["PathCoveringNumber"]

Table[GraphData[{"Keller",n},"PathCoveringNumber"],{n,5}]

King n×n

Table[GraphData[{"King",{n,n}},"PathCoveringNumber"],{n,10}]

Knight m×n

Entity["Graph",{"Knight",{m,n}}]["PathCoveringNumber"]

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"Knight",{m,n}},"PathCoveringNumber"],
Piecewise[{{Max[m,n],Min[m,n]==1},{2,m==n==3||m==n==4||(Min[m,n]==3&&4<Max[m,n]<7)},{4,Min[m,n]==2}},1]
},{n,10},{m,n}],1],{_,x_,x_}]

Complement[GraphData[{"Connected","Knight"}],GraphData["Traceable"]]

FindPathCovering[GraphData[{"Knight",{3,5}}]]//Timing

FindPathCovering[GraphData[{"Knight",{3,6}}]]//Timing

FindPathCovering[GraphData[{"Knight",{4,4}}]]//Timing

Knight n×n

Entity["Graph",{"Knight",{n,n}}]["PathCoveringNumber"]

Table[GraphData[{"Knight",{n,n}},"PathCoveringNumber"],{n,20}]

g=GraphData[{"Knight",{4,4}},"Graph","Labeled"]

PathCoveringNumber[GraphData[{"Knight",{4,4}}],Debug->True]//Timing

HighlightGraph[g,UndirectedEdge@@@Partition[{2,8,15,9,7,16,10,3,5,14,12,6,4,11,13},2,1],EdgeShapeFunction->GraphElementData["Arrow","ArrowSize"->.1]]

Ladder

Entity["Graph",{"Ladder",n}]["PathCoveringNumber"]

Table[GraphData[{"Ladder",n},"PathCoveringNumber"],{n,20}]

LadderRung

Table[GraphData[{"LadderRung",n},"PathCoveringNumber"],{n,20}]

MengerSponge

Table[GraphData[{"MengerSponge",n},"PathCoveringNumber"],{n,3}]

MoebiusLadder

Entity["Graph",{"MoebiusLadder",n}]["PathCoveringNumber"]

Table[GraphData[{"MoebiusLadder",n},"PathCoveringNumber"],{n,3,25}]

Mycielski

Entity["Graph",{"Mycielski",n}]["PathCoveringNumber"]

Table[GraphData[{"Mycielski",n},"PathCoveringNumber"],{n,2,10}]

Odd

Entity["Graph",{"Odd",n}]["PathCoveringNumber"]

Table[GraphData[{"Odd",n},"PathCoveringNumber"],{n,7}]

Pan

Table[GraphData[{"Pan",n},"PathCoveringNumber"],{n,3,20}]

Path

Entity["Graph",{"Path",n}]["PathCoveringNumber"]

Table[GraphData[{"Path",n},"PathCoveringNumber"],{n,20}]

PathComplement

Table[GraphData[{"PathComplement",n},"PathCoveringNumber"],{n,20}]

Prism

Entity["Graph",{"Prism",n}]["PathCoveringNumber"]

Table[GraphData[{"Prism",n},"PathCoveringNumber"],{n,3,25}]

Queen n×n

Table[GraphData[{"Queen",{n,n}},"PathCoveringNumber"],{n,10}]

Rook n×n

seq=Table[GraphData[{"Rook",{n,n}},"PathCoveringNumber"],{n,10}]

RookComplement n×n

seq=Table[GraphData[{"RookComplement",{n,n}},"PathCoveringNumber"],{n,10}]

SierpinskiCarpet

Table[GraphData[{"SierpinskiCarpet",n},"PathCoveringNumber"],{n,4}]

SierpinskiSieve

Table[GraphData[{"SierpinskiSieve",n},"PathCoveringNumber"],{n,5}]

SierpinskiTetrahedron

Table[GraphData[{"SierpinskiTetrahedron",n},"PathCoveringNumber"],{n,6}]

Star

Entity["Graph",{"Star",n}]["PathCoveringNumber"]

Table[GraphData[{"Star",n},"PathCoveringNumber"],{n,3,25}]

Sun

seq=Table[GraphData[{"Sun",n},"PathCoveringNumber"],{n,3,20}]

Sunlet

Computed up to n=8; inferred beyond

seq=Table[GraphData[{"Sunlet",n},"PathCoveringNumber"],{n,3,20}]

Table[Ceiling[n/2],{n,3,20}]

Table[
HighlightGraph[g=GraphData[{"Sunlet",n},"Graph","Labeled"],Replace[
Join@@(UndirectedEdge@@@Partition[#,2,1,1]&/@FindPathCovering[g]),
UndirectedEdge[x_,x_]:>x,
{1}
]],{n,3,7}]

FindSequenceFunction[seq,n-2]//Factor

Tetrahedral

Table[GraphData[{"Tetrahedral",n},"PathCoveringNumber"],{n,6,10}]

TorusGrid n×n

seq=Table[GraphData[{"TorusGrid",{n,n}},"PathCoveringNumber"],{n,3,10}]

Transposition

Entity["Graph",{"Transposition",n}]["PathCoveringNumber"]

Table[GraphData[{"Transposition",n},"PathCoveringNumber"],{n,6}]

Triangular

seq=Table[GraphData[{"Triangular",n},"PathCoveringNumber"],{n,3,10}]

TriangularGrid

seq=Table[GraphData[{"TriangularGrid",n},"PathCoveringNumber"],{n,10}]

Web

seq=Table[GraphData[{"Web",n},"PathCoveringNumber"],{n,3,20}]

Table[
HighlightGraph[g=GraphData[{"Web",n},"Graph","Labeled"],Replace[
Join@@(UndirectedEdge@@@Partition[#,2,1,1]&/@FindPathCovering[g]),
UndirectedEdge[x_,x_]:>x,
{1}
]],{n,3,4}]

FindSequenceFunction[seq,n-2]//Factor

TriangularSnake

seq=Table[GraphData[{"TriangularSnake",2n-1},"PathCoveringNumber"],{n,10}]

Wheel

Entity["Graph",{"Wheel",n}]["PathCoveringNumber"]

Table[GraphData[{"Wheel",n},"PathCoveringNumber"],{n,4,20}]

WhiteBishop n×n

Table[GraphData[{"WhiteBishop",{n,n}},"PathCoveringNumber"],{n,2,10}]

Examples

"ClawGraph"

GraphData[gn="ClawGraph","Graph","Labeled"]

FindPaths[GraphData[gn]]

FindPaths[Graph[{1},{}]]

FindPaths[]

OptionQ[{}]

PathCoveringNumber[GraphData[gn],Debug->True]

PathCoveringNumber[StarGraph[1],Debug->True]

PathCoveringNumber[StarGraph[2]]

StarGraph[5]

Table[PathCoveringNumber[StarGraph[n]],{n,8}]

Table[Piecewise[{{1,n==1||n==2}},n-2],{n,8}]

Table[PathCoveringNumber[StarGraph[n+1]],{n,6}]

Table[PathCoveringNumber[CompleteGraph[{1,n}]],{n,6}]

(Subscript[K, 4])

GraphData["K4","Graph","Labeled"]

FindPaths[GraphData["K4"]]

PathCoveringNumber[GraphData["K4"],Debug->True]

{5, 31}

GraphData[{5,31},"Traceable"]

GraphData[{5,31},"IndependenceNumber"]

GraphData[{5,31},"Graph","Labeled"]

FindPaths[GraphData[{5,31}]]

PathCoveringNumber[GraphData[{5,31}],Debug->True]

Algorithms

Subsets

GraphData[{"Sunlet",3},"Graph","Labeled"]

PathCoveringNumber[GraphData[{"Sunlet",3}],Method->"Subsets",Debug->True]

PathCoveringNumber[GraphData[{5,31}],Method->"Subsets",Debug->True]

PathCoveringNumber[GraphData[{"Tree",{11,196}}],Method->"Subsets",Debug->True]

NextSubset

PathCoveringNumber[GraphData[{"Sunlet",3}],Method->"NextSubset",Debug->True]

PathCoveringNumber[GraphData[{5,31}],Method->"NextSubset",Debug->True]