/*This program aims at constructing all {H7}-line graphs and enumeration of minimal forbidden subgraphs for the slim {H7}-line graphs, with a small number of vertices.*/
H1,VH1 := Graph<{1,2}|{{1,2}}>;AssignLabels(VH1,["slim","fat"]);H4,VH4 := Graph<{1,2,3,4}|{{1,2},{2,3},{3,4}}>;AssignLabels(VH4,["fat","slim","slim","fat"]);H7,VH7 := Graph<{1,2,3,4,5}|{{1,2},{2,3},{3,4},{5,2},{5,3},{5,4}}>;AssignLabels(VH7,["fat","slim","slim","fat","slim"]);
attachH1 := function(G,f) m := Order(G); attachedG := G; AddVertices(~attachedG,1); VV := VertexSet(attachedG); AssignLabels([VV | m+1],["slim"]); AddEdges(~attachedG,{{VV | m+1,f}}); AddEdges(~attachedG,{{VV | m+1,i} : i in {1..m} | (VV!i) adj (VV!f)}); return attachedG;end function;
attachH4toF1 := function(G,f) m := Order(G); attachedG := G; AddVertices(~attachedG,3); VV := VertexSet(attachedG); AssignLabels([VV | m+1,m+2,m+3],["slim","slim","fat"]); AddEdges(~attachedG,{{VV | m+1,f}}); AddEdges(~attachedG,{{VV | m+i,m+i+1} : i in {1,2}}); AddEdges(~attachedG,{{VV | m+1,i} : i in {1..m} | (VV!i) adj (VV!f)}); return attachedG;end function;
attachH4toF2 := function(G,t2) m := Order(G); attachedG := G; AddVertices(~attachedG,2); VV := VertexSet(attachedG); AssignLabels([VV | m+1,m+2],["slim","slim"]); AddEdges(~attachedG,{{VV | m+1,m+2}}); seqt2 := SetToSequence(t2); f1 := seqt2[1]; f2 := seqt2[2]; AddEdges(~attachedG,{{VV | f1,m+1}}); AddEdges(~attachedG,{{VV | f2,m+2}}); AddEdges(~attachedG,{{VV | m+1,i} : i in {1..m} | (VV!i) adj (VV!f1)}); AddEdges(~attachedG,{{VV | m+2,i} : i in {1..m} | (VV!i) adj (VV!f2)}); return attachedG;end function;
attachH7withFv := function(G,f) m := Order(G); attachedG := G; AddVertices(~attachedG,4); VV := VertexSet(attachedG); AssignLabels([VV | m+1,m+2,m+3,m+4],["slim","slim","slim","fat"]); AddEdges(~attachedG,{{VV!f,VV!(m+1)},{VV!(m+1),VV!(m+2)},{VV!(m+1),VV!(m+3)},{VV!(m+2),VV!(m+3)},{VV!(m+2),VV!(m+4)}, {VV!(m+3),VV!(m+4)}}); AddEdges(~attachedG,{{VV | m+1,i} : i in {1..m} | (VV!i) adj (VV!f)}); return attachedG;end function;
attachH7withFe := function(G,f) m := Order(G); attachedG := G; AddVertices(~attachedG,4); VV := VertexSet(attachedG); AssignLabels([VV | m+1,m+2,m+3,m+4],["slim","slim","slim","fat"]); AddEdges(~attachedG,{{VV!f,VV!(m+1)},{VV!f,VV!(m+2)},{VV!(m+1),VV!(m+2)},{VV!(m+1),VV!(m+3)},{VV!(m+2),VV!(m+3)},{VV!(m+3),VV!(m+4)}}); AddEdges(~attachedG,{{VV | m+1,i} : i in {1..m} | (VV!i) adj (VV!f)}); AddEdges(~attachedG,{{VV | m+2,i} : i in {1..m} | (VV!i) adj (VV!f)}); return attachedG;end function;
attachH7toF2 := function(G,t2) m := Order(G); X := {}; seqt2 := SetToSequence(t2); attachedG := G; AddVertices(~attachedG,3); VV := VertexSet(attachedG); AssignLabels([VV | m+1,m+2,m+3],["slim","slim","slim"]); fv := seqt2[1]; fe := seqt2[2]; AddEdges(~attachedG,{{VV!(m+1),VV!(m+2)},{VV!(m+1),VV!(m+3)},{VV!(m+2),VV!(m+3)}}); AddEdges(~attachedG,{{VV!fv,VV!(m+1)},{VV!fe,VV!(m+2)},{VV!fe,VV!(m+3)}}); AddEdges(~attachedG,{{VV | m+1,i} : i in {1..m} | (VV!i) adj (VV!fv)}); AddEdges(~attachedG,{{VV | m+2,i} : i in {1..m} | (VV!i) adj (VV!fe)}); AddEdges(~attachedG,{{VV | m+3,i} : i in {1..m} | (VV!i) adj (VV!fe)}); Include(~X,attachedG); attachedG := G; AddVertices(~attachedG,3); VV := VertexSet(attachedG); AssignLabels([VV | m+1,m+2,m+3],["slim","slim","slim"]); fv := seqt2[2]; fe := seqt2[1]; AddEdges(~attachedG,{{VV!(m+1),VV!(m+2)},{VV!(m+1),VV!(m+3)},{VV!(m+2),VV!(m+3)}}); AddEdges(~attachedG,{{VV!fv,VV!(m+1)},{VV!fe,VV!(m+2)},{VV!fe,VV!(m+3)}}); AddEdges(~attachedG,{{VV | m+1,i} : i in {1..m} | (VV!i) adj (VV!fv)}); AddEdges(~attachedG,{{VV | m+2,i} : i in {1..m} | (VV!i) adj (VV!fe)}); AddEdges(~attachedG,{{VV | m+3,i} : i in {1..m} | (VV!i) adj (VV!fe)}); Include(~X,attachedG); return X;end function;
//////////////////////////////////
joinH1 := function(G) VG := VertexSet(G); VfG := {Index(f) : f in VG | Label(f) eq "fat"}; X := {}; for f in VfG do H := attachH1(G,f); Include(~X,H); end for; return X;end function;
joinH4 := function(G) VG := VertexSet(G); VfG := {Index(f) : f in VG | Label(f) eq "fat"}; X := {}; for f in VfG do H := attachH4toF1(G,f); Include(~X,H); end for; fatpairs := Subsets(VfG,2); for t2 in fatpairs do H := attachH4toF2(G,t2); Include(~X,H); end for; return X;end function;
joinH7 := function(G) VG := VertexSet(G); VfG := {Index(f) : f in VG | Label(f) eq "fat"}; X := {}; for f in VfG do H := attachH7withFv(G,f); Include(~X,H); H := attachH7withFe(G,f); Include(~X,H); end for; fatpairs := Subsets(VfG,2); for t2 in fatpairs do Y := attachH7toF2(G,t2); X := X join Y; end for; return X;end function;
//////////////////////////////////////////////////////////////////
CanonicalHoffmanGraph:=function(H); G:=CanonicalGraph(H); if IsLabelled(VertexSet(H)) then AssignVertexLabels(~G, Sort(VertexLabels(H) )); end if; return G;end function;includeUpToIso2:=procedure(~S,T) for x in T do Include(~S,CanonicalHoffmanGraph(x)); end for;end procedure;includeUpToIso:=procedure(~S,T) m:=#T; for x in T do if not exists(s){y:y in S| IsIsomorphic(x,y)} then Include(~S,x); end if; end for;end procedure;
//////////////////////////////////////////////////////////////////
slimSubgraph:=function(G); Gs:=sub< G | {s : s in VertexSet(G) | Label(s) eq "slim"} >; return CanonicalGraph(Gs);end function;
extendable:=function(G)A:=AutomorphismGroup(G);VsG:={ Index(x) : x in VertexSet(G) | Label(x) eq "slim" };StabVsG:=Stabilizer(A,VsG);return #ActionImage(StabVsG,GSet(StabVsG,VsG)) eq #AutomorphismGroup(slimSubgraph(G));end function;
/////////////////////////////////////////////////////////
AllH7LGs := function(v); t := Cputime(); T := []; T[1] := {H1}; T[2] := joinH1(H1) join {H4}; X := {H7}; for G in T[2] do includeUpToIso(~X,joinH1(G)); end for; for G in T[1] do includeUpToIso(~X,joinH4(G)); end for; T[3] := X; for i in {4..v} do i; X := {}; for G in T[i-1] do includeUpToIso(~X,joinH1(G)); end for; for G in T[i-2] do includeUpToIso(~X,joinH4(G)); end for; for G in T[i-3] do includeUpToIso(~X,joinH7(G)); end for; T[i] := X; Cputime(t); end for; return T;end function;
/////////////////////////////v := 10;T := AllH7LGs(v);/////////////////////////////
S := [];for i in {1..v} do S[i] := {slimSubgraph(h) : h in T[i]};end for;
for i in {1..v} do printf "(T[%o],S[%o]) = (%o,%o) \n",i,i,#T[i],#S[i];end for;
for i in{3..v} do TT := SetToSequence(T[i]); sample := {i : i in {1..#TT} | extendable(TT[i]) eq false}; i; sample;end for;
////////////////////////////////////////////////////
NonHlineCG := function(n) X := {CanonicalGraph(g) : g in SmallGraphDatabase(n)}; for G in S[n] do Exclude(~X,G); end for; return X;end function;
IsSubgraph2:=function(g1,g2); V:=Isetset(Vertices(g1)); V2:=VertexSet(g2); a:=false; for v in V do G:=CanonicalGraph(g1-v); if Size(G) eq Size(g2) then if DegreeSequence(G) eq DegreeSequence(g2) then if G eq CanonicalGraph(g2) then a:=true; break; end if; end if; end if; end for; return a;end function;
FBs := [];for i in{2,3,4} do FBs[i] := NonHlineCG(i);end for;for i in {5..v} do i; t := Cputime(); X := NonHlineCG(i); for G in NonHlineCG(i) do if exists{S : S in NonHlineCG(i-1) | IsSubgraph2(G,S) eq true} then Exclude(~X,G); end if; end for; FBs[i] := X; Cputime(t);end for;
#FBs[4] eq 1;#FBs[5] eq 4;#FBs[6] eq 2;#FBs[7] eq 4;#FBs[8] eq 1;#FBs[9] eq 8;