Irregularity Strength

Author

Eric W. Weisstein
July 2, 2024

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

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

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

Definition

G. Chartrand, M.S. Jacobson, J. Lehel, O.R. Oellermann, S. Ruiz, F. Saba, Irregular networks, Congr. Numer. 64 (1988) 197–210.

https://arxiv.org/abs/2406.09584

Bounds

Jacobson-Lehel bound

Bohman, T. and Kravitz, D.  "On the Irregularity Strength of Trees."  J. Graph Th. 45, 241–254, 2004.

[2] G. Chartrand, M. S. Jacobsen, J. Lehel, O. R. Oellermann, S. Ruiz, and F. Saba, Irregular networks, Congress Numerantium, 64 (1988), pp 187–192.

[does not actually seem to be proven there]

Dinitz, J. H.; Garnick, D. K.; and Gyárfás, A.  "On the Irregularity Strength of the m×n Grid."  J. Graph Th. 16, 355--374, 1992.

https://cpb-us-w2.wpmucdn.com/sites.udel.edu/dist/3/7714/files/2022/02/IrregularityStrengths.pdf

[10] M.S. Jacobson and J. Lehel, A bound for the strength of an irregular network. Preprint.

Ebert, G.; Hammenter, J.; Lazebnik, F.; and Woldar, A.  "Irregularity Strengths for Certain Graphs."  Congr. Numer. 71, 39–52, 1990.

https://cpb-us-w2.wpmucdn.com/sites.udel.edu/dist/3/7714/files/2022/02/IrregularityStrengths.pdf

[13] M.S. Jacobson and J. Lehel, A bound for the strength of an irregular network. Submitted.

