Split Graph

Author

Eric W. Weisstein
April 27, 2023

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

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

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

Sources

https://en.wikipedia.org/wiki/Split_graph

https://cs.uwaterloo.ca/journals/JIS/VOL3/ROYLE/royle.html

https://arxiv.org/abs/2304.12381

Forbidden induced subgraphs

Mukhopadhyay, A.; John, D.; and Vasudevan, S.  "Recognizing and Generating Unswitchable Graphs."  12 Apr 2023.  https://arxiv.org/abs/2304.12381

GraphicsRow[Show[StyleGraphs[GraphData[#]],PlotLabel->TextCell[Column[{GraphData[#,"Notation"],GraphData[#,"Name"]}/.s_String:>Style[s,Italic],BaseStyle->Directive[Black,FontFamily->"Times",14],Alignment->Center]]]&/@{{"Cycle",5},{"Cycle",4},{"LadderRung",2}},Dividers->All]

Enumeration

GraphData

Length/@Table[GraphData["Split",n],{n,7}]

Formula

A048194

b[n_,i_]:=b[n,i]=If[n==0,{0},If[i<1,{},Flatten@Table[Map[Function[{p},p+j*x^i],b[n-i*j,i-1]],{j,0,n/i}]]];
g[n_,k_]:=g[n,k]=Sum[Sum[2^Sum[Sum[GCD[i,j]*Coefficient[s,x,i]*Coefficient[t,x,j],{j,1,Exponent[t,x]}],{i,1,Exponent[s,x]}]/Product[i^Coefficient[s,x,i]*Coefficient[s,x,i]!,{i,1,Exponent[s,x]}]/Product[i^Coefficient[t,x,i]*Coefficient[t,x,i]!,{i,1,Exponent[t,x]}],{t,b[n+k,n+k]}],{s,b[n,n]}];
A[n_,k_]:=g[Min[n,k],Abs[n-k]];
a[d_]:=a[d]=Sum[A[n,d-n],{n,0,d}]-Sum[A[n,d-n-1],{n,0,d-1}];

Array[a,20]

Sequence

seq={1,2,4,9,21,56,164,557,2223,10766,64956,501696,5067146,67997750,1224275498,29733449510,976520265678,43425320764422,2616632636247976,213796933371366930,23704270652844196754,3569464106212250952762,730647291666881838671052};

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

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

Do[Print[{k,FindLinearRecurrence[Drop[seq,k]]//Head//Timing}],{k,0,15}]

Classes that are Split

GraphClassesThatAreClass["Split"]

Graphics

All

GraphicsGrid[Flatten[Partition[#,UpTo[6]]&/@Table[Show[StyleGraphs[GraphData[#]],PlotLabel->GraphData[#,"Name"],LabelStyle->Directive[Italic,Black,FontFamily->"Times"]]&/@GraphData["Split",n],{n,4}],1],Dividers->All,ImageSize->600]

Connected

GraphicsGrid[Flatten[Partition[#,UpTo[6]]&/@Table[Show[StyleGraphs[GraphData[#]],PlotLabel->GraphData[#,"Name"],LabelStyle->Directive[Italic,Black,FontFamily->"Times"]]&/@GraphData[{"Connected","Split"},n],{n,4}],1],Dividers->All,ImageSize->600]

Checks

Split graphs are chordal

DeleteCases[GraphData[#,{"#","Chordal"}]&/@GraphData["Split"],{_,True}]

Complements of Split graphs are Chordal

DeleteCases[{#,Replace[GraphData[GraphData[#,"ComplementGraph","Name"],"Chordal"],_GraphData->$Failed]//Quiet}&/@GraphData["Split"],{_,True|$Failed}]

Chordal graphs whose complements are chordal <-> Split

DeleteCases[{#1,#2,And[#3,#4]}&@@@DeleteCases[{
#,
GraphData[#,"Split"],
GraphData[#,"Chordal"],
Replace[GraphData[GraphData[#,"ComplementGraph","Name"],"Chordal"],_GraphData->$Failed]//Quiet}&/@GraphData[All],
{_,_,_,$Failed}],{_,x_,x_}]

Split graphs are Perfect

https://oeis.org/A048194

"All split graphs are perfect. - Falk Hüffner, Nov 29 2015"

DeleteCases[{#,GraphData[#,"Perfect"]}&/@GraphData["Split"],{_,True}]

Algorithm

VertexDegrees

SplitGraphQ[g_Graph]:=Module[{d=ReverseSort[VertexDegree[g]],m},
m=Flatten[Position[MapIndexed[#≥#2[[1]]-1&,d],True]][[-1]];
Total[Take[d,m]]==m(m-1)+Total[Take[d,{m+1,-1}]]
]

Table[Count[GraphData/@GraphData[n],_?SplitGraphQ],{n,7}]//Timing

SplitGraphQ[g_Graph]:=Module[{d=ReverseSort[VertexDegree[g]],m=VertexCount[g]},
While[d[[m]]<m-1,m--];
Total[Take[d,m]]==m(m-1)+Total[Take[d,{m+1,-1}]]
]

Table[Count[GraphData/@GraphData[n],_?SplitGraphQ],{n,7}]//Timing

DeleteCases[Monitor[{
gn=#,
GraphData[#,"Split"],
SplitGraphQ[GraphData[#],Method->"VertexDegrees"]
}&/@GraphData[;;10],gn],
{_,x_,x_}
]//Timing

DeleteCases[Monitor[{
gn=#,
GraphData[#,"Split"],
SplitGraphQ[GraphData[#],Method->"VertexDegrees"]
}&/@GraphData[All],gn],
{_,x_,x_}
]//Timing

Forbidden induced subgraphs

DeleteCases[Monitor[{
gn=#,
GraphData[#,"Split"],
SplitGraphQ[GraphData[#],Method->"ForbiddenSubgraphs"]
}&/@GraphData[;;10],gn],
{_,x_,x_}
]//Timing

DeleteCases[Monitor[{
gn=#,
GraphData[#,"Split"],
SplitGraphQ[GraphData[#],Method->"ForbiddenSubgraphs"]
}&/@GraphData[All],gn],
{_,x_,x_}
]//Timing