Topological and Algebraic Characterizations of Gallai-Simplicial Complexes
Imran Ahmed Shahid Muhmood





COMSATS Institute of Information Technology, Lahore, Pakistan
drimranahmed@ciitlahore.edu.pk
COMSATS Institute of Information Technology, Lahore, Pakistan
shahid_nankana@yahoo.com
 

 Topological and Algebraic Characterizations of Gallai-Simplicial
Complexes
    Imran Ahmed, Shahid Muhmood
    December 30, 2023
==========================================================================

 We recall first Gallai-simplicial
complex Δ_Γ(G) associated to Gallai graph Γ(G)
of a planar graph G, see <cit.>. The Euler characteristic is
a very useful topological and homotopic invariant to classify
surfaces. In Theorems <ref> and <ref>, we compute Euler
characteristics of Gallai-simplicial complexes associated to
triangular ladder and prism graphs, respectively. 

Let G be a finite simple graph on n vertices of the form n=3l+2 or 3l+3. In Theorem
<ref>, we prove that G will be f-Gallai graph for the following types of constructions of G.

Type 1.  When n=3l+2. G=𝕊_4l is a graph
consisting of two copies of star graphs S_2l and S'_2l with
l≥ 2 having l common vertices.
 Type 2. When n=3l+3.
G=𝕊_4l+1 is a graph consisting of two star graphs
S_2l and S_2l+1 with l≥ 2 having l common vertices.
 0.4 true cm
 Key words: Euler characteristic, simplicial complex and f-ideals.

2010 Mathematics Subject Classification: Primary 05E25, 55U10, 13P10 Secondary 06A11, 13H10.



myheadings Ahmed and
Muhmood
         Topological and Algebraic Characterizations of Gallai-Simplicial
Complexes

Topological and Algebraic Characterizations of Gallai-Simplicial
Complexes
    Imran Ahmed, Shahid Muhmood
    December 30, 2023
==========================================================================






§ INTRODUCTION



















Let X be a finite CW complex of dimension N. The Euler
characteristic is a function χ which associates to each X an
integer χ(X). More explicitly, the Euler characteristic of X
is defined as the alternating sum

    χ(X)=∑_k=0^N(-1)^kβ_k(X)

with β_k(X)=rank(H_k(X)) the k-th Betti number of X.

The Euler characteristic is a very useful topological and homotopic
invariant to classify surfaces. The Euler characteristic is uniquely
determined by excision χ(X)=χ(C)+χ(X\ C), for
every closed subset C⊂ X. The excision property has a dual
form χ(X)=χ(U)+χ(X\ U), for every open subset
U⊂ X, see <cit.> and <cit.> for more details.








We consider a planar graph G, the Gallai graph Γ(G) of G
is a graph having edges of G as its vertices, that is,
V(Γ(G))=E(G) and two distinct edges of G are adjacent in
Γ(G) if they are adjacent in G but dot span a triangle. The
buildup of the 2-dimensional Gallai-simplicial complex
Δ_Γ(G) from a planar graph G is an abstract idea
similar to building an origami shape from a plane sheet of paper by
defining a crease pattern, see <cit.>.

Let S=k[x_1,…,x_n] be a polynomial ring over an infinite
field k. There is a natural bijection between a square free
monomial ideal and a simplicial complex written as
Δ↔ I_𝒩(Δ), where
I_𝒩(Δ) is the Stanley-Reisner ideal or non-face
ideal of Δ, see for instance <cit.>. In <cit.>, Faridi
introduced another correspondence Δ↔
I_ℱ(Δ), where I_ℱ(Δ) is the
facet ideal of Δ. She discussed its connections with the
theory of Stanley-Reisner rings.

In <cit.> and <cit.>, the authors investigated the
correspondence δ_ℱ(I)↔
I↔δ_𝒩(I), where
δ_ℱ(I) and δ_𝒩(I) are facet
and non-face simplicial complexes associated to the square free
monomial ideal I (respectively). A square free monomial ideal I
in S is said to be an f-ideal if and only if both
δ_ℱ(I) and δ_𝒩(I) have the
same f-vector. The concepts of f- ideals is important in the
sense that it discovers new connections between both the theories.
The complete characterization of f-ideals in the polynomial ring
S over a field k  can be found in <cit.>. A simple finite
graph G is said to be the f-graph if its edge ideal I(G) is an
f-ideal of degree 2, see <cit.>.

