Notebook Archive

Browse Categories
About
Contribute

Filter

Apply

Educational Materials

Alternating Group Graph

Eric W. Weisstein

Author

Eric W. Weisstein

Title

Alternating Group Graph

Description

The alternating group graph AG_n is the undirected Cayley graph of the set of 2(n-2) generators of the alternating group A_n given by g_3^-, g_3^+, g_4^-, g_4^+, ..., g_n^-, and g_n^+, where g_i^- = (1,i,2) (1) g_i^+ = (1,2,i) (2) in permutation cycle notation (Jwo et al. 1993). AG_n is a special case of the arrangement graph A_(n,k) given by A_(n,n-2). This and other special cases are summarized in the following table and illustrated above. n graph 2 singleton graph K_1 3 triangle graph...

Alternating Group Graph

Author

Eric W. Weisstein
July 30, 2018

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

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

Figure

gs=SortBy[{("AlternatingGroup"/.GraphData[#,"NotationRules"]),#}&/@GraphData["AlternatingGroup"],First]

{{2,SingletonGraph},{3,TriangleGraph},{4,CuboctahedralGraph},{5,{Arrangement,{5,3}}},{6,{Arrangement,{6,4}}}}

nicegs=Select[gs,GraphData[#[[2]],"Embeddings"]=!={}&]

{{2,SingletonGraph},{3,TriangleGraph},{4,CuboctahedralGraph}}

GraphicsGrid[Partition[Show[GraphData[#[[2]]]/.g_System`GraphSetProperty[g,{VertexSizeIf[#[[1]]2,.01,{"Scaled",.04}],System`VertexStyleRed,System`EdgeStyleBlack}],MethodNone,BaseStyleItalic,PlotLabelTextCell[Style[Column[{Subscript["AG",Style[#[[1]],Plain]],GraphData[#[[2]],"Name"]},AlignmentCenter],FontFamily"Times"]]]&/@nicegs,UpTo[3]],ImageSize450]

Special Cases

In[]:=

Sort[("AlternatingGroup"/.GraphData[#,"NotationRules"])#&/@GraphData["AlternatingGroup"]]

Out[]=

{2SingletonGraph,3TriangleGraph,4CuboctahedralGraph,5{Arrangement,{5,3}},6{Arrangement,{6,4}}}

In[]:=

TextGrid[DeleteCases[Table[{n,RecognizeGraph[AlternatingGroupGraph[n]]},{n,8}],{_,{}}],DividersAll]

Out[]=

1	SingletonGraph
2	SingletonGraph
3	TriangleGraph
4	CuboctahedralGraph
5	{Arrangement,{5,3}}
6	{Arrangement,{6,4}}

Properties

Acyclic


AdjacencyMatrixCount


Anarboricity


Arboricity


ArcTransitive


ArcTransitivity


AutomorphismCount


BalabanIndex

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

FindSequenceFunction[seq,n]

Bandwidth

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

BridgeCount

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

BurningNumber

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

CharacteristicPolynomial

Factor@(poly=Table[GraphData[{"AlternatingGroupGraph",n},"CharacteristicPolynomial"],{n,k0=1,kmax=6}]/.f_Functionf[x])//Column

In[]:=

coef=Factor/@FindLinearRecurrence[poly]

In[]:=

CoefficientList[Take[poly,10],x]

In[]:=

ToPolynomialRecurrence[p,x,n,coef]

In[]:=

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

In[]:=

TeXForm[%]

In[]:=

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

In[]:=

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

In[]:=

gf=Factor[

FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

ChordCount

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

Table[GraphData[{"AlternatingGroupGraph",n},"EdgeCount"],{n,2,6}]

Table[(n-1)n!/2,{n,2,6}]

Chordless

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

ChordlessCycleCount

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

In[]:=

FindSequenceFunction[Rest@seq,n-3]//Factor

Chords

Length/@Table[GraphData[{"AlternatingGroupGraph",n},"Chords"],{n,2,6}]

ChromaticInvariant

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

FindSequenceFunction[DeleteMissing@seq,n]

ChromaticNumber

In[]:=

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

Out[]=

{1,3,3,3,3}

ChromaticPolynomial

Factor@(poly=Table[GraphData[{"AlternatingGroupGraph",n},"ChromaticPolynomial"],{n,k0=1,kmax=6}]/.f_Functionf[x])//Column

In[]:=

coef=Factor/@FindLinearRecurrence[DeleteMissing@poly]

In[]:=

ToPolynomialRecurrence[p,x,n,coef]

In[]:=

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

In[]:=

TeXForm[%]

In[]:=

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

In[]:=

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

Subtract@@@Table[{GraphData[{"AlternatingGroupGraph",n},"ChromaticPolynomial"][x],x(

(-1)

(-3+x)

(-2+x)

(-1)

(-3+x)+

(-3+x)

)x)},{n,3,13}]//Expand

In[]:=

gf=Factor[

FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

Circumference

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

In[]:=

FindSequenceFunction[Drop[seq,2],n-2]

In[]:=

Table[n!,{n,3,6}]

Classes

Intersection@@(GraphData[#,"Classes"]&/@GraphData["AlternatingGroupGraph"])

{"Bicolorable","Bipartite","AlternatingGroupGraph","Class1","Connected","Perfect","Regular","Simple","Traceable","TriangleFree","VertexTransitive","WeaklyPerfect"}

CliqueCount

A139149

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

In[]:=

FindSequenceFunction[seq,n]

FindGeneratingFunction[seq,x]

Table[((n+1)!+2)/2,{n,2,6}]

CliqueCoveringNumber

Probably A001710

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

In[]:=

Numerator[Range[6]!/2]

FullSimplify[FindSequenceFunction[DeleteMissing@seq,n],n>2]

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

CliquePolynomial

(poly=Factor@Table[GraphData[{"AlternatingGroupGraph",n},"CliquePolynomial"][x],{n,k0=1,kmax=6}])//Column

CliqueNumber

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

ComplementOddChordlessCycleCount

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

ConnectedDominatingSetCount

A317481

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

FindSequenceFunction[DeleteMissing@seq,n]//FullSimplify

ConnectedDominationNumber

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

ConnectedDominationPolynomial

(poly=Table[GraphData[{"AlternatingGroupGraph",n},"ConnectedDominationPolynomial"],{n,k0=1,kmax=6}]/.f_Functionf[x])//Factor//Column

In[]:=

coef=Factor/@FindLinearRecurrence[DeleteMissing[poly]]

In[]:=

ToPolynomialRecurrence[p,x,n,coef]

In[]:=

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

In[]:=

TeXForm[%]

In[]:=

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

In[]:=

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

Subtract@@@Table[{GraphData[{"AlternatingGroupGraph",n},"ConnectedDominationPolynomial"][x],n

-2+n

-1+n

+2x(-1+

(1+x)

(-1+

(1+x)

)},{n,3,13}]//Expand

ConnectedInducedSubgraphCount

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

FindSequenceFunction[seq,n]//FullSimplify

ConnectedInducedSubgraphPolynomial

(poly=Factor@Table[GraphData[{"AlternatingGroupGraph",n},"ConnectedInducedSubgraphPolynomial"],{n,k0=1,6}]/.f_Functionf[x])//Factor//Column

In[]:=

coef=Factor/@FindLinearRecurrence[DeleteMissing[poly]]

In[]:=

ToPolynomialRecurrence[p,x,n,coef]

In[]:=

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

In[]:=

TeXForm[%]

In[]:=

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

In[]:=

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=

FindGeneratingFunction[poly,z]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

FullSimplify[%-poly]

CrossingNumber

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

Table[GraphData[{"AlternatingGroupGraph",n},"Planar"],{n,2,6}]

CycleCount

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

FindSequenceFunction[seq,n]//Factor

CyclePolynomial

Factor@(poly=Table[GraphData[{"AlternatingGroupGraph",n},"CyclePolynomial"],{n,k0=1,kmax=6}]/.f_Functionf[x])//Column

In[]:=

coef=Factor/@FindLinearRecurrence[poly]

In[]:=

ToPolynomialRecurrence[p,x,n,coef]

In[]:=

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

In[]:=

TeXForm[%]

In[]:=

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

In[]:=

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

In[]:=

gf=

FindGeneratingFunction[poly,z]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

Cyclic

Table[GraphData[{"AlternatingGroupGraph",n},"Cyclic"],{n,2,6}]

CyclomaticNumber

A317483

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

FindSequenceFunction[seq,n]//FullSimplify

DetourIndex

A296782

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

FindSequenceFunction[seq,n]//Factor

DetourPolynomial

(poly=Factor@Table[GraphData[{"AlternatingGroupGraph",n},"DetourPolynomial"],{n,k0=1,kmax=6}]/.f_Functionf[x])//Column

Diameter

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

In[]:=

FindSequenceFunction[seq,n]

DistancePolynomial

(poly=Factor@Table[GraphData[{"AlternatingGroupGraph",n},"DistancePolynomial"],{n,k0=1,kmax=6}]/.f_Functionf[x])//Column

In[]:=

coef=Factor/@FindLinearRecurrence[poly]

In[]:=

ToPolynomialRecurrence[p,x,n,coef]

In[]:=

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

In[]:=

TeXForm[%]

In[]:=

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

In[]:=

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

In[]:=

gf=Factor[

FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

DistinguishingNumber

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

DomaticNumber

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

DominationNumber

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

DominationPolynomial

(poly=Factor[Table[GraphData[{"AlternatingGroupGraph",n},"DominationPolynomial"],{n,k0=1,kmax=6}]/.f_Function:>f[x]])//Column

In[]:=

CoefficientList[Take[poly,5],x]

In[]:=

coef=Factor/@FindLinearRecurrence[DeleteMissing@poly]

In[]:=

ToPolynomialRecurrence[p,x,n,coef]

In[]:=

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

In[]:=

TeXForm[%]

In[]:=

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

In[]:=

Simplify[RSolve[Prepend[Table[p[k+k0-1,x]poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>2]

In[]:=

gf=Factor[

FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

DominatingSetCount

A317484

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

FindSequenceFunction[DeleteMissing@seq,n]//FullSimplify

In[]:=

gf=

FindGeneratingFunction[DeleteMissing@seq,x]

In[]:=

soln=FullSimplify[SeriesCoefficient[gf,{x,0,n}],n>2]

Table[3

-2+RootSum[-1-#1-

&,#^n&],{n,2,6}]

EdgeChromaticNumber

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

EdgeConnectivity

Table[GraphData[{"AlternatingGroupGraph",n},"EdgeConnectivity"],{n,2,6}]

EdgeCount


EdgeCoverCount

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

In[]:=

FullSimplify[FindSequenceFunction[DeleteMissing@seq,n],n>0&&n∈Integers]

In[]:=

coef=FindLinearRecurrence[DeleteMissing@seq]

In[]:=

Length@coef

In[]:=

Take[seq,6]

In[]:=

LinearRecurrence[{11,-24,-21,33,34,8},{2,34,341,2902,23092,178393},20]

In[]:=

gf=xFindGeneratingFunction[DeleteMissing@seq,x]

In[]:=

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

In[]:=

CoefficientListSeries

-2-12x-15

-9

-2

-1+11x-24

-21

+33

+34

,{x,0,20},x

EdgeCoverNumber

A001710

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

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

In[]:=

Range[6]!/2

EdgeCoverPolynomial

(poly=Factor[Table[GraphData[{"AlternatingGroupGraph",n},"EdgeCoverPolynomial"],{n,k0=1,kmax=6}]/.f_Functionf[x]])//Column

In[]:=

CoefficientList[Take[poly,4],x]//Column

In[]:=

FindLinearRecurrence[DeleteMissing@Drop[poly,1]]//Head

coef=Factor/@FindPolynomialRecurrence[poly,6]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[

FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

Table[nx(3x+2)-2x^2+1,{n,10}]

FullSimplify[%-poly]

EulerianCycleCount

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

FaceCount

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

FindSequenceFunction[seq,n]

FlowPolynomial

(poly=Factor@Table[GraphData[{"AlternatingGroupGraph",n},"FlowPolynomial"],{n,k0=1,kmax=6}]/.f_Functionf[x])//Column

In[]:=

coef=Factor/@FindLinearRecurrence[DeleteMissing@poly]

In[]:=

ToPolynomialRecurrence[p,x,n,coef]

In[]:=

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

In[]:=

TeXForm[%]

In[]:=

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

In[]:=

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[

FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

FractionalChromaticNumber

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

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

FractionalCliqueNumber

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

FractionalEdgeChromaticNumber

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

Girth

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

HamiltonDecompositionCount

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

Hamiltonian

Table[GraphData[{"AlternatingGroupGraph",n},"Hamiltonian"],{n,2,6}]

HamiltonianCycleCount

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

FindSequenceFunction[seq,n]//Factor

HamiltonianNumber

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

FindSequenceFunction[seq,n]

HamiltonianPathCount

A317485

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

In[]:=

FindSequenceFunction[Rest@seq,n-3]//Factor

HamiltonianWalkCount

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

FindSequenceFunction[DeleteMissing@seq,n]//Factor

HararyIndex

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

In[]:=

FindSequenceFunction[seq,n]//Factor

HexagonCount

A317486

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

(seq=Table[CycleCount[AlternatingGroupGraph[n],6],{n,8}])//Timing

(seq=Table[CycleCount[AlternatingGroupGraph[n],6],{n,9}])//Timing

In[]:=

FindLinearRecurrence[Drop[seq,2]]

In[]:=

FindGeneratingFunction[seq,x]

IdiosyncraticPolynomial

(poly=Factor@Table[GraphData[{"AlternatingGroupGraph",n},"IdiosyncraticPolynomial"],{n,k0=1,kmax=6}]/.f_Functionf[x,y])//Column

In[]:=

coef=Factor/@FindLinearRecurrence[poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[

FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

Table[nx(3x+2)-2x^2+1,{n,10}]

FullSimplify[%-poly]

IndependenceNumber

A001710

In[]:=

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

Out[]=

{1,1,4,20,120}

In[]:=

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

Out[]=

{1,3,12,60,360}

In[]:=

Table[Piecewise[{{1,n2||n3}},n!/6],{n,2,10}]

Out[]=

{1,1,4,20,120,840,6720,60480,604800}

(byblis V12.0.0 (2)) In[10]:=

Do[Print[{{"AlternatingGroupGraph",n},MemoryConstrained[First@FindIndependentVertexSet[AlternatingGroupGraph[n]],100*^9]//Timing}],{n,7}]

{{AlternatingGroup,1},{0.,{1}}}

{{AlternatingGroup,2},{0.,{1}}}

{{AlternatingGroup,3},{0.,{1}}}

{{AlternatingGroup,4},{0.,{2,3,7,10}}}

{{AlternatingGroup,5},{0.,{1,3,4,5,8,9,10,12,26,30,31,35,37,40,45,48,51,53,56,58}}}

{{AlternatingGroup,6},{15800.3,{3,5,8,10,25,27,28,29,32,33,34,36,37,39,40,41,44,45,46,48,63,65,68,70,73,74,76,78,79,81,83,84,110,111,113,114,115,116,118,119,133,134,136,138,139,141,143,144,146,150,151,155,158,162,163,167,169,172,177,180,181,183,184,185,188,189,190,192,206,210,211,215,217,220,225,228,231,233,236,238,241,243,244,245,248,249,250,252,266,270,271,275,277,280,285,288,291,293,296,298,314,315,317,318,319,320,322,323,325,328,333,336,339,341,344,346,351,353,356,358}}}

From Stan Wagon, Aug 8, 2018

α A n+k,n 	n=1;complete K k+1	2	3	4	5	6	7
k=1; bipartite	1	3	12	60	360	2520	20160
k=2	1	4	20	120	840	6720	[50880,60480]
k=3	1	5	30	[204,209]	<1680	<15120	<151200
k=4	1	6	42	336
k=5	1	7	56	504
k=6	1	8	72	720	7920	95040
k	1	k+2	(k+2)(k+3)	∞ many perfect	∞ many perfect	∞ many perfect

Table 1. Known results for the independence number of

n+k,n

. Perfect strategies exist in all cases shown except the red entries, and perhaps the bold one.

{1,1,4,20,120,840,6720}

IndependencePolynomial

(poly=Factor@Table[GraphData[{"AlternatingGroupGraph",n},"IndependencePolynomial"],{n,k0=1,kmax=6}]/.f_Functionf[x])//Column

In[]:=

CoefficientList[Take[poly,4],x]

In[]:=

coef=Factor/@FindLinearRecurrence[poly]

In[]:=

ToPolynomialRecurrence[p,x,n,coef]

In[]:=

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

In[]:=

TeXForm[%]

In[]:=

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

In[]:=

Simplify[RSolve[Prepend[Table[p[k+k0-1,x]poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

In[]:=

gf=Factor[

FindGeneratingFunction[poly,z]]

In[]:=

soln=FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>2]

In[]:=

CoefficientListTable

-n



1-

1+4x



1+

1+4x



,{n,10}//Expand,x//Column

In[]:=

Table

-n



1-

1+4x



1+

1+4x



,{n,10}//Expand

In[]:=

Table

n/2

LucasLn,1

,{n,10}//Expand

Subtract@@@Tablex(x+2)+

n/2

LucasLn,1

,GraphData[{"AlternatingGroupGraph",n},"IndependencePolynomial"][x],{n,3,10}//Expand

IndependenceRatio

In[]:=

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

Out[]=

1,



From Stan Wagon 2018-07-30: "FWIW Piotr has been expessing doubts that the 1/3 pattern continues. I am still hopeful as it is too beautiful."

In[]:=

FullSimplify[FindSequenceFunction[Rest@seq,n-3],n>3&&n∈Integers]

Table[Floor[2n/3]/(2n),{n,2,6}]

n!/2

IndependentEdgeSetCount

In[]:=

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

Out[]=

{1,4,2649,Missing[NotAvailable],Missing[NotAvailable]}

IndependentVertexSetCount

In[]:=

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

Out[]=

{2,4,108,954748238,Missing[NotAvailable]}

FindSequenceFunction[seq,n]//FullSimplify

In[]:=

gf=

FindGeneratingFunction[seq,x]

In[]:=

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

Table[LucasL[n]+3,{n,2,6}]

IntersectionNumber

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

IrredundancePolynomial

(poly=Factor@Table[GraphData[{"AlternatingGroupGraph",n},"IrredundancePolynomial"],{n,k0=4,20}]/.f_Functionf[x])//Column

In[]:=

coef=Factor/@FindLinearRecurrence[poly]

In[]:=

ToPolynomialRecurrence[p,x,n,coef]

In[]:=

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

In[]:=

TeXForm[%]

In[]:=

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

In[]:=

Simplify[RSolve[Prepend[Table[p[k+k0-1,x]poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

Simplify

:Time spent on a transformation exceeded 300. seconds, and the transformation was aborted. Increasing the value of TimeConstraint option may improve the result of simplification.

Simplify

:Time spent on a transformation exceeded 300. seconds, and the transformation was aborted. Increasing the value of TimeConstraint option may improve the result of simplification.

Simplify

:Time spent on a transformation exceeded 300. seconds, and the transformation was aborted. Increasing the value of TimeConstraint option may improve the result of simplification.

General

:Further output of Simplify::time will be suppressed during this calculation.

In[]:=

gf=Factor[

FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

IrredundantSetCount

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

In[]:=

coef=FindLinearRecurrence[Rest@seq]

In[]:=

Length[coef]

In[]:=

Take[seq,1+{1,8}]

In[]:=

Join[{7},LinearRecurrence[{3,-2,-1,2,-2,0,2,-1},{22,29,39,60,94,151,241,400},20]]

FindSequenceFunction[DeleteMissing@seq,n]

In[]:=

FindSequenceFunction[Drop[seq,2],n-4]

In[]:=

gf=

FindGeneratingFunction[DeleteMissing@seq,x]

CoefficientListSeries

7+x-23

-9

+14

-6

(-1+x)

(1-x-

)

,{x,0,20},x

In[]:=

Refine[SeriesCoefficient[gf,{x,0,n}],n>3]

In[]:=

terms=List@@res;

In[]:=

N[terms/.n0]//Chop

In[]:=

terms[[All,1]]

In[]:=

Expand[1+2(1+n)]

In[]:=

Table[3+2n+RootSum[1-

&],{n,40}]

Table[Piecewise[{{7,n3}},3+2n+RootSum[1-

&]],{n,2,6}]

KirchhoffIndex

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

(seq=Table[KirchhoffIndex@AlternatingGroupalGraph[n],{n,3,40}])//Timing

FindSequenceFunction[Drop[seq,3],n-5]//Head//Timing

In[]:=

FindLinearRecurrence[Drop[seq,3]]//Head//Timing

In[]:=

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

KirchhoffSumIndex

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

(seq=Table[KirchhoffSumIndex@AlternatingGroupalGraph[n],{n,3,40}])//Timing

In[]:=

FindSequenceFunction[Drop[seq,3],n-5]//Head//Timing

In[]:=

FindLinearRecurrence[Drop[seq,3]]//Head//Timing

In[]:=

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

LaplacianPolynomial

(poly=Factor@Table[GraphData[{"AlternatingGroupGraph",n},"LaplacianPolynomial"],{n,k0=1,kmax=6}]/.f_Functionf[x])//Column

In[]:=

coef=Factor/@FindLinearRecurrence[poly]

coef=Factor/@FindPolynomialRecurrence[poly,6]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[

FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

Table[nx(3x+2)-2x^2+1,{n,10}]

FullSimplify[%-poly]

LeafCount

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

Likelihood

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

LongestCycleCount

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

LongestPathLength

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

LongestPathCount

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

LovaszNumber

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

MatchingGeneratingPolynomial

Factor@(poly=Table[GraphData[{"AlternatingGroupGraph",n},"MatchingGeneratingPolynomial"],{n,k0=1,kmax=6}]/.f_Functionf[x])//Column

In[]:=

CoefficientList[Take[poly,5],x]

In[]:=

coef=Factor/@FindLinearRecurrence[poly]

In[]:=

ToPolynomialRecurrence[p,x,n,coef]

In[]:=

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

In[]:=

TeXForm[%]

In[]:=

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

In[]:=

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

In[]:=

gf=Factor[

FindGeneratingFunction[poly,z]]

Simplify[SeriesCoefficient[gf,{z,0,n}],n>2]

In[]:=

Table

3/2

(1+4x)

-n

-nx(2+7x)

1-

1+4x



1+

1+4x



+

1+4x



1-

1+4x



1+

1+4x



+

3/2

(1+4x)



1-

1+4x



1+

1+4x



,{n,5}//Factor

In[]:=

Table

3/2

(1+4x)

-n

-nx(2+7x)

1-

1+4x



1+

1+4x



+

3/2

(1+4x)

1+4x



1-

1+4x



1+

1+4x



,{n,5}//Factor

MatchingNumber

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

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

MatchingPolynomial

(poly=Factor@Table[GraphData[{"AlternatingGroupGraph",n},"MatchingPolynomial"],{n,k0=1,kmax=6}]/.f_Functionf[x])//Column

In[]:=

coef=Factor/@FindLinearRecurrence[poly]

In[]:=

ToPolynomialRecurrence[p,x,n,coef]

In[]:=

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

In[]:=

TeXForm[%]

In[]:=

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

In[]:=

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

In[]:=

gf=Factor[

FindGeneratingFunction[poly,z]]

SeriesCoefficient[gf,{z,0,n}]

MaximalCliqueCount

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

FindSequenceFunction[Rest@seq,n]

MaximalIndependencePolynomial

(poly=Table[GraphData[{"AlternatingGroupGraph",n},"MaximalIndependencePolynomial"],{n,2,6}]/.f_Functionf[x])//Column

MaximalIndependentEdgeSetCount

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

(seq=Table[Length@FindAllMaximalIndependentEdgeSets[AlternatingGroupalGraph[n]],{n,3,35}])//Timing

In[]:=

coef=FindLinearRecurrence[seq]

In[]:=

Length[coef]

In[]:=

LinearRecurrence[coef,Take[seq,Length@coef],{-1,20}]//Take[#,13]&

In[]:=

seq=LinearRecurrence[{0,5,3,-10,-12,7,18,4,-11,-8,1,3,1},{2,4,12,14,40,56,112,178,306,482,792,1214,1924},40]

In[]:=

FindSequenceFunction[Drop[seq,2],n-4]//Head//Timing

In[]:=

gf=xFindGeneratingFunction[seq,x,ValidationLength5]

In[]:=

CoefficientListSeries-

2(1+2x+

-6

+12

-9

-6

)

(-1+

)

(-1+

)

,{x,0,20},x

In[]:=

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

MaximalIndependentVertexSetCount

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

FindSequenceFunction[seq,n]//FullSimpify

In[]:=

gf=

FindGeneratingFunction[seq,x]

In[]:=

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

MaximalIrredundantSetCount

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

In[]:=

FindSequenceFunction[DeleteMissing@Drop[seq,2],n-4]//Head//Timing

In[]:=

FindLinearRecurrence[DeleteMissing@Drop[seq,2]]//Head//Timing

In[]:=

FindGeneratingFunction[seq,x,ValidationLength5]//Head//Timing

MaximumCliqueCount

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

FindSequenceFunction[Rest@seq,n]

MaximumIndependentEdgeSetCount

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

In[]:=

gf=

FindGeneratingFunction[seq,x]

In[]:=

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

MaximumIndependentVertexSetCount

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

In[]:=

gf=

FindGeneratingFunction[seq,x]

In[]:=

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

MaximumIrredundantSetCount

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

In[]:=

FindGeneratingFunction[DeleteMissing@seq,x]//Head//Timing

FindSequenceFunction[DeleteMissing@seq,n]//Head//Timing

MaximumLeafNumber

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

In[]:=

FindSequenceFunction[DeleteMissing@Rest@seq,n-3]

MaximumVertexDegree

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

MeanDistance

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

FindSequenceFunction[seq,n]//Factor

MinimalDominatingSetCount

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

In[]:=

FindSequenceFunction[DeleteMissing@Rest@seq,n-3]

In[]:=

gf=

FindGeneratingFunction[seq,x]

In[]:=

Refine[SeriesCoefficient[gf,{x,0,n}],n>3]

MinimalDominatingSetSignature

seq=Table[GraphData[{"AlternatingGroupGraph",n},"MinimalDominatingSetSignature"],{n,2,6}]//Column

FindSequenceFunction[DeleteMissing@seq,n]//Factor

MinimalEdgeCoverCount

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

In[]:=

seq={1,6,24,74,180,464,1113,2646,6360,15222,36795,89584,219635,542320,1346881,3361998,8427172,21195416,53455740,135112332,342093443,867325032,2201286622,5591469852,14211796995,36139507614,91934054637,233934039872,595393224041,1515602413390};

In[]:=

seq=Rest@CoefficientList[Series[x*(1+x)*(1+x-2*x^2-14*x^3-39*x^4+63*x^5+69*x^6+55*x^7-39*x^8-85*x^9-118*x^10-102*x^11-63*x^12-27*x^13-7*x^14-x^15)/((1-x^2-x^3)^3*(1-x-x^2-x^3)^2*(1-2*x-x^2-x^3)),{x,0,50}],x]

In[]:=

coef=FindLinearRecurrence[seq]

In[]:=

Length[coef]

In[]:=

Take[seq,18]

In[]:=

LinearRecurrence[{4,1,-12,-15,24,49,6,-73,-76,5,80,72,14,-30,-34,-19,-6,-1},{1,6,24,74,180,464,1113,2646,6360,15222,36795,89584,219635,542320,1346881,3361998,8427172,21195416},30]

FindSequenceFunction[seq,n]

In[]:=

gf=xFactor@FindGeneratingFunction[seq,x,ValidationLength5]

In[]:=

CoefficientListSeries-

(1+x)(-1-x+2

+14

+39

-63

-69

-55

+39

+85

+118

+102

+63

+27

)

(-1+

)

(-1+x+

)

(-1+2x+

)

,{x,0,20},x

In[]:=

Series[gf,{x,0,20}]

In[]:=

res=Refine[SeriesCoefficient[gf,{x,0,n}],n>0&&n∈Integers]

MinimalTotalDominatingSetCount

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

seq={2,4,9,12,15,21,21,20,30,45,44,49,65,77,98,132,153,180,247,329,409,528,690,889,1180,157637,2657,3538,4684,6169,8164,10783,14229,18877,25036,33078,43757,57996,76809,101721,134773,178450,236284,313097,414828,549383};

In[]:=

coef=FindLinearRecurrence[seq]

In[]:=

Length[coef]

In[]:=

Take[seq,Length[coef]]

In[]:=

LinearRecurrence[{2,-1,1,-1,0,0,-1,0,1,1,-1},{2,4,9,12,15,21,21,20,30,45,44},20]

In[]:=

FindSequenceFunction[seq,n]

In[]:=

gf=xFindGeneratingFunction[seq,x,ValidationLength5]

In[]:=

CoefficientListSeries

2+3

-4

-2

-9

-2

+12

-9

(-1+x)

(1-

)

,{x,0,20},x

In[]:=

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

In[]:=

Table2n+RootSum[-1-#1+

&,#^n&]+(1+

(-1)

)Root[1-#1+

&,2]

2+n

Root[-1+

&,1]

2+n

Root[-1+

&,2]

+Root[1-#1+

&,3]

2+n

Root[-1+

&,1]

2+n

Root[-1+

&,3]

,{n,20}//RootReduce

In[]:=

TableRoot[1-#1+

&,2]

2+n

Root[-1+

&,1]

2+n

Root[-1+

&,2]

+Root[1-#1+

&,3]

2+n

Root[-1+

&,1]

2+n

Root[-1+

&,3]

,{n,2,30,2}//RootReduce

In[]:=

Table[RootSum[-1-#+#^3&,

-n

&],{n,20}]

In[]:=

Table[2n+RootSum[-1-#1+

&,#^n&]+(1+

(-1)

)RootSum[-1-#+#^3&,

-n/2

&],{n,20}]

MinimumCoveringsByMaximalCliquesCount

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

In[]:=

seq={1,4,30,12,98,28,270,60,682,124,1638,252,3810,508,8670,1020,19418,2044,42966,4092,94162,8188,204750,16380,442314,32764,950214,65532,2031554,131068,4325310,262140,9174970,524284,19398582,1048572,40894386,2097148,85983150};

In[]:=

Join[{1},Table[If[Mod[n,2]0,2,n](2^Ceiling[n/2]-2),{n,4,20}]]

Table[Piecewise[{{1,n3},{2(2^Ceiling[n/2]-2),Mod[n,2]0},{(2^Ceiling[n/2]-2)n,Mod[n,2]1}}],{n,2,6}]

In[]:=

FindSequenceFunction[DeleteMissing@Drop[seq,1],n-3]//Head//Timing

In[]:=

coef=FindLinearRecurrence[DeleteMissing@Drop[seq,1]]

In[]:=

Length@coef

In[]:=

Take[seq,1+{1,8}]

In[]:=

Join[{1},LinearRecurrence[{0,6,0,-13,0,12,0,-4},{4,30,12,98,28,270,60,682},20]]

In[]:=

gf=

FindGeneratingFunction[seq,x]

In[]:=

CoefficientListSeries

1+4x+24

-12

-69

+60

-20

(1-3

)

,{x,0,20},x

In[]:=

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

MinimumConnectedDominatingSetCount

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

In[]:=

FindSequenceFunction[DeleteMissing@Drop[seq,2],n-4]//FullSimplify

MinimumDistinguishingLabelingCount

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

FindSequenceFunction[DeleteMissing@seq,n]

FindGeneratingFunction[DeleteCases[seq,_Missing],x]

MinimumDominatingSetCount

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

In[]:=

FindSequenceFunction[DeleteMissing@Drop[seq,4],n-6]//Factor

MinimumEdgeCoverCount

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

In[]:=

seq={1,2,21,8,85,18,217,32,441,50,781,72,1261,98,1905,128,2737,162,3781,200,5061,242,6601,288,8425,338,10557,392,13021,450,15841,512,19041,578,22645,648,26677,722,31161,800,36121,882,41581,968,47565,1058,54097,1152};

In[]:=

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

In[]:=

coef=FindLinearRecurrence[seq]

In[]:=

Length[coef]

In[]:=

Take[seq,8]

In[]:=

LinearRecurrence[{0,4,0,-6,0,4,0,-1},{1,2,21,8,85,18,217,32},20]

In[]:=

Table[Floor[(n+3)/2],{n,20}]

In[]:=

gf=xFindGeneratingFunction[seq,x]

In[]:=

CoefficientListSeries

1+2x+17

-2

(-1+

)

,{x,0,20},x

In[]:=

Refine[SeriesCoefficient[gf,{x,0,n}],n>0]

In[]:=

Tablen(

+3n-1-

(-1)

(

+n-1))4,{n,20}

MinimumTotalDominatingSetCount

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

In[]:=

FindSequenceFunction[DeleteMissing@Drop[seq,2],n-4]

MinimumVertexCoverCount

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

MinimumVertexDegree

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

MolecularTopologicalIndex

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

FindLinearRecurrence[seq

FindSequenceFunction[seq,n]//Factor

Nonhamiltonian

Table[GraphData[{"AlternatingGroupGraph",n},"Nonhamiltonian"],{n,2,6}]

OddChordlessCycleCount

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

PathCount

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

FindSequenceFunction[DeleteMissing@seq,n]//Factor

PathPolynomial

(poly=Factor[Table[GraphData[{"AlternatingGroupGraph",n},"PathPolynomial"],{n,k0=1,kmax=6}]/.f_Function:>f[x]])//Column

In[]:=

coef=Factor/@FindLinearRecurrence[DeleteMissing@poly]

In[]:=

ToPolynomialRecurrence[p,x,n,coef]

In[]:=

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

In[]:=

TeXForm[%]

In[]:=

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

In[]:=

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

In[]:=

gf=Factor[

FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

poly2=Table[XXX,{n,k0,kmax}]

FullSimplify[poly2-poly]

PentagonCount

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

(seq=Table[CycleCount[AlternatingGroupGraph[n],5],{n,8}])//Timing

(seq=Table[CycleCount[AlternatingGroupGraph[n],5],{n,9}])//Timing

Planar

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

ProjectivePlaneCrossingNumber

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

Radius

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

RankPolynomial

(poly=Factor@Table[GraphData[{"AlternatingGroupGraph",n},"RankPolynomial"],{n,k0=1,kmax=6}]/.f_Functionf[x,y])

In[]:=

coef=Factor/@FindLinearRecurrence[DeleteMissing@poly]

In[]:=

ToPolynomialRecurrence[p,x,n,coef]

In[]:=

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

In[]:=

TeXForm[%]

In[]:=

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

In[]:=

Simplify[RSolve[Prepend[Table[p[k+k0-1,x]poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[

FindGeneratingFunction[poly,z]]

SeriesCoefficient[gf,{z,0,n}]

RectilinearCrossingNumber

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

ReliabilityPolynomial

(poly=Factor@Table[GraphData[{"AlternatingGroupGraph",n},"ReliabilityPolynomial"],{n,k0=1,kmax=6}]/.f_Functionf[x])//Column

In[]:=

coef=Factor/@FindLinearRecurrence[DeleteMissing@poly]

In[]:=

ToPolynomialRecurrence[p,x,n,coef]

In[]:=

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

In[]:=

TeXForm[%]

In[]:=

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

In[]:=

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[

FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

FullSimplify[poly2-poly]

ShannonCapacity

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

SigmaPolynomial

(poly=Factor@Table[GraphData[{"AlternatingGroupGraph",n},"SigmaPolynomial"],{n,k0=1,kmax=6}]/.f_Functionf[x])//Column

In[]:=

coef=Factor/@FindLinearRecurrence[DeleteMissing@poly]

ToPolynomialRecurrence[p,x,n,coef]

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

TeXForm[%]

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[

FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

Table[nx(3x+2)-2x^2+1,{n,10}]

FullSimplify[%-poly]

Skewness

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

SpanningTreeCount

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

In[]:=

FindSequenceFunction[seq,n]//FullSimplify

SquareCount

A317487

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

(seq=Table[CycleCount[AlternatingGroupGraph[n],4],{n,9}])//Timing

(seq=Table[CycleCount[AlternatingGroupGraph[n],4],{n,10}])//Timing

In[]:=

FindLinearRecurrence[Drop[seq,3]]

In[]:=

FindSequenceFunction[Drop[seq,3],n-3]

FindGeneratingFunction[seq,x]

StabilityIndex

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

TopologicalIndex

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

ToroidalCrossingNumber

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

TotalDominatingSetCount

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

FullSimplify[FindSequenceFunction[DeleteMissing@seq,n],n∈Integers]

TotalDominationNumber

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

TotalDominationPolynomial

(poly=Factor@Table[GraphData[{"AlternatingGroupGraph",n},"TotalDominationPolynomial"],{n,k0=1,kmax=6}]/.f_Functionf[x])//Column

In[]:=

coef=Factor/@FindLinearRecurrence[DeleteMissing@poly]

In[]:=

ToPolynomialRecurrence[p,x,n,coef]

In[]:=

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

In[]:=

TeXForm[%]

In[]:=

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

In[]:=

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

In[]:=

gf=Factor[

FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

Traceable

Table[GraphData[{"AlternatingGroupGraph",n},"Traceable"],{n,2,6}]

Triameter


TriangleCount

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

(seq=Table[CycleCount[AlternatingGroupGraph[n],3],{n,8}])//Timing

(seq=Table[CycleCount[AlternatingGroupGraph[n],3],{n,9}])//Timing

TuttePolynomial

(poly=Factor@Table[GraphData[{"AlternatingGroupGraph",n},"TuttePolynomial"],{n,k0=1,kmax=6}]/.f_Functionf[x,y])//Column

In[]:=

coef=Factor/@FindLinearRecurrence[DeleteMissing@poly]

In[]:=

ToPolynomialRecurrence[p,x,n,coef]

In[]:=

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

In[]:=

TeXForm[%]

In[]:=

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

In[]:=

Refine[RSolve[Prepend[Table[p[k+k0-1,x]poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[

FindGeneratingFunction[poly,z]]

FullSimplify[SeriesCoefficient[gf,{z,0,n}],n>0]

FullSimplify[poly2-poly]

Untraceable

Table[GraphData[{"AlternatingGroupGraph",n},"Untraceable"],{n,2,6}]

VertexConnectivity

Table[GraphData[{"AlternatingGroupGraph",n},"VertexConnectivity"],{n,2,6}]

VertexCount

In[]:=

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

Out[]=

{1,3,12,60,360}

In[]:=

FindSequenceFunction[seq,n-1]//FullSimplify

Out[]=

Pochhammer[1,n]

In[]:=

FunctionExpand[%]

Out[]=

Gamma[1+n]

In[]:=

Table[n!/2,{n,2,6}]

Out[]=

{1,3,12,60,360}

VertexCoverCount

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

FindSequenceFunction[seq,n]

VertexCoverNumber

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

FindSequenceFunction[seq,n]//FullSimplify

In[]:=

gf=

FindGeneratingFunction[seq,x]

In[]:=

FullSimplify[SeriesCoefficient[gf,{x,0,n}],n>3]

VertexCoverPolynomial

(poly=Factor@Table[GraphData[{"AlternatingGroupGraph",n},"VertexCoverPolynomial"],{n,k0=1,kmax=6}]/.f_Functionf[x])//Column

In[]:=

coef=Factor/@FindLinearRecurrence[poly]

In[]:=

ToPolynomialRecurrence[p,x,n,coef]

In[]:=

FormattedPolynomialRecurrence[p,x,n,coef]//TraditionalForm

In[]:=

TeXForm[%]

In[]:=

LinearRecurrence[coef,poly,{2-k0,Length[coef]-k0+1}]

In[]:=

FullSimplify[RSolve[Prepend[Table[p[k+k0-1,x]poly[[k]],{k,Length[coef]}],ToPolynomialRecurrence[p,x,n,coef]],p[n,x],n],n∈Integers&&n>0]

gf=Factor[

FindGeneratingFunction[poly,z]]

SeriesCoefficient[gf,{z,0,n}]

poly2=Table[LinearRecurrence[{x^2,2x^3,x^4},{x^2,x^3(4+x),x^4(3+6x+x^2)},{n}][[1]],{n,k0,20}]

FullSimplify[poly2-poly]

VertexDegrees

seq=Table[GraphData[{"AlternatingGroupGraph",n},"VertexDegrees"],{n,3,10}]

WienerIndex

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

FindSequenceFunction[seq,n]//Factor

WienerSumIndex

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

(seq=Table[WienerSumIndex@AlternatingGroupalGraph[n],{n,3,40}])//Timing

In[]:=

FindSequenceFunction[Drop[seq,3],n-5]//Head//Timing

In[]:=

FindLinearRecurrence[Drop[seq,3]]//Head//Timing

In[]:=

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

Recognize


Hamiltonian Cycles


Testing


GraphData


Cite this as: Eric W. Weisstein, "Alternating Group Graph" from the Notebook Archive (2018), https://notebookarchive.org/2019-07-0z3qvqa

Wolfram Foundation

Download

Alternating Group Graph

Author

Figure

Special Cases

Properties

Acyclic

AdjacencyMatrixCount

Anarboricity

Arboricity

ArcTransitive

ArcTransitivity

AutomorphismCount

BalabanIndex

Bandwidth

BridgeCount

BurningNumber

CharacteristicPolynomial

ChordCount

Chordless

ChordlessCycleCount

Chords

ChromaticInvariant

ChromaticNumber

ChromaticPolynomial

Circumference

Classes

CliqueCount

CliqueCoveringNumber

CliquePolynomial

CliqueNumber

ComplementOddChordlessCycleCount

ConnectedDominatingSetCount

ConnectedDominationNumber

ConnectedDominationPolynomial

ConnectedInducedSubgraphCount

ConnectedInducedSubgraphPolynomial

CrossingNumber

CycleCount

CyclePolynomial

Cyclic

CyclomaticNumber

DetourIndex

DetourPolynomial

Diameter

DistancePolynomial

DistinguishingNumber

DomaticNumber

DominationNumber

DominationPolynomial

DominatingSetCount

EdgeChromaticNumber

EdgeConnectivity

EdgeCount

EdgeCoverCount

EdgeCoverNumber

EdgeCoverPolynomial

EulerianCycleCount

FaceCount

FlowPolynomial

FractionalChromaticNumber

FractionalCliqueNumber

FractionalEdgeChromaticNumber

Girth

HamiltonDecompositionCount

Hamiltonian

HamiltonianCycleCount

HamiltonianNumber

HamiltonianPathCount

HamiltonianWalkCount

HararyIndex

HexagonCount

IdiosyncraticPolynomial

IndependenceNumber

IndependencePolynomial

IndependenceRatio

IndependentEdgeSetCount

IndependentVertexSetCount

IntersectionNumber

IrredundancePolynomial

IrredundantSetCount

Acyclic


AdjacencyMatrixCount


Anarboricity


Arboricity


ArcTransitive


ArcTransitivity


AutomorphismCount


EdgeCount


Triameter
