Complement Odd Chordless Cycle Polynomial

Author

Eric W. Weisstein
March 2, 2023

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

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

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

Parametrized families

<<MathWorld`Graphs`

Andrasfai

(poly=Table[GraphData[{"Andrasfai",n},"ComplementOddChordlessCyclePolynomial"],{n,k0=1,10}]/.f_Function:>f[x])//Column

DeleteMissing[Rest[seq]][[All,1,2]]

FindSequenceFunction[%,n-1]//Factor

Binomial[n+2,4](3n-1)/5

Antiprism

Entity["Graph",{"Antiprism",n}]["ComplementOddChordlessCyclePolynomial"][x]

(poly=Table[GraphData[{"Antiprism",n},"ComplementOddChordlessCyclePolynomial"],{n,k0=3,25}]/.f_Function:>f[x])

(poly=Table[GraphData[{"Antiprism",n},"ComplementOddChordlessCyclePolynomial"],{n,k0=3,20}]/.f_Function:>f[x])

Apollonian

(poly=Table[GraphData[{"Apollonian",n},"ComplementOddChordlessCyclePolynomial"],{n,6}])

Barbell

(poly=Table[GraphData[{"Barbell",n},"ComplementOddChordlessCyclePolynomial"],{n,3,20}])

Bishop n×n

(poly=Table[GraphData[{"Bishop",{n,n}},"ComplementOddChordlessCyclePolynomial"],{n,10}])

BlackBishop n×n

(poly=Table[GraphData[{"BlackBishop",{n,n}},"ComplementOddChordlessCyclePolynomial"],{n,10}])

Book

(poly=Table[GraphData[{"Book",n},"ComplementOddChordlessCyclePolynomial"],{n,20}])

CocktailParty

(poly=Table[GraphData[{"CocktailParty",n},"ComplementOddChordlessCyclePolynomial"],{n,20}])

Complete

Entity["Graph",{"Complete",n}]["ComplementOddChordlessCyclePolynomial"][x]

(poly=Table[GraphData[{"Complete",n},"ComplementOddChordlessCyclePolynomial"],{n,20}])

CompleteBipartite m×n

Entity["Graph",{"CompleteBipartite",{m,n}}]["ComplementOddChordlessCyclePolynomial"][x]

Table[
GraphData[{"CompleteBipartite",{m,n}},"ComplementOddChordlessCyclePolynomial"],{n,20},{m,n}]//Column//TraditionalForm

CompleteBipartite n×n

Entity["Graph",{"CompleteBipartite",{n,n}}]["ComplementOddChordlessCyclePolynomial"][x]

(poly=Table[GraphData[{"CompleteBipartite",{n,n}},"ComplementOddChordlessCyclePolynomial"],{n,10}])

CompleteTripartite k×m×n

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

(poly=Table[GraphData[{"CompleteTripartite",{k,m,n}},"ComplementOddChordlessCyclePolynomial"],{n,5},{m,n},{k,m}]/.f_Function:>f[x])//Column

CompleteTripartite n×n×n

Entity["Graph",{"CompleteTripartite",{n,n,n}}]["ComplementOddChordlessCyclePolynomial"][x]

(poly=Table[GraphData[{"CompleteTripartite",{n,n,n}},"ComplementOddChordlessCyclePolynomial"],{n,10}])

CrossedPrism

(poly=Table[GraphData[{"CrossedPrism",2n},"ComplementOddChordlessCyclePolynomial"],{n,k0=3,10}])

Crown

(poly=Table[GraphData[{"Crown",n},"ComplementOddChordlessCyclePolynomial"],{n,3,20}])

CubeConnectedCycle

Entity["Graph",{"CubeConnectedCycle",n}]["ComplementOddChordlessCyclePolynomial"][x]

(poly=Table[GraphData[{"CubeConnectedCycle",n},"ComplementOddChordlessCyclePolynomial"],{n,k0=3,8}]/.f_Function:>f[x])//Column