In Theorems <ref> and <ref>, we compute Euler characteristics
of Gallai-simplicial complexes associated to triangular ladder and
prism graphs, respectively.

Let G be a finite simple graph on n vertices of the form n=3l+2 or 3l+3. In Theorem
<ref>, we prove that G will be f-Gallai graph for the following types of constructions of G.

Type 1.  When n=3l+2. G=𝕊_4l is a graph
consisting of two copies of star graphs S_2l and S'_2l with
l≥ 2 having l common vertices.
 Type 2. When n=3l+3.
G=𝕊_4l+1 is a graph consisting of two star graphs
S_2l and S_2l+1 with l≥ 2 having l common vertices.



§ PRELIMINARIES


A simplicial complex Δ on [n]={1,…, n}
is a collection of subsets of [n] with the property that {i}∈Δ for all i, and if F∈Δ then every subset of F
will belong to Δ (including empty set). The elements of
Δ are called faces of Δ and the dimension of a face
F∈Δ is defined as |F|-1, where |F| is the number of
vertices of F. The faces of dimensions 0 and 1 are called
vertices and edges, respectively, and dim ∅= -1.

The maximal faces of Δ under inclusion are called
facets. The dimension of Δ is denoted by Δ and is
defined as:

    Δ=max{ F | F∈Δ}.
 A simplicial complex is
said to be pure if it has all the facets of the same dimension. If
{F_1,… ,F_q} is the set of all the facets of Δ, then
Δ=<F_1,… ,F_q>.

We denote by Δ_n the closed n-dimensional simplex. Every
simplex Δ_n is homotopic to a point and thus

    χ(Δ_n)=1, ∀  n≥ 0.

Note that ∂Δ_n is homeomorphic to the (n-1)-sphere
S^n-1. Since S^0 is a union of two points, we have
χ(S^0)=2. In general, the n-dimensional sphere is a union of
two closed hemispheres intersecting along the Equator which is a
(n-1) sphere. Therefore,

    χ(S^n)=2χ(Δ_n)-χ(S^n-1)=2-χ(S^n-1).

We deduce inductively

    2=χ(S^n)+χ(S^n-1)=…=χ(S^1)+χ(S^0)

so that χ(S^n)=1+(-1)^n. Now, note that the interior of
Δ_n is homeomorphic to ℝ^n so that

    χ(ℝ^n)=χ(Δ_n)-χ(∂Δ_n)=1-χ(S^n-1)=(-1)^n.


The excision property implies the following useful formula. Suppose

    ∅⊂Δ^(0)⊂…⊂Δ^(N)=Δ

is an increasing filtration of Δ by closed subsets. Then,

    χ(Δ)=χ(Δ^(0))+χ(Δ^(1)\Δ^(0))
    +…+χ(Δ^(N)\Δ^(N-1)).
 We denote by
Δ^(k) the union of the simplices of dimension ≤ k.
Then, Δ^(k)\Δ^(k-1) is the union of
interiors of the k-dimensional simplices. We denote by
f_k(Δ) the number of such simplices. Each of them is
homeomorphic to ℝ^k and thus its Euler characteristic is
equal to (-1)^k. Consequently, the Euler characteristic of
Δ is given by

    χ(Δ)=∑_k=0^N(-1)^kf_k(Δ),

see <cit.> and <cit.>.

Let Δ be a simplicial complex of dimension N, we define its
f-vector by a (N+1)-tuple f=(f_0,…, f_N), where f_i is
the number of i-dimensional faces of Δ.



The following definitions serve as a bridge between the
combinatorial and algebraic properties of the simplicial complexes
over the finite set of vertices [n].

