Median Graph

Author

Eric W. Weisstein
July 28, 2023

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

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

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

Counts

All == Connected

A292623

1, 1, 1, 3, 4, 11, 23, 69, 178, 567

Total[Boole[Get[#]]]&/@FileNames["*.m",FileNameJoin[{$GraphDataDirectory,"Nodes","Median"}]]

Table[Count[ConnectedGraphs[n],_?MedianGraphQ],{n,10}]//Timing

Length/@Table[GraphData["Median",n],{n,10}]

Disconnected

0

Table[Total[Boole[Get[FileNameJoin[{$GraphDataDirectory,"Nodes","Median","Median_"<>If[n<10,"0",""]<>ToString[n]<>".m"}]][[DisconnectedGraphIndices[n]]]]],{n,10}]

Table

median=Table[{n,Select[GraphData[n],GraphData[#,"Median"]===True&]},{n,6}]

TextGrid[median,Dividers->All]

Graphic

GraphicsGrid[Map[Show[GraphData[#]/.g_System`Graph:>SetProperty[g,{VertexSize->If[VertexCount[g]==1,.02,{"Scaled",.07}],System`VertexStyle->Red,System`EdgeStyle->Black}],PlotLabel->TextCell[Style[GraphData[#,"Name"],FontSlant->Italic,FontColor->Black,FontFamily->"Times"],TextAlignment->Center,PageWidth->80]]&,Flatten[Partition[#,UpTo[6]]&/@median[[All,2]],1],{2}],
Dividers->All,ImageSize->500]

Algorithm

FindShortestPath finds only one of possibly many shortest paths

ShortestPathInterval[a_,b_,d_]:=Module[{n=Length[d]},
Select[Range[n],d[[a,b]]==d[[a,#]]+d[[#,b]]&]
]

g=GraphData[{"Grid",{3,3}},"Graph","Labeled"]

d=GraphDistanceMatrix[g]

ShortestPathInterval[1,2,d]

ShortestPathInterval[1,3,d]

ShortestPathInterval[2,6,d]

ShortestPathInterval[1,9,d]

subs=Subsets[Range[9],{3}]

Intersection@@(ShortestPathInterval[Sequence@@#,d]&/@Partition[{1,2,3},2,1,1])

Intersection@@(ShortestPathInterval[Sequence@@#,d]&/@Partition[{1,2,4},2,1,1])

Parametrized familes

GraphDataCountTable["Median"]

Antiprism

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

Circulant

Entity["Graph",{"Circulant",{n,{i1,i2}}}]["Median"]

TextGrid[DeleteCases[{#,GraphData[#,"NotationRules","Circulant"],GraphData[#,"Median"]}&/@GraphData["Circulant"],{__,False}],Dividers->All]

Complete

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

CompleteBipartite m×n

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

Sort@DeleteCases[{GraphData[#,"NotationRules","CompleteBipartite"],#,GraphData[#,"Median"]}&/@GraphData["CompleteBipartite"],{__,False}]

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"CompleteBipartite",{m,n}},"Median"],
Piecewise[{{True,Min[m,n]==1||m==n==2}},False]
},{n,10},{m,n}],1],{_,x_,x_}]

CompleteBipartite n×n

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

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

CompleteTripartite k×m×n

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

Sort@DeleteCases[{GraphData[#,"NotationRules","CompleteBipartite"],#,GraphData[#,"Median"]}&/@GraphData["CompleteTripartite"],{__,False}]

CompleteTripartite n×n×n

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

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

CubeConnectedCycle

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

Cycle

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

Empty

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

FibonacciCube

https://arxiv.org/pdf/2307.14054.pdf

Klavˇzar [5] proved that Fibonacci and Lucas cubes are median graphs, and Munarini [11] proved that Pell graphs are median graphs. They both used the following theorem by Mulder [10]:

[5] S. Klavzar, On median nature and enumerative properties of fibonacci-like cubes, Discrete Math. 299 (2005) 145–153.

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

GeneralizedPetersen

Entity["Graph",{"GeneralizedPetersen",{k,n}}]["Median"]

Sort@DeleteCases[{GraphData[#,"NotationRules","GeneralizedPetersen"],#,GraphData[#,"Median"]}&/@GraphData["GeneralizedPetersen"],{__,False}]

Grid m×n

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

Sort@DeleteCases[{GraphData[#,"NotationRules","Grid"],#,GraphData[#,"Median"]}&/@GraphData["Grid"],{__,True}]

Grid n×n

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

Sort@DeleteCases[{GraphData[#,"NotationRules","Grid"],#,GraphData[#,"Median"]}&/@GraphData["Grid"],{__,True}]

Grid k×m×n

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

Grid n×n×n

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

Hypercube

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

Keller

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

Knight m×n

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

Sort@DeleteCases[{GraphData[#,"NotationRules","Knight"],#,GraphData[#,"Median"]}&/@GraphData["Knight"],{__,False}]

Knight n×n

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

Ladder

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

LucasCube

https://arxiv.org/pdf/2307.14054.pdf

Klavˇzar [5] proved that Fibonacci and Lucas cubes are median graphs, and Munarini [11] proved that Pell graphs are median graphs. They both used the following theorem by Mulder [10]:

[5] S. Klavzar, On median nature and enumerative properties of fibonacci-like cubes, Discrete Math. 299 (2005) 145–153.

Table[GraphData[{"LucasCube",n},"Median"],{n,15}]

MoebiusLadder

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

Mycielski

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

Odd

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

Path

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

Pell

https://arxiv.org/pdf/2307.14054.pdf

Klavˇzar [5] proved that Fibonacci and Lucas cubes are median graphs, and Munarini [11] proved that Pell graphs are median graphs. They both used the following theorem by Mulder [10]:

[5] S. Klavzar, On median nature and enumerative properties of fibonacci-like cubes, Discrete Math. 299 (2005) 145–153.

Table[GraphData[{"Pell",n},"Median"],{n,9}]

Prism

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

Star

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

Transposition

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

Trapezohedron

Entity["Graph",{"Trapezohedron",n}]["Median"]

Wheel

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

Parametrized families compute

Book (subset of stacked book)

And@@Monitor[MedianGraphQ[GraphData[g=#]]&/@GraphData["Book"],g]//Timing

FibonacciCube

GraphData["FibonacciCube"]

And@@Monitor[MedianGraphQ[GraphData[g=#]]&/@Take[SortBy[GraphData["FibonacciCube"],GraphData[#,"V"]&],11],g]//Timing

Gear (for n > 3)

Monitor[MedianGraphQ[GraphData[g=#]]&/@GraphData["Gear"],g]//Timing

Grid

Hypercube

GraphData["Hypercube"]

And@@Monitor[MedianGraphQ[GraphData[g=#]]&/@Take[SortBy[GraphData["Hypercube"],GraphData[#,"V"]&],8],g]//Timing

Ladder (subset of stacked book)

And@@Monitor[MedianGraphQ[GraphData[g=#]]&/@GraphData["Ladder"],g]//Timing

Path (subset of tree)

And@@Monitor[MedianGraphQ[GraphData[g=#]]&/@GraphData["Path"],g]//Timing

Polyomino

And@@Monitor[MedianGraphQ[GraphData[g=#]]&/@GraphData["Polyomino*"],g]//Timing

StackedBook

And@@Monitor[MedianGraphQ[GraphData[g=#]]&/@GraphData["StackedBook"],g]//Timing

Star (subset of tree)

And@@Monitor[MedianGraphQ[GraphData[g=#]]&/@GraphData["Star"],g]//Timing

Tree

And@@Monitor[MedianGraphQ[GraphData[g=#]]&/@GraphData["Tree"],g]//Timing