Do[
Print[{gn=GraphData[{"CubeConnectedCycle",n},"#"],OddChordlessCyclePolynomial[GraphComplement[GraphData[gn]],x]//Timing}],{n,3,8}]

Cycle

Entity["Graph",{"Cycle",n}]["ComplementOddChordlessCyclePolynomial"][x]

(poly=Table[GraphData[{"Cycle",n},"ComplementOddChordlessCyclePolynomial"],{n,k0=3,20}]/.f_Function:>f[x])

DiagonalIntersection

(poly=Table[GraphData[{"DiagonalIntersection",n},"ComplementOddChordlessCyclePolynomial"],{n,k0=3,14}]/.f_Function:>f[x])//Column

Do[
Print[{gn=GraphData[{"DiagonalIntersection",n},"#"],OddChordlessCyclePolynomial[GraphComplement[GraphData[gn]],x]//Timing}],{n,3,14}]

Dipyramid

(poly=Table[GraphData[{"Dipyramid",n},"ComplementOddChordlessCyclePolynomial"],{n,k0=3,20}]/.f_Function:>f[x])//Column

Empty

Entity["Graph",{"Empty",n}]["ComplementOddChordlessCyclePolynomial"][x]

(poly=Table[GraphData[{"Empty",n},"ComplementOddChordlessCyclePolynomial"],{n,30}]/.f_Function:>f[x])

FibonacciCube

(poly=Table[GraphData[{"FibonacciCube",n},"ComplementOddChordlessCyclePolynomial"],{n,15}])

FoldedCube

(poly=Table[GraphData[{"FoldedCube",n},"ComplementOddChordlessCyclePolynomial"],{n,2,10}]/.f_Function:>f[x])

Do[
Print[{gn=GraphData[{"FoldedCube",n},"#"],OddChordlessCyclePolynomial[GraphComplement[GraphData[gn]],x]//Timing}],{n,2,10}]

Fiveleaper n×n

(poly=Table[GraphData[{"Fiveleaper",{n,n}},"ComplementOddChordlessCyclePolynomial"],{n,10}])

Gear

(poly=Table[GraphData[{"Gear",n},"ComplementOddChordlessCyclePolynomial"],{n,3,20}])

Grid m×n

Entity["Graph",{"Grid",{m,n}}]["ComplementOddChordlessCyclePolynomial"][x]

Table[GraphData[{"Grid",{m,n}},"ComplementOddChordlessCyclePolynomial"],{n,10},{m,n}]//Column

Grid n×n

Entity["Graph",{"Grid",{n,n}}]["ComplementOddChordlessCyclePolynomial"][x]

(poly=Table[GraphData[{"Grid",{n,n}},"ComplementOddChordlessCyclePolynomial"],{n,20}]/.f_Function:>f[x])

Grid k×m×n

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

(poly=Table[GraphData[{"Grid",{k,m,n}},"ComplementOddChordlessCyclePolynomial"],{n,5},{m,n},{k,m}])

Grid n×n×n

Entity["Graph",{"Grid",{n,n,n}}]["ComplementOddChordlessCyclePolynomial"][x]

(poly=Table[GraphData[{"Grid",{n,n,n}},"ComplementOddChordlessCyclePolynomial"],{n,10}])

HalvedCube

(poly=Table[GraphData[{"HalvedCube",n},"ComplementOddChordlessCyclePolynomial"],{n,10}]/.f_Function:>f[x])//Column

Table[3 (2^(n+1))Binomial[n,5](x^5),{n,10}]==poly

Do[
Print[{gn=GraphData[{"HalvedCube",n},"#"],OddChordlessCyclePolynomial[GraphComplement[GraphData[gn]],x]//Timing}],{n,10}]

Hanoi

(poly=Table[GraphData[{"Hanoi",n},"ComplementOddChordlessCyclePolynomial"],{n,5}])

Helm

(poly=Table[GraphData[{"Helm",n},"ComplementOddChordlessCyclePolynomial"],{n,3,20}]/.f_Function:>f[x])//Column

Hypercube

Entity["Graph",{"Hypercube",n}]["ComplementOddChordlessCyclePolynomial"][x]

(poly=Table[GraphData[{"Hypercube",n},"ComplementOddChordlessCyclePolynomial"],{n,0,10}])

Keller

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

(poly=Table[GraphData[{"Keller",n},"ComplementOddChordlessCyclePolynomial"],{n,5}]/.f_Function:>f[x])//Column

Do[
Print[{gn=GraphData[{"Keller",n},"#"],OddChordlessCyclePolynomial[GraphComplement[GraphData[gn]],x]//Timing}],{n,5}]

King m×n

(poly=Table[GraphData[{"King",{m,n}},"ComplementOddChordlessCyclePolynomial"],{n,10},{m,n}]/.f_Function:>f[x])//Column

King n×n

(poly=Table[GraphData[{"King",{n,n}},"ComplementOddChordlessCyclePolynomial"],{n,20}]/.f_Function:>f[x])

Knight m×n

Entity["Graph",{"Knight",{m,n}}]["ComplementOddChordlessCyclePolynomial"][x]

Table[GraphData[{"Knight",{m,n}},"ComplementOddChordlessCyclePolynomial"]/.f_Function:>f[x],{n,10},{m,n}]//Column//TraditionalForm

Knight n×n

Entity["Graph",{"Knight",{n,n}}]["ComplementOddChordlessCyclePolynomial"][x]

(poly=Table[GraphData[{"Knight",{n,n}},"ComplementOddChordlessCyclePolynomial"],{n,10}]/.f_Function:>f[x])

Ladder

Entity["Graph",{"Ladder",n}]["ComplementOddChordlessCyclePolynomial"][x]

(poly=Table[GraphData[{"Ladder",n},"ComplementOddChordlessCyclePolynomial"],{n,20}])

LadderRung

(poly=Table[GraphData[{"LadderRung",n},"ComplementOddChordlessCyclePolynomial"],{n,20}])

MengerSponge

(poly=Table[GraphData[{"MengerSponge",n},"ComplementOddChordlessCyclePolynomial"],{n,3}]/.f_Function:>f[x])

MoebiusLadder

Entity["Graph",{"MoebiusLadder",n}]["ComplementOddChordlessCyclePolynomial"][x]

(poly=Table[GraphData[{"MoebiusLadder",n},"ComplementOddChordlessCyclePolynomial"],{n,k0=3,25}]/.f_Function:>f[x])

Mycielski

A301769

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

(poly=Table[GraphData[{"Mycielski",n},"ComplementOddChordlessCyclePolynomial"],{n,11}]/.f_Function:>f[x])//Column

Do[Print[{gn=GraphData[{"Mycielski",n},"#"],OddChordlessCyclePolynomial[GraphComplement[GraphData[gn]],x,"MinValue"->5,"MaxValue"->5]//Timing}],{n,10}]

Odd

Entity["Graph",{"Odd",n}]["ComplementOddChordlessCyclePolynomial"][x]

(poly=Table[GraphData[{"Odd",n},"ComplementOddChordlessCyclePolynomial"],{n,7}]/.f_Function:>f[x])

Table[IndependenceNumber[GraphComplement[GraphData[{"Odd",n}]]],{n,7}]

Do[
Print[{gn=GraphData[{"Odd",n},"#"],OddChordlessCyclePolynomial[GraphComplement[GraphData[gn]],x]//Timing}],{n,7}]

Pan

(poly=Table[GraphData[{"Pan",n},"ComplementOddChordlessCyclePolynomial"],{n,3,20}]/.f_Function:>f[x])//Column

Pasechnik

(poly=Table[GraphData[{"Pasechnik",n},"ComplementOddChordlessCyclePolynomial"],{n,5}]/.f_Function:>f[x])//Column

Path

Entity["Graph",{"Path",n}]["ComplementOddChordlessCyclePolynomial"][x]

(poly=Table[GraphData[{"Path",n},"ComplementOddChordlessCyclePolynomial"],{n,20}])

Prism

Entity["Graph",{"Prism",n}]["ComplementOddChordlessCyclePolynomial"][x]

(poly=Table[GraphData[{"Prism",n},"ComplementOddChordlessCyclePolynomial"],{n,k0=3,25}]/.f_Function:>f[x])

Queen n×n

(poly=Table[GraphData[{"Queen",{n,n}},"ComplementOddChordlessCyclePolynomial"],{n,20}]/.f_Function:>f[x])//Column

poly={0,0,0,24 (x^5)+24 (x^7),560 (x^5)+136 (x^7),3968 (x^5)+456 (x^7),15240 (x^5)+1056 (x^7),44136 (x^5)+1960 (x^7),102768 (x^5)+3304 (x^7),214784 (x^5)+5056 (x^7),402968 (x^5)+7416 (x^7),706776 (x^5)+10272 (x^7),1167088 (x^5)+13904 (x^7),1844176 (x^5)+18176 (x^7),2795800 (x^5)+23144 (x^7),4112048 (x^5)+29112 (x^7),5873488 (x^5)+36128 (x^7),8198408 (x^5)+44008 (x^7),11197592 (x^5)+52968 (x^7),15023856 (x^5)+62888 (x^7),19817976 (x^5)+74320 (x^7),25776240 (x^5)+87008 (x^7),33071984 (x^5)+100848 (x^7),41943680 (x^5)+115840 (x^7),52610352 (x^5)+132632 (x^7),65356872 (x^5)+151200 (x^7),80441352 (x^5)+171192 (x^7),98207720 (x^5)+192696 (x^7)};

FindLinearRecurrence[DeleteMissing@poly]//Head//Timing

FindGeneratingFunction[DeleteMissing@poly,z]//Head//Timing

cc5=Coefficient[DeleteMissing[poly],x,5]

Do[Print[{k,FindLinearRecurrence[DeleteMissing@Drop[cc5,k]]//Head//Timing}],{k,0,5}]

FindSequenceFunction[cc5,n]//Head//Timing

FindGeneratingFunction[cc5,x]//Head//Timing

cc7=Coefficient[DeleteMissing[poly],x,7]

Do[Print[{k,FindLinearRecurrence[DeleteMissing@Drop[cc7,k]]//Head//Timing}],{k,0,5}]

FindSequenceFunction[cc7,n]//Head//Timing

FindGeneratingFunction[cc7,x]//Head//Timing

Do[
Print[{gn=GraphData[{"Queen",{n,n}},"#"],OddChordlessCyclePolynomial[GraphComplement[GraphData[gn]],x,"MinValue"->7,"MaxValue"->7]//Timing}],{n,20}]

Rook m×n

(poly=Table[GraphData[{"Rook",{m,n}},"ComplementOddChordlessCyclePolynomial"],{n,10},{m,n}]/.f_Function:>f[x])//Column

Rook n×n

(poly=Table[GraphData[{"Rook",{n,n}},"ComplementOddChordlessCyclePolynomial"],{n,10}])

RookComplement n×n

(poly=Table[GraphData[{"RookComplement",{n,n}},"ComplementOddChordlessCyclePolynomial"],{n,10}])

SierpinskiCarpet

(poly=Table[GraphData[{"SierpinskiCarpet",n},"ComplementOddChordlessCyclePolynomial"],{n,4}]/.f_Function:>f[x])

SierpinskiSieve

(poly=Table[GraphData[{"SierpinskiSieve",n},"ComplementOddChordlessCyclePolynomial"],{n,5}]/.f_Function:>f[x])

SierpinskiTetrahedron

(poly=Table[GraphData[{"SierpinskiTetrahedron",n},"ComplementOddChordlessCyclePolynomial"],{n,6}]/.f_Function:>f[x])

Do[
Print[{gn=GraphData[{"SierpinskiTetrahedron",n},"#"],OddChordlessCyclePolynomial[GraphComplement[GraphData[gn]],x]//Timing}],{n,6}]

Star

Entity["Graph",{"Star",n}]["ComplementOddChordlessCyclePolynomial"][x]

(poly=Table[GraphData[{"Star",n},"ComplementOddChordlessCyclePolynomial"],{n,25}])

Sun

(poly=Table[GraphData[{"Sun",n},"ComplementOddChordlessCyclePolynomial"],{n,3,20}])

Sunlet

(poly=Table[GraphData[{"Sunlet",n},"ComplementOddChordlessCyclePolynomial"],{n,k0=3,20}]/.f_Function:>f[x])//Column

Tetrahedral

(poly=Table[GraphData[{"Tetrahedral",n},"ComplementOddChordlessCyclePolynomial"],{n,6,10}]/.f_Function:>f[x])//Column

Do[
Print[{gn=GraphData[{"Tetrahedral",n},"#"],OddChordlessCyclePolynomial[GraphComplement[GraphData[gn]],x]//Timing}],{n,6,10}]

Transposition

Entity["Graph",{"Transposition",n}]["ComplementOddChordlessCyclePolynomial"][x]

(poly=Table[GraphData[{"Transposition",n},"ComplementOddChordlessCyclePolynomial"],{n,6}])

Triangular

(poly=Table[GraphData[{"Triangular",n},"ComplementOddChordlessCyclePolynomial"],{n,2,20}]/.f_Function:>f[x])//Column

Table[12Binomial[n,5](x^5),{n,2,20}]==poly

Do[
Print[{gn=GraphData[{"Triangular",n},"#"],OddChordlessCyclePolynomial[GraphComplement[GraphData[gn]],x]//Timing}],{n,2,20}]

TriangularGrid

(poly=Table[GraphData[{"TriangularGrid",n},"ComplementOddChordlessCyclePolynomial"],{n,0,10}])

TriangularHoneycombAcuteKnight

(poly=Table[GraphData[{"TriangularHoneycombAcuteKnight",n},"ComplementOddChordlessCyclePolynomial"],{n,20}]/.f_Function:>f[x])

Do[
Print[{gn=GraphData[{"TriangularHoneycombAcuteKnight",n},"#"],OddChordlessCyclePolynomial[GraphComplement[GraphData[gn]],x]//Timing}],{n,20}]

TriangularHoneycombBishop

(poly=Table[GraphData[{"TriangularHoneycombBishop",n},"ComplementOddChordlessCyclePolynomial"],{n,9}]/.f_Function:>f[x])

TriangularHoneycombObtuseKnight

(poly=Table[GraphData[{"TriangularHoneycombObtuseKnight",n},"ComplementOddChordlessCyclePolynomial"],{n,20}]/.f_Function:>f[x])

TriangularHoneycombQueen

(poly=Table[GraphData[{"TriangularHoneycombQueen",n},"ComplementOddChordlessCyclePolynomial"],{n,10}]/.f_Function:>f[x])

Do[
Print[{gn=GraphData[{"TriangularHoneycombQueen",n},"#"],OddChordlessCyclePolynomial[GraphComplement[GraphData[gn]],x]//Timing}],{n,10}]

TriangularHoneycombRook

(poly=Table[GraphData[{"TriangularHoneycombRook",n},"ComplementOddChordlessCyclePolynomial"],{n,10}]/.f_Function:>f[x])

Web

(poly=Table[GraphData[{"Web",n},"ComplementOddChordlessCyclePolynomial"],{n,k0=4,20}]/.f_Function:>f[x])

Wheel

Entity["Graph",{"Wheel",n}]["ComplementOddChordlessCyclePolynomial"][x]

(poly=Table[GraphData[{"Wheel",n},"ComplementOddChordlessCyclePolynomial"],{n,4,20}]/.f_Function:>f[x])

WhiteBishop n×n

(poly=Table[GraphData[{"WhiteBishop",{n,n}},"ComplementOddChordlessCyclePolynomial"],{n,2,10}]/.f_Function:>f[x])

Checks

<<MathWorld`Graphs`

(bad=DeleteCases[
Monitor[{
gn=#,
GraphData[#,"ComplementOddChordlessCyclePolynomial"]/.f_Function:>f[x],
TimeConstrained[
OddChordlessCyclePolynomial[GraphComplement@GraphData[#],x],
60]
}&/@Select[
GraphData[All],
!MissingQ[GraphData[#,"ChordlessCyclePolynomial"]]&
],gn],
{_,x_,x_}
])//Timing

Cases[bad,{_,_,$Aborted}]

l={#,{0,#3}}&@@@DeleteCases[bad,{_,_Missing,_}|{_,_,$Aborted}]

PropertyReplace[l,"ComplementOddChordlessCycles"]

RenameGraphFiles[]