Let Δ be a simplicial complex over the vertex set
{v_1,…,v_n} and S=k[x_1,…,x_n] be the polynomial
ring on n variables.  We define the facet ideal of Δ by
I_ℱ(Δ), which is an ideal of S generated by
square free monomials x_i_1… x_i_s where
{v_i_1,…,v_i_s} is a facet of Δ. We define the
non-face ideal or the Stanley-Reisner ideal of Δ by
I_𝒩(Δ), which is an ideal of S generated by
square free monomials x_i_1… x_i_s where
{v_i_1,…,v_i_s} is a non-face of Δ.

Let I=(M_1,…,M_q) be a square free monomial ideal in the
polynomial ring S=k[x_1,…,x_n], where {M_1,…,M_q} is
a minimal generating set of I. We define a simplicial complex
δ_ℱ(I) over a set of vertices
v_1,…,v_n with facets F_1,…,F_q, where for each
i, F_i={v_j |  x_j|M_i, 1≤ j≤ n}.
δ_ℱ(I) is said to be the facet complex of I. We
define a simplicial complex δ_𝒩(I) over a set of
vertices v_1,…,v_n, where {v_i_1,…,v_i_s} a
face of δ_𝒩(I) if and only if the product
x_i_1… x_i_s does not belong to I. We call
δ_𝒩(I) the non-face complex or the
Stanley-Reisner complex of I.


To proceed further, we define the Gallai-graph Γ(G), which is
a nice combinatorial buildup, see <cit.> and <cit.>.

 Let G be a graph and Γ(G) is said to be the Gallai graph of G if
the following conditions hold;

1. Each edge of G represents a vertex of Γ(G).

2. If two edges are adjacent in G that do not span a triangle in
G then their corresponding vertices will be adjacent in
Γ(G).

 The graph G and its
Gallai graph Γ(G) are given in figures (i) and (ii),
repectively.


        
    < g r a p h i c s >

        

To define Gallai-simplicial complex Δ_Γ(G) of a planar
graph G, we introduce first a few notions, see <cit.>.

<cit.> Let G be a  finite simple graph with vertex set
V(G)=[n] and edge set E(G)={e_i,j={i,j} |  i,j∈ V(G)}.
We define the set of Gallai-indices Ω(G) of the graph G as
the collection of subsets of V(G) such that if e_i,j and
e_j,k are adjacent in Γ(G), then F_i,j,k={i,j,k}∈Ω(G) or if e_i,j is an isolated vertex in Γ(G) then
F_i,j={i,j}∈Ω(G).


<cit.> A Gallai-simplicial complex Δ_Γ(G) of G is
a simplicial complex defined over V(G) such that

    Δ_Γ(G)=<F  |  F∈Ω(G)>,
 where Ω(G) is
the set of Gallai-indices of G.


For the graph G shown in figure below, its Gallai-simplicial
complex Δ_Γ(G) is given by

    Δ_Γ(G)=<{2,4}, {1,2,3},{1,3,4},{1,2,5},{1,4,5}>.











§ CHARACTERIZATIONS OF GALLAI-SIMPLICIAL COMPLEXES

The ladder graph L_n is a planar undirected graph with 2n
vertices and 3n-2 edges. The ladder graph L_n is the cartesian
product of two path graphs P_n and P_2, that is L_n=P_n×
P_2 and looks like a ladder with n rungs. The path graph P_n is
a graph whose vertices can be listed in an order v_1,…,v_n
such that {v_i,v_i+1} is an edge for 1≤ i≤ n-1. If we
add a cross edge between every two consecutive rungs of the ladder
then the resulting graph is said to be a triangular ladder graph
L^∗_n with 2n vertices and 4n-3 edges.

Let L^∗_n be the triangular ladder graph on 2n vertices with
fixing the label of the edge-set E(L^∗_n) as follows;

    E(L^∗_n)={e_1,2, e_2,3,…,e_2n-1,2n,e_1,2n-1,e_1,2n,…,e_n-1,n+1,e_n-1,n+2}.

Then, we have

Ω(L^∗_n)={F_1,2,3,…,F_n-2,n-1,n,F_n,n+1,n+2,…,F_2n-2,2n-1,2n,

F_1,2,2n,F_2,3,2n-1,…,F_n-1,n,n+2,F_1,2,2n-2,…,F_n-2,n-1,n+1,

F_1,2n-2,2n-1,…,F_n-2,n+1,n+2,F_2,2n-1,2n,…,F_n-1,n+2,n+3}.


