Graph Bridge

Author

Eric W. Weisstein
December 1, 2018

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

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

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

Initialization

Figure

SortBy[GraphData[{"Bridged","Connected"},;;6],GraphData[#,"V"]&]

GraphData["ClawGraph"]

Bridges[GraphData["ClawGraph"]]

Bridges[Graph["ClawGraph"]]

CombinatoricaGraphToV8Graph@Graph[{{{1, 5}}, {{1, 6}}, {{2, 5}}, {{3, 6}}, 
  {{4, 6}}, {{5, 6}}}, 
 {{{0.5000000000000001, 0.8660254037844386}}, 
  {{-0.49999999999999983, 0.8660254037844387}}, 
  {{-1., 0}}, {{-0.5000000000000004, 
    -0.8660254037844384}}, 
  {{0.49999999999999933, -0.866025403784439}}, 
  {{1., 0}}}]

Position[Length/@Bridges/@Graphs[6],3,{1}]

InputForm[g=Graphs[6][[21]]]

ShowGraph[Highlight[g,List/@Bridges[g],HighlightedEdgeColors->{Black}]]

Examples

GraphicsGrid[Partition[Show[GraphData[#],PlotLabel->#]&/@GraphData["Bridged",;;6],UpTo[10]],Dividers->All,ImageSize->1000]

Compute

gn={"P2",{"LadderRung",2},{6,28},{"Barbell",3}};

gs=GraphData[#,"Graph","Labeled"]&/@gn

GraphData

GraphData[#,"Bridges"]&/@gn

Bridges

Bridges/@gs

FindMinimumCut

Select[Sort[Sort/@KVertexConnectedComponents[#,2]],Length[#]==2&]&/@gs

Parametrized families

Andrasfai

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

Antelope n×n

Table[GraphData[{"Antelope",{n,n}},"Connected"],{n,10}]

seq=Table[GraphData[{"Antelope",{n,n}},"BridgeCount"],{n,10}]

Antiprism

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

seq=Table[GraphData[{"Antiprism",n},"BridgeCount"],{n,3,20}]

Apollonian

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

Barbell

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

Bishop n×n

seq=Table[GraphData[{"Bishop",{n,n}},"BridgeCount"],{n,10}]

BlackBishop m×n

Table[GraphData[{"BlackBishop",{m,n}},"BridgeCount"],{n,10},{m,n}]//Column

BlackBishop n×n

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

Book

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

Bruhat

seq=Table[GraphData[{"Bruhat",n},"BridgeCount"],{n,6}]

Centipede

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

FindSequenceFunction[DeleteMissing@seq,n]//FullSimplify

CocktailParty

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

Complete

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

seq=Table[GraphData[{"Complete",n},"BridgeCount"],{n,20}]

CompleteBipartite m×n

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

DeleteCases[Flatten[Table[{{m,n},GraphData[{"CompleteBipartite",{m,n}},"BridgeCount"],Piecewise[{{Max[m, n], Min[m, n] == 1}}, 0]},{n,20},{m,n}],1],{_,x_,x_}]

CompleteBipartite n×n

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

seq=Table[GraphData[{"CompleteBipartite",{n,n}},"BridgeCount"],{n,20}]

CompleteTripartite k×m×n

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

DeleteCases[Flatten[Table[{{m,n},GraphData[{"CompleteTripartite",{k,m,n}},"BridgeCount"],0},{n,10},{m,n},{k,m}],2],{_,x_,x_}]

CompleteTripartite n×n×n

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

seq=Table[GraphData[{"CompleteTripartite",{n,n,n}},"BridgeCount"],{n,10}]

CrossedPrism

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

Crown

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

CubeConnectedCycle

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

seq=Table[GraphData[{"CubeConnectedCycle",n},"BridgeCount"],{n,3,8}]

Cycle

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

seq=Table[GraphData[{"Cycle",n},"BridgeCount"],{n,3,20}]

DiagonalIntersection

seq=Table[GraphData[{"DiagonalIntersection",n},"BridgeCount"],{n,3,14}]

Dipyramid

seq=Table[GraphData[{"Dipyramid",n},"BridgeCount"],{n,3,10}]

Empty

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

seq=Table[GraphData[{"Empty",n},"BridgeCount"],{n,30}]

FibonacciCube

seq=Table[GraphData[{"FibonacciCube",n},"BridgeCount"],{n,15}]

Fiveleaper n×n

seq=Table[GraphData[{"Fiveleaper",{n,n}},"BridgeCount"],{n,10}]

Gear

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

GeneralizedPetersen

Sort[{"GeneralizedPetersen"/.GraphData[#,"NotationRules"],GraphData[#,"BridgeCount"]}&/@GraphData["GeneralizedPetersen"]]

DeleteCases[%,{_,0}]

Grid 3×n

Entity["Graph",{"Grid",{3,n}}]["BridgeCount"]

seq=Table[GraphData[{"Grid",Sort[{3,n}]},"BridgeCount"],{n,10}]

Grid m×n

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

DeleteCases[Flatten[Table[{{m,n},GraphData[{"Grid",{m,n}},"BridgeCount"],Piecewise[{{Max[m, n]-1, Min[m, n] == 1}}, 0]},{n,10},{m,n}],1],{_,x_,x_}]

Grid n×n

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

seq=Table[GraphData[{"Grid",{n,n}},"BridgeCount"],{n,10}]

Grid k×m×n

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

DeleteCases[Flatten[Table[{{k,m,n},GraphData[{"Grid",{k,m,n}},"BridgeCount"],Piecewise[{{Max[k,m, n]-1, k m n===Max[k,m,n]}}, 0]},{n,5},{m,n},{k,m}],2],{_,x_,x_}]

Grid n×n×n

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

seq=Table[GraphData[{"Grid",{n,n,n}},"BridgeCount"],{n,10}]

HalvedCube

seq=Table[GraphData[{"HalvedCube",n},"BridgeCount"],{n,10}]

Hanoi

seq=Table[GraphData[{"Hanoi",n},"BridgeCount"],{n,5}]

Helm

seq=Table[GraphData[{"Helm",n},"BridgeCount"],{n,3,20}]

Hypercube

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

seq=Table[GraphData[{"Hypercube",n},"BridgeCount"],{n,0,10}]

Keller

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

seq=Table[GraphData[{"Keller",n},"BridgeCount"],{n,5}]

King 2×n

seq=Table[GraphData[{"King",Sort[{2,n}]},"BridgeCount"],{n,10}]

King m×n

Table[GraphData[{"King",{m,n}},"BridgeCount"],{n,10},{m,n}]//Column

King n×n

seq=Table[GraphData[{"King",{n,n}},"BridgeCount"],{n,10}]

Knight m×n

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

DeleteCases[Flatten[Table[{{m,n},GraphData[{"Knight",{m,n}},"BridgeCount"],Piecewise[{{-4 + 2Max[m, n], Min[m, n] == 2}}, 0]},{n,10},{m,n}],1],{_,x_,x_}]

Knight n×n

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

seq=Table[GraphData[{"Knight",{n,n}},"BridgeCount"],{n,20}]

Ladder

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

seq=Table[GraphData[{"Ladder",n},"BridgeCount"],{n,20}]

LadderRung

seq=Table[GraphData[{"LadderRung",n},"BridgeCount"],{n,20}]

FindSequenceFunction[DeleteMissing@seq,n]

MoebiusLadder

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

seq=Table[GraphData[{"MoebiusLadder",n},"BridgeCount"],{n,3,20}]

Mycielski

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

seq=Table[GraphData[{"Mycielski",n},"BridgeCount"],{n,11}]

Odd

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

seq=Table[GraphData[{"Odd",n},"BridgeCount"],{n,7}]

Pan

seq=Table[GraphData[{"Pan",n},"BridgeCount"],{n,3,20}]

Path

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

seq=Table[GraphData[{"Path",n},"BridgeCount"],{n,20}]

PathComplement

seq=Table[GraphData[{"PathComplement",n},"BridgeCount"],{n,20}]

Prism

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

seq=Table[GraphData[{"Prism",n},"BridgeCount"],{n,3,25}]

Queen m×n

DeleteCases[Flatten[Table[{{m,n},GraphData[{"Queen",{m,n}},"BridgeCount"],Piecewise[{{1,m n==2}},0]},{n,10},{m,n}],1],{_,x_,x_}]

Queen n×n

seq=Table[GraphData[{"Queen",{n,n}},"BridgeCount"],{n,10}]

Rook n×n

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

RookComplement  n×n

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

StackedBook n×n

seq=Table[GraphData[{"StackedBook",{n,n}},"BridgeCount"],{n,10}]

Star

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

seq=Table[GraphData[{"Star",n},"BridgeCount"],{n,20}]

Sun

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

Sunlet

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

Tetrahedral

seq=Table[GraphData[{"Tetrahedral",n},"BridgeCount"],{n,6,10}]

TorusGrid n×n

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

Transposition

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

seq=Table[GraphData[{"Transposition",n},"BridgeCount"],{n,6}]

Triangular

seq=Table[GraphData[{"Triangular",n},"BridgeCount"],{n,2,10}]

TriangularGrid

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

TriangularHoneycombAcuteKnight

seq=Table[GraphData[{"TriangularHoneycombAcuteKnight",n},"BridgeCount"],{n,20}]

TriangularHoneycombBishop

seq=Table[GraphData[{"TriangularHoneycombBishop",n},"BridgeCount"],{n,9}]

TriangularHoneycombObtuseKnight

seq=Table[GraphData[{"TriangularHoneycombObtuseKnight",n},"BridgeCount"],{n,20}]

TriangularHoneycombQueen

seq=Table[GraphData[{"TriangularHoneycombQueen",n},"BridgeCount"],{n,10}]

TriangularHoneycombRook

seq=Table[GraphData[{"TriangularHoneycombRook",n},"BridgeCount"],{n,10}]

Web

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

Wheel

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

seq=Table[GraphData[{"Wheel",n},"BridgeCount"],{n,4,20}]

WhiteBishop n×n

seq=Table[GraphData[{"WhiteBishop",{n,n}},"BridgeCount"],{n,2,10}]

Check

Bridges

DeleteCases[Monitor[{gn=#,GraphData[#,"Bridges"],Bridges[GraphData[#]]}&/@GraphData[All],gn],{_,x_,x_}]//Timing