Select[
DeleteCases[
{
#,
GraphData[#,"IrregularityStrength"],
IrregularityLambda[GraphData[#]]
}&/@GraphData[All],
{_,_Missing,_}
],
#[[2]]<#[[1]]&
]

Chartrand bound s(G)≥(max_(1≤i≤Δ))(((Subscript[n, i])+i-1)/i) for connected graphs with |G|>=3

(Abs[G])

Chartrand et al.

https://www.researchgate.net/publication/265701559_Irregular_networks

Ba\v ca, M.; Imran, M.; and Semani\v cov\'a-Fe\v nov\v cíkov\'a', A.  ``Irregularity and Modular Irregularity Strength of Wheels.''  {\it Mathematics} {\bf 9}, 2710, 2021.

https://www.mdpi.com/2227-7390/9/21/2710#B9-mathematics-09-02710

Select[
{
#,
#2,
Max[Function[{i,n},((n+i-1)/i)]@@@Tally[GraphData[#,"VertexDegrees"]]]
}&@@@DeleteCases[{#,GraphData[#,"IrregularityStrength"]}&/@GraphData["Connected",2;;],{_,∞}],
#[[2]]<#[[3]]&]

<<MathWorld`Graphs`

Select[
{
#,
#2,
ChartrandIrregularityBound[GraphData[#]]
}&@@@DeleteCases[{#,GraphData[#,"IrregularityStrength"]}&/@GraphData["Connected",2;;],{_,∞}],
#[[2]]<#[[3]]&]

Compare bounds

data=DeleteCases[
Monitor[{
gn=#,
GraphData[#,"IrregularityStrength"],
ChartrandIrregularityBound[GraphData[#]],IrregularityLambda[GraphData[#]]
}&/@GraphData["Connected",2;;20],
gn],
{_,x_,x_,x_}|{_,Infinity,_,_}|{_,_Missing,_,_}];//Timing

Select[data,#[[3]]<#[[2]]&]

(diff={#,#4-#3}&@@@data)[[All,2]]//Union

Cases[diff,{gn_,1}:>gn]

Cases[diff,{gn_,2}:>gn]

GraphDataCountTable

GraphDataCountTable["IrregularityStrength",Join[{
"Antiprism"->110654,"CompleteBipartite"->010702,"Cycle"->004525,"Hypercube"->373895,"Pan"->4525,"Path"->004524,"Wheel"->008620},
Thread[{"CocktailParty","Complete","CycleComplement"}->010701],
Thread[{"Centipede","Star"}->000027]
]]

Parametrized families

<<MathWorld`Graphs`

Alkane

seq=Table[GraphData[{"Alkane",n},"IrregularityStrength"],{n,10}]

AlternatingGroupGraph

seq=Table[GraphData[{"AlternatingGroupGraph",n},"IrregularityStrength"],{n,2,6}]

Andrasfai

seq=Table[GraphData[{"Andrasfai",n},"IrregularityStrength"],{n,20}]

Do[Print[{gn={"Andrasfai",n},IrregularityStrength[GraphData[gn],Method->"NextTuple"]//Timing}],{n,2,6}]

Antelope n×n

seq=Table[GraphData[{"Antelope",{n,n}},"IrregularityStrength"],{n,20}]

Antiprism

A110654

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

Anholcer, M. and Palmer, C.  "Irregular Labellings of Circulant Graphs."  Discr. Math. 312, 3461–3466, 2012.

seq=Table[GraphData[{"Antiprism",n},"IrregularityStrength"],{n,3,25}]

Table[Ceiling[((2n+3)/4)],{n,3,25}]

Table[Ceiling[n/2]+1,{n,3,25}]

Table[Subtract@@{Ceiling[((2n+3)/4)],1+Ceiling[n/2]},{n,100}]//Union

GraphData[{"Antiprism",6},"NotationRules","Circulant"]

new={#,GraphData[#,"IrregularityStrength"],Ceiling[((#2[[1]]+3)/4)]}&@@@Cases[{#,GraphData[#,"NotationRules","Circulant"]}&/@GraphData["Circulant"],{_,{n_,{1,s2_}}/;n≥4s2+1}]

Do[Print[{gn={"Antiprism",n},IrregularityStrength[GraphData[gn],Method->"NextTuple"]//Timing}],{n,3,6}]

Apollonian

seq=Table[GraphData[{"Apollonian",n},"IrregularityStrength"],{n,5}]

Barbell

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

Do[Print[{gn={"Barbell",n},IrregularityStrength[GraphData[gn],Method->"NextTuple"]//Timing}],{n,3,6}]

BlackBishop n×n

seq=Table[GraphData[{"BlackBishop",{n,n}},"IrregularityStrength"],{n,20}]

Do[Print[{gn={"BlackBishop",{n,n}},IrregularityStrength[GraphData[gn],Method->"NextTuple"]//Timing}],{n,3,6}]

Bishop n×n

seq=Table[GraphData[{"Bishop",{n,n}},"IrregularityStrength"],{n,20}]

Book

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

Bruhat

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

Camel n×n

seq=Table[GraphData[{"Camel",{n,n}},"IrregularityStrength"],{n,20}]

Centipede

Inferred for n > 6:

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

Do[Print[{gn={"Centipede",n},IrregularityStrength[GraphData[gn],Method->"NextTuple"]//Timing}],{n,6}]

CocktailParty

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

Anholcer, M. and Palmer, C.  "Irregular Labellings of Circulant Graphs."  Discr. Math. 312, 3461–3466, 2012.

cyclepowers=Cases[{#,GraphData[#,"NotationRules","Circulant"]}&/@GraphData["CocktailParty"],{gn_,{n_,l_List}/;(l==Range[Length[l]]&&Length[l]≥2&&n>2Length[l]+1)}:>{gn,n,Length[l]}]

vals={#,GraphData[#,"IrregularityStrength"],Ceiling[((#2+2#3-1)/(2#3))]+Boole[#2==2#3+1||(Mod[#3,2]==1&&Mod[#2,4#3]==2#3+1)]}&@@@cyclepowers

Cases[vals,{_,_Missing,_}]

Do[Print[{gn={"CocktailParty",n},IrregularityStrength[GraphData[gn],Method->"NextTuple"]//Timing}],{n,2,4}]

Circulant

Anholcer, M.\ and Palmer, C.  ``Irregular Labellings of Circulant Graphs.''  {\it Discr.\ Math.} {\bf 312}, 3461--3466, 2012.\par

new={#,GraphData[#,"IrregularityStrength"],Ceiling[((#2[[1]]+3)/4)]}&@@@Cases[{#,GraphData[#,"NotationRules","Circulant"]}&/@GraphData["Circulant"],{_,{n_,{1,s2_}}/;n≥4s2+1}]

DeleteCases[new,{_,_Missing,_}]

Complete

A010701

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

Chartrand et al.

https://www.researchgate.net/publication/265701559_Irregular_networks

Amar, D.  "Irregularity Strength of Regular Graphs of Large Degree."  Disc. Math. 114, 9–17, 1993.

seq=Table[GraphData[{"Complete",n},"IrregularityStrength"],{n,30}]

Do[Print[{{"Complete",n},IrregularityStrength[CompleteGraph[n],Method->"NextTuple"]//Timing}],{n,7}]

CompleteBipartite n×n

A010702

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

Amar, D.  "Irregularity Strength of Regular Graphs of Large Degree."  Disc. Math. 114, 9–17, 1993.

Faudree, R.; Jacobson, M.; Lehel, J.; and Schelp, R.  ``Irregular Networks, Regular Graphs and Integer Matrices With Distinct Row and Column Sums.''
  {\it Disc.\ Math.} {\bf 76},) 223--240, 1989.\par

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

Table[Piecewise[{{Infinity,n==1},{3,Mod[n,2]==0},{4,Mod[n,2]==1}}],{n,20}]==seq

CompleteBipartite m×n

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

Chartrand et al.

https://www.researchgate.net/publication/265701559_Irregular_networks

Amar, D.  "Irregularity Strength of Regular Graphs of Large Degree."  Disc. Math. 114, 9–17, 1993.

Faudree, R.; Jacobson, M.; Lehel, J.; and Schelp, R.  ``Irregular Networks, Regular Graphs and Integer Matrices With Distinct Row and Column Sums.''
  {\it Disc.\ Math.} {\bf 76},) 223--240, 1989.\par

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"CompleteBipartite",{m,n}},"IrregularityStrength"],
Piecewise[{
{Infinity,m==n==1},
{3,m==n&&Mod[n,2]==0},
{4,m==n&&Mod[n,2]==1},
{Ceiling[(m+n-1)/Min[m,n]],Max[m,n]≥2Min[m,n]},
{3,1<Max[m,n]/2≤Min[m,n]<Max[m,n]}
}]
},{n,20},{m,n}],1],{_,x_,x_}]

CompleteTripartite n×n×n

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

Inferred for n > 4:

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

Do[Print[{gn={"CompleteTripartite",{n,n,n}},IrregularityStrength[GraphData[gn],Method->"NextTuple"]//Timing}],{n,6}]

CompleteTripartite k×m×n

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

DeleteCases[Sort@DeleteCases[Flatten[Table[{
{k,m,n},
GraphData[{"CompleteTripartite",{k,m,n}},"IrregularityStrength"],
(k+m+n)/2
},{n,10},{m,n},{k,m}],2],{_,x_,x_}],{_,_Missing,_}]

CrossedPrism

seq=Table[GraphData[{"CrossedPrism",2n},"IrregularityStrength"],{n,2,12}]

Crown

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

Do[Print[{gn={"Crown",n},IrregularityStrength[GraphData[gn],Method->"NextTuple"]//Timing}],{n,6}]

CubeConnectedCycle

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

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

Cycle

A004525

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

Faudree, R.; Schelp, R.; Jacobson, M.; and Lehel, J. "Irregular Networks, Regular Graphs and Integer Matrices With Distinct Row and Column Sums.''
  Disc. Math. 76, 223–240, 1989.

seq=Table[GraphData[{"Cycle",n},"IrregularityStrength"],{n,3,30}]

Table[Piecewise[{{Ceiling[n/2],Mod[n,4]==1}},Ceiling[n/2]+1],{n,3,30}]

Do[Print[{gn={"Cycle",n},IrregularityStrength[GraphData[gn],Method->"NextTuple"]//Timing}],{n,3,9}]

Do[Print[{gn={"Cycle",n},IrregularityStrength[GraphData[gn],Method->"NextTuple"]//Timing}],{n,11,12}]

CycleComplement

seq=Table[GraphData[{"CycleComplement",n},"IrregularityStrength"],{n,3,20}]

DiagonalIntersection

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

Dipyramid

seq=Table[GraphData[{"Dipyramid",n},"IrregularityStrength"],{n,3,20}]

Do[Print[{gn={"Dipyramid",n},IrregularityStrength[GraphData[gn],Method->"NextTuple"]//Timing}],{n,3,6}]

Do[Print[{gn={"Dipyramid",n},IrregularityStrength[GraphData[gn],Method->"NextTuple"]//Timing}],{n,{7}}]

DorogovtsevGoltsevMendes

seq=Table[GraphData[{"DorogovtsevGoltsevMendes",n},"IrregularityStrength"],{n,0,7}]

DoubleCone

seq=Table[GraphData[{"DoubleCone",n},"IrregularityStrength"],{n,3,20}]

Do[Print[{gn={"DoubleCone",n},IrregularityStrength[GraphData[gn],Method->"NextTuple"]//Timing}],{n,3,6}]

Empty

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

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

FibonacciCube

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

Fiveleaper n×n

seq=Table[GraphData[{"Fiveleaper",{n,n}},"IrregularityStrength"],{n,20}]

Flower

seq=Table[GraphData[{"Flower",n},"IrregularityStrength"],{n,5,20}]

FoldedCube

seq=Table[GraphData[{"FoldedCube",n},"IrregularityStrength"],{n,2,10}]

Gear

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

Do[Print[{gn={"Gear",n},IrregularityStrength[GraphData[gn],Method->"NextTuple"]//Timing}],{n,3,6}]

GeneralizedPetersen

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

Jendrol', S. and \v Zoldák, V.  "The Irregularity Strength of Generalized Petersen Graphs."  Math. Slovaca 45, 107–113, 1995.

https://dml.cz/bitstream/handle/10338.dmlcz/136640/MathSlov_45-1995-2_1.pdf

Giraffe n×n

seq=Table[GraphData[{"Giraffe",{n,n}},"IrregularityStrength"],{n,20}]

Goldberg

seq=Table[GraphData[{"Goldberg",n},"IrregularityStrength"],{n,3,20}]

Grid n×n

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

seq=Table[GraphData[{"Grid",{n,n}},"IrregularityStrength"],{n,20}]

Grid m×n

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

Sort@DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"Grid",{m,n}},"IrregularityStrength"],
XXX
},{n,10},{m,n}],1],{_,x_,x_}]

Dinitz, J.~H.; Garnick, D.~K.; and Gy\'arf\'as, A.  ``On the Irregularity Strength of the $m\times n$ Grid.''  {\it J.\ Graph Th.} {\bf 16}, 355--374, 1992.

FeasibleRegionQ[x_,y_]:=2Floor[((x+2)/4)]+8≤y≤4Floor[(x/2)]-15

GridGraphIrregularityStrength[m_,n_]:=With[
{λ=IrregularityLambda@GridGraph[{m,n}]},
Piecewise[{
{λ,m==1&&n>2&&Mod[n,4]!=2},
{λ+1,m==1&&n>2&&Mod[n,4]==2},
{λ,m==2&&n>=2&&Mod[n,6]!=1},
{λ+1,m==2&&n>=2&&Mod[n,6]==1},
{λ,m==3&&n==5},
{λ,3≤m≤16&&3≤n≤16&&Mod[m n,4]!=3},
{λ+1,3≤m≤16&&3≤n≤16&&Mod[m n,4]==3},
{λ,FeasibleRegionQ[m,n]&&Mod[m n,4]!=3},
{λ+1,FeasibleRegionQ[m,n]&&Mod[m n,4]==3}
},Missing["NotAvailable"]]
]

grids=Select[GraphData["Grid",3;;],0<Length[GraphData[#,"NotationRules","Grid"]]<3&]

data={#,FirstCase[GraphData[#,"StandardNames"],{"Grid",{m_,n_}}:>{m,n}]}&/@grids

new=DeleteCases[{#,GraphData[#,"IrregularityStrength"],GridGraphIrregularityStrength@@#2}&@@@data,{_,x_,x_}]

l={#,{0,#3}}&@@@new

Grid n×n×n

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

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

Grid k×m×n

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

Sort@DeleteCases[Flatten[Table[{
{k,m,n},
GraphData[{"Grid",{k,m,n}},"IrregularityStrength"],
XXX
},{n,5},{m,n},{k,m}],2],{_,x_,x_}]

HalvedCube

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

Hanoi

seq=Table[GraphData[{"Hanoi",n},"IrregularityStrength"],{n,6}]

Do[Print[{gn={"Hanoi",n},IrregularityStrength[GraphData[gn],Method->"NextTuple"]//Timing}],{n,6}]

Helm

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

Table[{n,IrregularityLambda[HelmGraph[n]]},{n,3,10}]

Do[Print[{gn={"Helm",n},IrregularityStrength[GraphData[gn],Method->"NextTuple"]//Timing}],{n,3,6}]

Hypercube

A373895

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

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

Table[Piecewise[{{Missing["NotAvailable"],n==0},{Infinity,n==1}},Ceiling[(((2^n)+n-1)/n)]],{n,0,10}]==seq

Ebert, G.; Hammenter, J.; Lazebnik, F.; and Woldar, A.  "Irregularity Strengths for Certain Graphs."  Congr. Numer. 71, 39–52, 1990.

<<MathWorld`Graphs`

Table[{n,IrregularityLambda[HypercubeGraph[n]],Ceiling[(((2^n)+n-1)/n)]},{n,2,10}]

l=Table[Piecewise[{{Missing["NotAvailable"],n==0},{Infinity,n==1}},Ceiling[(((2^n)+n-1)/n)]],{n,2,20}]

FindSequenceFunction[l,n-1]//Head//Timing

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

FindLinearRecurrence[l]//Head//Timing

Table[Ceiling[(((2^n)+n-1)/n)],{n,40}]

Keller

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

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

King n×n

seq=Table[GraphData[{"King",{n,n}},"IrregularityStrength"],{n,20}]

King m×n

Entity["Graph",{"King",{m,n}}]["IrregularityStrength"]

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"King",{m,n}},"IrregularityStrength"],
XXX
},{n,10},{m,n}],1],{_,x_,x_}]

Knight n×n

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

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

Knight m×n

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

DeleteCases[Flatten[Table[{
{m,n},
GraphData[{"Knight",{m,n}},"IrregularityStrength"],
XXX
},{n,10},{m,n}],1],{_,x_,x_}]

Ladder

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

Ebert, G.; Hammenter, J.; Lazebnik, F.; and Woldar, A.  ``Irregularity Strengths for Certain Graphs.'' {\it Congressus Numerantium} {\bf 71}, 39--52, 1990.

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

Table[{n,IrregularityLambda[LadderGraph[n]],Ceiling[((2n+1)/3)]},{n,10}]

Table[Piecewise[{{Infinity,n==1},{3,n==2||n==3},{Ceiling[(2n+1)/3]+1,Mod[n,6]==1}},Ceiling[(2n+1)/3]],{n,20}]==seq

Do[Print[{gn={"Ladder",n},IrregularityStrength[GraphData[gn],Method->"NextTuple"]//Timing}],{n,10}]

LadderRung

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

LucasCube

seq=Table[GraphData[{"LucasCube",n},"IrregularityStrength"],{n,15}]

MengerSponge

seq=Table[GraphData[{"MengerSponge",n},"IrregularityStrength"],{n,3}]

MoebiusLadder

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

seq=Table[GraphData[{"MoebiusLadder",n},"IrregularityStrength"],{n,3,25}]

Table[IrregularityLambda[MoebiusLadder[n]],{n,3,25}]

Do[Print[{gn={"MoebiusLadder",n},IrregularityStrength[GraphData[gn],Method->"NextTuple"]//Timing}],{n,3,6}]

Mycielski

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

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

Odd

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

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

Pan

A004525

Inferred for n > 11:

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

Table[Floor[(n+1)/4]+Ceiling[(n+1)/4],{n,3,20}]==seq

Do[Print[{gn={"Pan",n},IrregularityStrength[GraphData[gn],Method->"NextTuple"]//Timing}],{n,3,11}]

Path

A004524

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

Chartrand et al.

https://www.researchgate.net/publication/265701559_Irregular_networks

Amar, D.  "Irregularity Strength of Regular Graphs of Large Degree."  Disc. Math. 114, 9–17, 1993.

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

Table[Piecewise[{{Missing["NotAvailable"],n==1},{Infinity,n==2}},Floor[(n+2)/4]+Floor[(n+3)/4]],{n,20}]==seq

Table[Round[(n+1)/2],{n,20}]

Table[Round[(n-1)/2],{n,0,20}]

Round[(Range[0,20]-1)/2]

Do[Print[{gn={"Path",n},IrregularityStrength[GraphData[gn],Method->"NextTuple"]//Timing}],{n,3,9}]

PathComplement

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

Do[Print[{gn={"PathComplement",n},IrregularityStrength[GraphData[gn],Method->"NextTuple"]//Timing}],{n,4,7}]

Pell

seq=Table[GraphData[{"Pell",n},"IrregularityStrength"],{n,9}]

Prism

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

Jendrol', S.\ and \v Zold\'ak, V.  ``The Irregularity Strength of Generalized Petersen Graphs.''  {\it Math.\ Slovaca} {\bf 45}, 107--113, 1995.\par

https://dml.cz/bitstream/handle/10338.dmlcz/136640/MathSlov_45-1995-2_1.pdf

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

GraphData[#,"NotationRules","GeneralizedPetersen"]&/@SortBy[GraphData["Prism"],GraphData[#,"V"]&]

seq=Table[Ceiling[((2(n+1))/3)]+Boole[Mod[n,6]==5],{n,3,25}]

FullSimplify[FindSequenceFunction[seq,n-2],n∈Integers]

Table[(1/18) (21-3 (((-1))^n)+12 n+3 Cos[((n π)/3)]-3 Cos[((2 n π)/3)]-3 (Sqrt[3]) Sin[((n π)/3)]+(Sqrt[3]) Sin[((2 n π)/3)]),{n,3,50}]

FindLinearRecurrence[seq]

gf=(x^3)FindGeneratingFunction[seq,x]

FullSimplify[SeriesCoefficient[gf,{x,0,n}],n>2&&n∈Integers]

Table[(1/6) (7-(((-1))^n)+4 n-ChebyshevU[n,-(1/2)]+Cos[((n π)/3)]-(Sqrt[3]) Sin[((n π)/3)]),{n,3,25}]

Table[(7-(-1)^n+4 n-ChebyshevU[n,-1/2]+Cos[n Pi/3]-Sqrt[3] Sin[n Pi/3])/6,{n,3,25}]

Table[(8-(-1)^n+4 n-Mod[n+2,3]+Cos[n Pi/3]-Sqrt[3] Sin[n Pi/3])/6,{n,3,25}]

Do[Print[{gn={"Prism",n},IrregularityStrength[GraphData[gn],Method->"NextTuple"]//Timing}],{n,3,6}]

Queen n×n

seq=Table[GraphData[{"Queen",{n,n}},"IrregularityStrength"],{n,20}]

Regular

Amar, D.  "Irregularity Strength of Regular Graphs of Large Degree."  Disc. Math. 114, 9–17, 1993.

Rook n×n

seq=Table[GraphData[{"Rook",{n,n}},"IrregularityStrength"],{n,20}]

RookComplement n×n

seq=Table[GraphData[{"RookComplement",{n,n}},"IrregularityStrength"],{n,20}]

SierpinskiCarpet

seq=Table[GraphData[{"SierpinskiCarpet",n},"IrregularityStrength"],{n,4}]

SierpinskiGasket

seq=Table[GraphData[{"SierpinskiGasket",n},"IrregularityStrength"],{n,7}]

SierpinskiTetrahedron

seq=Table[GraphData[{"SierpinskiTetrahedron",n},"IrregularityStrength"],{n,6}]

Spoke n×n

seq=Table[GraphData[{"Spoke",{n,n}},"IrregularityStrength"],{n,5}]

StackedBook

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

StackedPrism

seq=Table[GraphData[{"StackedPrism",{n,n}},"IrregularityStrength"],{n,3,5}]

Star

A000027

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

seq=Table[GraphData[{"Star",n},"IrregularityStrength"],{n,25}]

Sun

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

Sunlet

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

TorusGrid n×n

seq=Table[GraphData[{"TorusGrid",{n,n}},"IrregularityStrength"],{n,3,20}]

Transposition

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

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

Trapezohedron

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

seq=Table[GraphData[{"Trapezohedron",n},"IrregularityStrength"],{n,3,20}]

Triangular

seq=Table[GraphData[{"Triangular",n},"IrregularityStrength"],{n,2,20}]

TriangularGrid

seq=Table[GraphData[{"TriangularGrid",n},"IrregularityStrength"],{n,0,20}]

TriangularHoneycombAcuteKnight

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

TriangularHoneycombBishop

seq=Table[GraphData[{"TriangularHoneycombBishop",n},"IrregularityStrength"],{n,20}]

TriangularHoneycombObtuseKnight

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

TriangularHoneycombQueen

seq=Table[GraphData[{"TriangularHoneycombQueen",n},"IrregularityStrength"],{n,20}]

TriangularHoneycombRook

seq=Table[GraphData[{"TriangularHoneycombRook",n},"IrregularityStrength"],{n,20}]

TriangularSnake

seq=Table[GraphData[{"TriangularSnake",n},"IrregularityStrength"],{n,1,20,2}]

Web

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

Wheel

A008620

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

Ebert, G.; Hammenter, J.; Lazebnik, F.; and Woldar, A.  ``Irregularity Strengths for Certain Graphs.'' {\it Congressus Numerantium} {\bf 71}, 39--52, 1990.

Table[{n,IrregularityLambda[WheelGraph[n]],Ceiling[((n+1)/3)]},{n,3,20}]

Bača, M.; Imran, M.; Semaničová-Feňovčíková, A. Irregularity and Modular Irregularity Strength of Wheels. Mathematics 2021, 9, 2710. https://doi.org/10.3390/math9212710

https://www.mdpi.com/2227-7390/9/21/2710#B9-mathematics-09-02710

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

Do[Print[{gn={"Wheel",n},IrregularityStrength[GraphData[gn],Method->"NextTuple"]//Timing}],{n,4,10}]

Table[Piecewise[{{3,n==4||n==5}},Ceiling[((n+1)/3)]],{n,4,20}]

WheelComplement

seq=Table[GraphData[{"WheelComplement",n},"IrregularityStrength"],{n,4,20}]

WhiteBishop n×n

seq=Table[GraphData[{"WhiteBishop",{n,n}},"IrregularityStrength"],{n,2,20}]

Zebra n×n

seq=Table[GraphData[{"Zebra",{n,n}},"IrregularityStrength"],{n,20}]

Examples

<<MathWorld`Graphs`

1 isolated vertex

Select[GraphData[;;5],GraphData[#,"IsolatedPointCount"]==1&]

Print[{#,GraphData[#,"V"],IrregularityStrength[GraphData[#]]//Timing}]&/@%;

>1 isolated vertex

Select[GraphData["Nonempty",;;5],GraphData[#,"IsolatedPointCount"]>1&]

Print[{#,GraphData[#,"V"],IrregularityStrength[GraphData[#],MaxIterations->20]//Timing}]&/@%;

isolated edge

Select[GraphData[;;5],!FreeQ[GraphData[#,"ConnectedComponents","Name"],{"Path",2}]&]

Print[{#,GraphData[#,"V"],IrregularityStrength[GraphData[#],MaxIterations->20]//Timing}]&/@%;

Star

Do[Print[{n,IrregularityStrength[StarGraph[n]]//Timing}],{n,2,9}]

TriangleGraph

IrregularityStrength[GraphData@"TriangleGraph"]

Checks

DeleteCases[
Monitor[
{
gn=#,
GraphData[#,"IrregularityStrength"],
IrregularityStrength[GraphData[#],Method->"NextTuple"]
}&/@GraphData[2;;6],
gn],
{_,x_,x_}]//Timing

DeleteCases[
Monitor[
{
gn=#,
GraphData[#,"IrregularityStrength"],
IrregularityStrength[GraphData[#],Method->"Tuples"]
}&/@GraphData[2;;6],
gn],
{_,x_,x_}]//Timing

DeleteCases[
Monitor[
{
gn=#,
GraphData[#,"IrregularityStrength"],
IrregularityStrength[GraphData[#],Method->"Tuples"]
}&/@DeleteCases[GraphData[2;;7],{"Complete",7}|{"CompleteKPartite",{1,2,2,2}}],
gn],
{_,x_,x_}]//Timing