By definition, it is clear that F_i,i+1,i+2∈Ω(L^∗_n)
because i, i+1, i+2 are consecutive vertices of 2n-cycle and
edges e_i,i+1 and e_i+1,i+2 do not span a triangle except
F_n-1,n,n+1 and F_2n-1,2n,1 as the edge sets
{e_n-1,n,e_n,n+1} and {e_2n-1,2n,e_2n,1} span
triangles in the triangular ladder graph L^∗_n. Moreover,
F_i,i+1,j∈Ω(L^∗_n) for indices of types 1≤ i≤
n-1; j=2n+1-i and 1≤ i≤ n-2; j=2n-1-i. Also,
F_i,j,j+1∈Ω(L^∗_n) for indices of types 1≤ i≤
n-2; j=2n-1-i and 2≤ i≤ n-1; j=2n+1-i. Hence the
result.













Let Δ_Γ(L^∗_n) be the Gallai simplicial complex of
triangular ladder graph L^∗_n with 2n vertices for n≥ 3.
Then, the Euler characteristic of Δ_Γ(L^∗_n) is

    χ(Δ_Γ(L^∗_n))=∑_k=0^N(-1)^kf_k=0.



Since, the triangular ladder graph has 2n vertices therefore, we
have f_0=2n.

Moreover, for {l,j,k}∈Δ_Γ(L^∗_n) with 1≤
l≤ 2n-2 and j,k∈ [2n], we have


  * |{1,j,k}|=4 with {j,k}∈{{2,3},{2,2n-2},{2,2n},{2n-2,2n-1}};

  * |{l,j,k}|=5(n-3) for 2≤ l≤ n-2 and
{j,k}∈{{l+1,l+2},{l+1,2n-1-l},{l+1,2n+1-l},{2n-1-l,2n-l},{2n+1-l,2n+2-l}};

  * |{n-1,j,k}|=2 with {j,k}∈{{n,n+2},{n+2,n+3}};

  * |{l,l+1,l+2}|=n-1 for n≤ l≤ 2n-2.

Adding the results from (1) to (4), we get

    |{l,j,k}|=4+5(n-3)+2+(n-1)=6n-10

with 1≤ l≤ 2n-2 and j,k∈ [2n]. Therefore, f_2=6n-10.

Now, for {j,k}∈Δ_Γ(L^∗_n) with 1≤ j≤
2n-1 and k∈ [2n], we have
  
  * |{1,k}|=5, where k∈{2,3,2n-2,2n-1,2n};
  
  * |{j,k}|=6(n-3) with 2≤ j≤ n-2 and k∈{j+1,j+2,2n-1-j,2n-j,2n+1-j,2n+2-j};
  
  * |{n-1,k}|=4, where k∈{n,n+1,n+2,n+3};
  
  * |{j,k}|=2(n-1) with n≤ j≤ 2n-2 and k∈{j+1,j+2};
  
  * |{2n-1,2n}|=1.

Adding the results from (5) to (9), we obtain

    |{j,k}|=5+6(n-3)+4+2(n-1)+1=8n-10,

where 1≤ j≤ 2n-1 and k∈ [2n]. Therefore, f_1=8n-10.

Thus, we compute

    χ(Δ_Γ(L^∗_n))=f_0-f_1+f_2=2n-(8n-10)+(6n-10)=0,

which is the desired result.




The Prism graph Y_3,n is a simple graph defined by the cartesian
product Y_3,n=C_3× P_n with 3n vertices and 3(2n-1)
edges. We label the edge-set of Y_3,n in the following way;

E(Y_3,n)={e_1,2,
e_2,3,e_3,1,e_4,5,e_5,6,e_6,4,…,e_3i+1,3i+2,e_3i+2,3i+3,e_3i+3,3i+1,…,

e_3n-2,3n-1,e_3n-1,3n,e_3n,3n-2,e_1,4,e_4,7,…,e_3n-5,3n-2,e_2,5,e_5,8,…,e_3n-4,3n-1,e_3,6,

e_6,9,…,e_3n-3,3n}, where
e_3i+1,3i+2,e_3i+2,3i+3,e_3i+3,3i+1 for 0≤ i≤ n-1
are the edges of (i+1)-th C_3-cycle.

Let Y_3,n be a prism graph on the vertex set [3n] and edge set E(Y_3,n), with labeling of edges
given above. Then, we have

Ω(Y_3,n)={F_1,2,4,F_1,2,5,F_2,3,5,F_2,3,6,
F_4,5,1,F_4,5,2,F_4,5,7,F_4,5,8,F_5,6,2,
F_5,6,3,F_5,6,8,
F_5,6,9,…,
F_3n-5,3n-4,3n-8,F_3n-5,3n-4,3n-7,F_3n-5,3n-4,3n-2,
F_3n-5,3n-4,3n-1,
F_3n-4,3n-3,3n-7,F_3n-4,3n-3,3n-6,F_3n-4,3n-3,3n-1,F_3n-4,3n-3,3n,
F_3n-2,3n-1,3n-5,
F_3n-2,3n-1,3n-4,F_3n-1,3n,3n-4,F_3n-1,3n,3n-3,
F_3,1,6,F_3,1,4,F_6,4,3, F_6,4,1,F_6,4,9,F_6,4,7,
…,F_3n-3,3n-5,3n-6,F_3n-3,3n-5,3n-8,F_3n-3,3n-5,3n,
F_3n-3,3n-5,3n-2, F_3n,3n-2,3n-3,
F_3n,3n-2,3n-5,
F_1,4,7,…,F_3n-8,3n-5,3n-2,F_2,5,8,
…,F_3n-7,3n-4,3n-1, F_3,6,9,
…, F_3n-6,3n-3,3n}.


By definition, one can easily see that F_3i+1,3i+2,3i+3 does not
belong to Ω(Y_3,n) because 3i+1,3i+2,3i+3 with 0≤
i≤ n-1 are vertices of (i+1)-th C_3-cycle. Therefore, from
construction of all possible triangles in
prism graph Y_3,n, we have

(i) F_j,j+1,j-3,F_j,j+1,j-2∈Ω(Y_3,n) for 4≤
j≤
  3n-1 but j is not multiple of 3;

(ii) F_j,j+1,j+3,F_j,j+1,j+4∈Ω(Y_3,n) for 1≤
j≤
  3n-4 but j is not multiple of 3;

(iii) F_3j,3j-2,3j-3,F_3j,3j-2,3j-5∈Ω(Y_3,n) for
2≤
j≤ n;

(iv) F_3j,3j-2,3j+3,F_3j,3j-2,3j+1∈Ω(Y_3,n) for
1≤
j≤ n-1;

(v) F_j,j+3,j+6∈Ω(Y_3,n) for 1≤ j≤
  3n-6.

Hence the proof.















Let Δ_Γ(Y_3,n) be the Gallai-simplicial complex of
prism graph Y_3,n with 3n vertices for n≥ 3. Then, the
Euler characteristic of Δ_Γ(Y_3,n) is

    χ(Δ_Γ(Y_3,n))=∑_k=0^N(-1)^kf_k=3(n-1).



Since, the prism graph has 3n vertices therefore, we have
f_0=3n.

Now, for {3l+i,j,k}∈Δ_Γ(Y_3,n) with 0≤ l≤
n-2 and j,k∈[3n] such that i=1,2,3, we have

  
  * |{3l+1,j,k}|=7(n-2) with 0≤ l≤ n-3 and
  {j,k}∈{{3l+2,3l+4},{3l+2,3l+5},{3l+3,3l+4},{3l+3,3l+6},{3l+4,3l+5},{3l+4,3l+6},{3l+4,3l+7}};
  
  * |{3l+2,j,k}|=5(n-2) for 0≤ l≤ n-3 and
  {j,k}∈{{3l+3,3l+5},{3l+3,3l+6},{3l+4,3l+5},{3l+5,3l+6},{3l+5,3l+8}};
  
  * |{3l+3,j,k}|=3(n-2) for 0≤ l≤ n-3 and {j,k}∈{{3l+4,3l+6},{3l+5,3l+6},{3l+6,3l+9}};
  
  * |{3n-5,j,k}|=6, where {j,k}∈{{3n-4,3n-2},{3n-4,3n-1},{3n-3,3n-2},{3n-3,3n},{3n-2,3n-1},{3n-2,3n}};
  
  * |{3n-4,j,k}|=4, where {j,k}∈{{3n-3,3n-1},{3n-3,3n},{3n-2,3n-1},{3n-1,3n}};
  
  * |{3n-3,j,k}|=2, where {j,k}∈{{3n-2,3n},{3n-1,3n}}.

Adding the results from (1) to (6), we get

    f_2=7(n-2)+5(n-2)+3(n-2)+6+4+2=15n-18.

Next, for {3j+i,k}∈Δ_Γ(Y_3,n) with 0≤ j≤
n-2 and k∈[3n] such that i=1,2,3, we obtain
  
  * |{3j+1,k}|=6(n-2) with 0≤ j≤ n-3 and
  k∈{3j+2,3j+3,3j+4,3j+5,3j+6,3j+7};
  
  * |{3j+2,k}|=5(n-2) with 0≤ j≤ n-3 and k∈{3j+3,3j+4,3j+5,3j+6,3j+8};
  
  * |{3j+3,k}|=4(n-2) with 0≤ j≤ n-3 and k∈{3j+4,3j+5,3j+6,3j+9};
  
  * |{3n-5,k}|=5, where k∈{3n-4,3n-3,3n-2,3n-1,3n};
  
  * |{3n-4,k}|=4, where k∈{3n-3,3n-2,3n-1,3n};
  
  * |{3n-3,k}|=3, where k∈{3n-2,3n-1,3n}.

Moreover, we have
  
  * |{3n-2,k}|=2, where k∈{3n-1,3n};
  
  * |{3n-1,3n}|=1.

Adding the results from (7) to (14), we get

    f_1=6(n-2)+5(n-2)+4(n-2)+5+4+3+2+1=15n-15.


Hence, we compute

    χ(Δ_Γ(Y_3,n))=f_0-f_1+f_2=3n-(15n-15)+(15n-18)=3(n-1),

which is the desired result.




§ CONSTRUCTION OF F-GALLAI GRAPHS







We introduce first the f-Gallai graph.


A finite simple graph G is said to be f-Gallai graph, if
the edge ideal I(Γ(G)) of the Gallai graph Γ(G) is an
f-ideal.

The following theorem provided us a construction of f-graphs.








 <cit.>.
Let G be a simple graph on n vertices. Then for the
following
constructions, G will be f-graph:

Case(i) When n= 4l. G consists of two components G_1 and G_2
joined with l-edges, where both G_1 and G_2 are the complete
graphs on 2l vertices.

Case(ii) When n= 4l+ 1. G consists of two components G_1 and
G_2 joined with l-edges, where G_1 is the complete graph on
2l vertices and G_2 is the complete graph on 2l+ 1 vertices.







The star graph S_n is a complete bipartite graph K_1,n on
n+1 vertices and n edges formed by connecting a single vertex
(central vertex) to all other vertices.


We establish now the following result.


Let G be a finite simple graph on n vertices of the form n=3l+2 or 3l+3. Then for the following constructions, G will
be f-Gallai graph.

Type 1.  When n=3l+2. G=𝕊_4l is a graph
consisting of two copies of star graphs S_2l and S'_2l with
l≥ 2 having l common vertices.
 Type 2. When n=3l+3.
G=𝕊_4l+1 is a graph consisting of two star graphs
S_2l and S_2l+1 with l≥ 2 having l common vertices.


Type 1. When n=3l+2, the number of edges in
𝕊_4l will be 4l, as shown in figure 𝕊_12
with l=3. Let {e_1,…,e_2l} and {e'_1,…,e'_2l}
be the edge sets of the star graphs S_2l and S'_2l,
respectively such that e_i and e'_i have a common vertex for
each i=1,…,l. While finding Gallai graph
Γ(𝕊_4l) of the graph 𝕊_4l, we observe
that the edges e_1,…,e_2l of the star graph S_2l in
𝕊_4l will induce a complete graph Γ(S_2l) on
2l vertices in the Gallai graph Γ(𝕊_4l), as
shown in figure Γ(𝕊_12) with l=3. Similarly, the
edges e'_1,…,e'_2l of the star graph S'_2l will induce
another complete graph Γ(S'_2l) on 2l vertices in
Γ(𝕊_4l). As, e_i and e'_i are the adjacent
edges in 𝕊_4l for each i=1,…,l. Therefore, e_i
and e'_i will be incident vertices in Γ(𝕊_4l)
for every i=1,…,l. Thus, Gallai graph
Γ(𝕊_4l) having 4l vertices consists of two
components Γ(S_2l) and Γ(S'_2l) joined with l-
edges, where both Γ(S_2l) and Γ(S'_2l) are
complete graphs on 2l vertices. Therefore, by Theorem <ref>,
Γ(𝕊_4l) is f-Gallai graph.


Type 2. When n=3l+3, the number of edges in
𝕊_4l+1 will be 4l+1, see figure 𝕊_13
(where l=3). Let {e_1,…,e_2l} and
{e'_1,…,e'_2l+1} be the edge sets of the star graphs
S_2l and S_2l+1 (respectively) such that e_i and e'_i
share a common vertex for each i=1,…,l. One can easily see
that the edges e_1,…,e_2l of S_2l in
𝕊_4l+1 will induce a complete graph Γ(S_2l) on
2l vertices in the Gallai graph Γ(𝕊_4l+1), see
figure Γ(𝕊_13) (where l=3). Similarly, the edges
e'_1,…,e'_2l+1 of S_2l+1 will induce another complete
graph Γ(S_2l+1) on 2l+1 vertices in
Γ(𝕊_4l+1). Since e_i and e'_i are the adjacent
edges in 𝕊_4l+1 for every i=1,…,l. Therefore,
e_i and e'_i will be incident vertices in the Gallai graph
Γ(𝕊_4l+1) for each i=1,…,l. Thus, the
Gallai graph Γ(𝕊_4l+1) having 4l+1 vertices
consists of two components Γ(S_2l) and Γ(S_2l+1)
joined with l-edges, where Γ(S_2l) and Γ(S_2l+1)
are complete graphs on 2l and 2l+1 vertices, respectively.
Hence, by Theorem <ref>, Γ(𝕊_4l+1) is
f-Gallai graph.




 One can easily see that the Gallai graph of the
line graph L_n is isomorphic to L_n-1 and that of cyclic graph
C_n is isomorphic to C_n. Therefore, both Γ(L_n) and
Γ(C_n) are f-Gallai graphs if and only if n=5, see
<cit.>.


1

AAAB G. Q. Abbasi, S. Ahmad, I. Anwar, W. A. Baig, f-ideals of degree
2, Algebra Colloquium, 19 (2012), no. 1, 921-926.

AKNS I. Anwar, Z. Kosar and S. Nazir, An Efficient Algebraic Criterion For Shellability, arXiv: 1705.09537.

AMBZ I. Anwar, H. Mahmood, M. A. Binyamin and M. K. Zafar, On the Characterization of
f-Ideals, Communications in Algebra 42 (2014), no. 9, 3736-3741.










WBH W. Bruns and J. Herzog, Cohen-Macaulay Rings, Revised
Edition, Cambridge Studies in Advanced Marthematics, Vol. 39,
Cambridge University Press, Cambridge, 1998.

SF S. Faridi, The Facet Ideal of a Simplicial
Complex, Manuscripta Mathematica, 109 (2002), 159-174.

TG T. Gallai, Transitiv Orientierbare Graphen, Acta Math.
Acad. Sci. Hung., 18 (1967), 25-66.

H A. Hatcher, Algebraic Topology, Cambridge
University Press, 2002.







VBL V. B. Le, Gallai Graphs and Anti-Gallai Graphs, Discrete
Math., 159 (1996), 179-189.

MAZ H. Mahmood, I. Anwar, M. K. Zafar, A Construction of Cohen-Macaulay f-Graphs, Journal of Algebra and its
Applications, 13 (2014), no. 6, 1450012-1450019.

M W.S. Massey, Algebraic Topology, An Introduction,
Springer-Verlag, New York, 1977.





