Computational aspects of line simplicial complexes

Abstract

Let G be a finite simple graph. The line graph L (G) represents adjacencies between edges of G. We define first line simplicial complex Δ_L (G) of G containing Gallai and anti-Gallai simplicial complexes Δ_Γ (G) and Δ_Γ′ (G) (respectively) as spanning subcomplexes. We establish the relation between Euler characteristics of line and Gallai simplicial complexes. We prove that the shellability of a line simplicial complex does not hold in general. We give formula for Euler characteristic of line simplicial complex associated to Jahangir graph $J$ _m,n by presenting an algorithm.

Keywords

Euler characteristic Betti number facet ideal connected simplicial complex shellability

1 Introduction

Due to their immense applications in various fields, the study of simplicial complexes is a well established knowledge area of commutative algebra and algebraic topology. Simplicial complexes play the important role in encoding compact topological spaces. It has always been an important tool in topology to encode reasonably nice compact spaces via triangulation. In recent years, this importance has increased as triangulation is a necessary part of protocols for communicating with computers about topological spaces. The study of connectedness of simplicial complex has been of great importance due to various combinatorial and topological aspects, see for instance [5], [18] and [19].

Computing topological invariants is very useful in understanding the shape of an arbitrary object. The Euler characteristic is a number that describes topological space’s shape or structure regardless of the way it is bent. It is a well-known topological and homotopic invariant to classify surfaces. It arises from homological algebra [11, 23].

Let Δ be a simplicial complex of dimension d. The Euler characteristic of Δ is defined as $χ (Δ) = \sum_{k = 0}^{d} (- 1)^{k} f_{k},$

where f_k is the number of k-dimensional faces of Δ. The chain complex C_∗ (Δ) can be expressed as 0 → C_d (Δ) ^→∂_dC_d-1 (Δ) ^→∂_d-1 . . . ^→∂₂C₁ (Δ) ^→∂₁C₀ (Δ) ^→∂₀0,

where C_k (Δ) is a free abelian group generated by all k-dimensional faces of Δ and ∂_k the boundary homomorphism, given by $\partial_{k} (F_{0, \dots, k}) = \sum_{i = 0}^{k} (- 1)^{i} F_{0, \dots, \hat{i}, \dots, k}$

such that the symbol $\hat{i}$ represents that the vertex i is to be deleted from the sequence 0, …, k. The k-th homology group of Δ is the quotient group H_k (Δ) = Ker ∂_k/Im ∂_k+1,

where Ker ∂_k and Im ∂_k+1 are the groups of simplicial k-cycles and k-boundaries, respectively.

The Euler characteristic of a simplicial complex Δ having dimension d is also given by $χ (Δ) = \sum_{k = 0}^{d} (- 1)^{k} β_{k},$

where the k-th Betti number β_k is the rank of k-th homology group H_k (Δ). The Betti numbers were coined by Poincaré after Betti. These numbers are topological objects which were proved to be invariants by Poincaré. He used them to extend the polyhedral formula to higher dimensional spaces. The modern formulation is due to Noether. The Betti numbers are used to distinguish topological spaces based on the connectivity of d-dimensional simplicial complexes. These numbers tell us the maximum amount of cuts that must be made before separating a surface into two pieces. The Betti numbers have applications in signal processing, data aggregation, sensing, bioinformatics and image analysis [6, 14].

The excision is one of the most useful property of Euler characteristic, given by χ (Δ) = χ (C) + χ (Δ ∖ C) ,

for every closed subset C ⊂ Δ. The excision property has a dual form χ (Δ) = χ (U) + χ (Δ ∖ U) ,

for every open subset U ⊂ Δ. This property is frequently used under the guise of the inclusion-exclusion formula.

The shellability of a simplical complex Δ is a well-studied combinatorial property that carries strong geometric and algebraic interpretations, see for instance [3 , 22] and [24]. In many situations, proving shellability is the most efficient way of establishing Cohen-Macaulayness [3]. The algebraic criterion for shellability of a simplicial complex has been first introduced by A. Dress [7]. Eagon and Reiner [8] gave algebraic criterion of pure shellability of a dual simplicial complex $\overset{ˇ}{Δ}$ in the context of the Stanley-Reisner ideal theory.

In this note, we define first line simplicial complex Δ_L (G) associated to a finite simple graph G (see Definition 2.3), which is the generalization of line graph L (G). The notion of line graph was first introduced by Harary and Norman [10], which provides us main stream line of this work. The properties of line graph L(G) have been studied by many authors, see for instance [1 , 20 and 21]. The line graph L (G) is a graph having edges of G as its vertices and two distinct edges of G are adjacent in L (G) if they are adjacent in G. It contains Gallai and anti-Gallai graphs Γ (G) and Γ′ (G) as spanning subgraphs, which have edges of G as their vertices. Two edges of G are adjacent in Gallai graph Γ (G) (respectively anti-Gallai graph Γ′ (G)) if they are incident but do not span (respectively span) a triangle in G. The anti-Gallai graph Γ′ (G) is the complement of Γ (G) in L (G) [9, 15]. The line simplicial complex contains Gallai simplicial complex Δ_Γ (G) and anti-Gallai simplicial complex Δ_Γ′ (G) as spanning subcomplexes. For Gallai simplicial complex, we refer [19]. The anti-Gallai simplicial complex Δ_Γ′ (G) is the complement of Δ_Γ (G) in Δ_L (G).

In Theorem 3.2, we establish the relation between Euler characteristics of line and Gallai simplicial complexes.

In Proposition 4.1, we prove that the shellability of line simplicial complexes does not hold in general. In Proposition 4.2, we show that the line simplicial complex Δ_L (W_n+1) of wheel graph W_n+1 is shellable.

In Theorem 5.3, we give formula for Euler characteristic of line simplicial complex associated to Jahangir graph $J$ _m,n by presenting an algorithm.

2 Basic setup

A simplicial complex Δ on the vertex set [n] = {1, …, n} is a subset of 2^[n] with the property that if F ∈ Δ then every subset of F will belong to Δ. The members of Δ are called faces and the maximal faces under inclusion are called facets.

If $F (Δ) = {F_{1}, \dots, F_{h}}$ is the set of all facets of Δ, then Δ = 〈F₁, …, F_h〉 . A subcomplex of the simplicial complex Δ is a simplicial complex whose facet set is the subset of $F (Δ)$ .

The dimension of a face F ∈ Δ is given by dim F = ∣ F ∣ -1, where ∣F∣ is the number of vertices of F. The dimension of the simplical complex Δ is defined by dim Δ = max {dim F| F ∈ Δ} . A simplicial complex Δ is said to be pure if it has all facets of the same dimension.

Let Δ be a simplicial complex of dimension d. The f-vector of Δ is defined as (f₀, …, f_d), where f_k is the number of k-cells of Δ. The Euler characteristic of the simplicial complex Δ is given by $χ (Δ) = \sum_{k = 0}^{d} (- 1)^{k} f_{k} .$

A simplicial complex Δ is said to be connected if for any two facets F and $\tilde{F}$ of Δ, there exists a sequence of facets $F = F_{0}, \dots, F_{q} = \tilde{F}$ such that F_i∩ F_i+1 ≠ ∅ for any i = 0, …, q-1. A disconnected simplicial complex is a complex which is not connected. That is, the vertex set [n] of Δ can be written as disjoint union of two non-empty subsets V₁ and V₂ of [n] such that no face of Δ has vertices in both V₁ and V₂, see [5] and [18].

A simplicial complex Δ over [n] is shellable if its facets can be ordered F₁, F₂, …, F_s such that the subcomplex ${\hat{Δ}}_{〈 F_{i} 〉} = 〈 F_{1}, F_{2}, \dots, F_{i - 1} 〉 \cap 〈 F_{i} 〉$ is pure of dimension dim (F_i) -1 for all 2 ≤ i ≤ s, see [3] and [24].

In [10], Harary and Norman define the line graph L (G) of a finite simple graph G, which provides the main streamline of this work.

Definition 2.1. [10] Let G be a finite simple graph. The graph L (G) is said to be line graph of G if each vertex of L (G) represents an edge of G and two vertices of L (G) are adjacent if and only if their corresponding edges are incident in G.

We define now line indices associated to a finite simple graph G, which plays a key role in the structural study of the line simplicial complex Δ_L (G).

Definition 2.2. Let G be a finite simple graph on the vertex set V (G) = [n]. Let $E (G) = {e_{i, j} | i, j \in V (G)}$ be the edge set of G. A set ϒ (G) of all line indices of G is a collection of subsets of V (G) such that if e_i,j and e_j,k are adjacent in L (G), then $F_{i, j, k} = {i, j, k} \in ϒ (G)$ or if e_i,j is an isolated vertex in L (G) then $F_{i, j} = {i, j} \in ϒ (G) .$

Definition 2.3. A line simplicial complex Δ_L (G) of G is a simplicial complex on the vertex set V (G) such that $Δ_{L} (G) = 〈 F | F \in ϒ (G) 〉,$ where ϒ (G) is the set of all line indices of G.

The line index is said to be a Gallai index if the incident edges e_i,j and e_j,k of G do not span a triangle in G, see [19]. The set of all Gallai indices is denoted by Ω_Γ (G). The line index is said to be an anti-Gallai index if the incident edges e_i,j and e_j,k of G lie on a triangle in G. The set of all anti-Gallai indices is denoted by Ω_Γ′ (G). The Gallai and anti-Gallai simplicial complexes Δ_Γ (G) and Δ_Γ′ (G) are generated by the sets of all Gallai and anti-Gallai indices, respectively.

3 Euler characteristic of line simplicial complexes

We prove first necessary and sufficient condition for a line simplicial complex Δ_L (G) to be connected.

Lemma 3.1. Let G be a finite simple graph on vertex set [n]. Then, the graph G is connected if and only if the line simplicial complex Δ_L (G) is connected.

Proof. Let G be a finite simple graph on vertex set [n]. For n ≤ 3, the result is trivial. Therefore, we take n ≥ 4. We establish first the direct implication. On contrary, we assume that the line simplicial complex Δ_L (G) is not connected. By definition, there exist two non-empty subsets V₁ and V₂ of V (Δ_L (G)) = [n] such that [n] = V₁ ∪ V₂ and V₁∩ V₂ = ∅ with the property that any facet of Δ_L (G) either has vertices from V₁ or V₂. Since G is connected graph on [n] with n ≥ 4, therefore the line simplicial complex Δ_L (G) is pure of dimension 2. So, there are facets, say F_i,j,k, F_l,m,p ∈ Δ_L (G) for every $i \neq j \neq k \in V_{1} \subset [n]; l \neq m \neq p \in V_{2} \subset [n]$ such that e_i,j, e_j,k; e_l,m, e_m,p are pairs of adjacent vertices of line graph L (G). Therefore, the edges e_i,j, e_j,k; e_l,m, e_m,p are pairs of incident edges in G for every i, j, k ∈ V₁; l, m, p ∈ V₂ with [n] = V₁ ∪ V₂ such that V₁∩ V₂ = ∅, a contradiction.

Now, we prove the converse implication. On contrary, we assume that the graph G is not connected. Therefore, there exist two non-empty subsets V₁ and V₂ of V (G) = [n] such that [n] = V₁ ∪ V₂ and V₁∩ V₂ = ∅ with the property that there are vertices, say r and s in G such that no path in G has r and s as end points for every r ∈ V₁ and s ∈ V₂. It implies that there is no face of Δ_L (G) containing both vertices r and s for every r ∈ V₁ and s ∈ V₂ i.e. Δ_L (G) is not connected, a contradiction. Hence the result.□

We establish now the relation between Euler characteristics of line and Gallai simplicial complexes.

Theorem 3.2. Let Δ_L (G) and Δ_Γ (G) be line and Gallai simplicial complexes of a finite simple graph G. Then, the Euler characteristic of the line simplicial complex Δ_L (G) is given by $χ (Δ_{L} (G)) = χ (Δ_{Γ} (G)) + ∣ Ω_{Γ^{'}} (G) ∣,$ where ∣Ω_Γ′ (G)∣ is the number of anti-Gallai indices associated to G.

Proof. Let G be a finite simple graph consisting of t connected components G₁, …, G_t. Then,

$G = \cup_{k = 1}^{t} G_{k}$ such that G_i∩ G_j = ∅ for every i, j = 1, …, t with i ≠ j. By Lemma 3.1, the line simplicial complex Δ_L (G) also consists of t connected components Δ_L (G₁) , …, Δ_L (G_t). Therefore, the line simplicial complex can be expressed as $Δ_{L} (G) = \cup_{k = 1}^{t} Δ_{L} (G_{k})$ such that Δ_L (G_i)∩ Δ_L (G_j) = ∅ for all i, j = 1, …, t with i ≠ j.

By the excision property, the Euler characteristic of the line simplicial complex Δ_L (G) is given by $χ (Δ_{L} (G)) = \sum_{k = 1}^{t} χ (Δ_{L} (G_{k})) .$ Let Δ_Γ (G_k) and Δ_Γ′ (G_k) be Gallai and anti-Gallai simplicial complexes associated to each connected component G_k of graph G for k = 1, …, t. Then, each connected component Δ_L (G_k) of Δ_L (G) contains Δ_Γ (G_k) and Δ_Γ′ (G_k) as spanning subcomplexes for k = 1, …, t. Therefore, by definition, the Euler characteristic of each connected component Δ_L (G_k) of Δ_L (G) is given by $χ (Δ_{L} (G_{k})) = χ (Δ_{Γ} (G_{k})) + ∣ Ω_{Γ^{'}} (G_{k}) ∣,$ where Ω_Γ′ (G_k) is the set of all anti-Gallai indices associated to G_k for k = 1, …, t. Consequently,

$χ (Δ_{L} (G)) = \sum_{k = 1}^{t} χ (Δ_{Γ} (G_{k})) + \sum_{k = 1}^{t} ∣ Ω_{Γ^{'}} (G_{k}) ∣$ = χ (Δ_Γ (G))+ ∣ Ω_Γ′ (G) ∣ due to excision property. Hence proved.□

Example 3.3. Consider the graph G given in Figure 1.

Fig. 1

Graph G.

Then, the line simplicial complex of G is given by Δ_L (G) = 〈{1, 2, 3} , {1, 3, 4} , {2, 3, 4} 〉 .

Therefore, χ (Δ_L (G)) = f₀-f₁ + f₂ = 1, where f_i is the number of i-dimensional faces of Δ_L (G).

The Gallai simplicial complex of G is given by Δ_Γ (G) = 〈{1, 2} , {1, 3, 4} , {2, 3, 4} 〉 .

We compute χ (Δ_Γ (G)) = g₀-g₁ + g₂ = 0, where g_i is the number of i-dimensional faces of Δ_Γ (G).

Note that ∣Ω_Γ′ (G) ∣ =1. Therefore, χ (Δ_L (G)) = χ (Δ_Γ (G)) + ∣ Ω_Γ′ (G) ∣ .

Remark 3.4. Let G be a finite simple graph. If there is no triangle in G, then there will be no anti-Gallai index in ϒ (G) i.e. Ω_Γ′ (G) =∅ and hence the line and Gallai simplicial complexes of G are coincident.

4 Shellability of line simplicial complexes

In the following result, we prove that the line simplicial complexes are not shellable in general.

Proposition 4.1. The line simplicial complexes are not shellable in general.

Proof. Consider the line simplicial complex Δ_L (C₅) = 〈{1, 2, 3} , {2, 3, 4} , {3, 4, 5} , {4, 5, 1} , {5, 1, 2} 〉 associated to the cycle C₅ on 5 vertices. We prove that Δ_L (C₅) is not shellable. On contrary, we assume that Δ_L (C₅) is shellable and F₁, F₂, F₃, F₄, F₅ is a shelling order of the facets of Δ_L (C₅). Without loss of generality, we may assume that F₁ = {1, 2, 3} and F₂ = {2, 3, 4}. Since 〈F₁, F₂〉 ∩ {4, 5, 1} = 〈{1} , {4} 〉 is not of dimension 1, it follows that F₃ ≠ {4, 5, 1}.

Also observe that F₃ ≠ {5, 1, 2} since otherwise the subcomplexes 〈F₁, F₂, F₃〉 ∩ {3, 4, 5} = 〈{3, 4} , {5} 〉 and 〈F₁, F₂, F₃〉 ∩ {4, 5, 1} = 〈{4} , {1, 5} 〉 are nonpure. Thus we must have F₃ = {3, 4, 5}. But then we have nonpure subcomplexes 〈F₁, F₂, F₃〉 ∩ {4, 5, 1} = 〈{4, 5} , {1} 〉 and 〈F₁, F₂, F₃〉 ∩ {5, 1, 2} = 〈{1, 2} , {5} 〉 . So, there is no choice for F₄, which is a contradiction.□

In the following result, we prove that the line simplicial complex of wheel graph W_n+1 is shellable.

Proposition 4.2. The line simplicial complex Δ_L (W_n+1) of wheel graph W_n+1 is shellable.

Proof. Let W_n+1 be the wheel graph on n + 1 vertices having edge set E (W_n+1) = {e_1,2, e_2,3, …, e_n,1, e_1,n+1, …, e_n,n+1} , as shown in the Figure 2.

Fig. 2

Wheel Graph W_n+1.

We fix shelling order of the facets of line simplicial complex Δ_L (W_n+1), given by Δ_L (W_n+1) = 〈F_1,2,n+1, …, F_1,n,n+1, F_2,3,n+1, …, F_n-1,n,n+1, F_1,2,3, …, F_n,1,2〉 .

We establish result into the following steps.

Step 1. For the facets F_1,2,n+1, …, F_1,n,n+1, the subcomplex ${\hat{Δ}}_{〈 F_{1, i, n + 1} 〉} = 〈 F_{1, 2, n + 1}, \dots, F_{1, i - 1, n + 1} 〉 \cap 〈 F_{1, i, n + 1} 〉$ = 〈F_1,n+1〉 is pure of dimension 1 for 3 ≤ i ≤ n.

Step 2. For the facets F_2,3,n+1, …, F_2,n,n+1, …, F_n-1,n,n+1, the subcomplex ${\hat{Δ}}_{〈 F_{j, k, n + 1} 〉}$ is pure of dimension 1 due to 〈F_1,2,n+1, …, F_1,n,n+1, F_2,3,n+1, …, F_j,k-1,n+1〉 ∩ 〈F_j,k,n+1〉 = 〈F_j,n+1, F_k,n+1〉 for 1 < j < k ≤ n such that k ≠ j + 1 and 〈F_1,2,n+1, …, F_1,n,n+1, …, F_j-1,n,n+1〉 ∩ 〈F_j,k,n+1〉 = 〈F_j,n+1, F_k,n+1〉 for 1 < j < k ≤ n with k = j + 1.

Step 3. For the facets F_1,2,3, F_2,3,4, …, F_n-2,n-1,n, the subcomplex ${\hat{Δ}}_{〈 F_{i, i + 1, i + 2} 〉}$ is pure of dimension 1 due to 〈F_1,2,n+1, …, F_1,n,n+1, …, F_n-1,n,n+1〉 ∩ 〈F_i,i+1,i+2〉 = 〈F_i,i+1, F_i+1,i+2, F_i,i+2〉 for i = 1 and 〈F_1,2,n+1, …, F_1,n,n+1, …, F_n-1,n,n+1, F_1,2,3, …, F_i-1,i,i+1〉 ∩ 〈F_i,i+1,i+2〉 = 〈F_i,i+1, F_i+1,i+2, F_i,i+2〉 for 2 ≤ i ≤ n-2.

Step 4. Finally, the subcomplexes ${\hat{Δ}}_{〈 F_{n - 1, n, 1} 〉}$ and ${\hat{Δ}}_{〈 F_{n, 1, 2} 〉}$ are pure of dimension 1 due to 〈F_1,2,n+1, …, F_1,n,n+1, F_2,3,n+1, …, F_2,n,n+1, …, F_n-1,n,n+1, F_1,2,3, …, F_n-2,n-1,n〉 ∩ 〈F_n-1,n,1〉 = 〈F_1,n-1, F_1,n, F_n-1,n〉 and 〈F_1,2,n+1, …, F_1,n,n+1, F_2,3,n+1, …, F_2,n,n+1, …, F_n-1,n,n+1, F_1,2,3, …, F_n-2,n-1,n, F_n-1,n,1〉 ∩ 〈F_n,1,2〉 = 〈F_1,2, F_1,n, F_2,n〉, respectively.

Hence the result.□

5 Betti numbers of line simplicial complexes

Let Δ be a simplicial complex of dimension d. The chain complex of Δ C_∗ (Δ) : 0 → C_d (Δ) ^→∂_dC_d-1 (Δ) ^→∂_d-1 . . . ^→∂₂C₁ (Δ) ^→∂₁C₀ (Δ) ^→∂₀0

is a sequence of homomorphisms of free abelian groups C_k (Δ) generated by all k-dimensional faces of Δ. The boundary homomorphism ∂_k is given by $\partial_{k} (F_{0, \dots, k}) = \sum_{i = 0}^{k} (- 1)^{i} F_{0, \dots, \hat{i}, \dots, k},$ (1) where the symbol $\hat{i}$ means that the vertex i is to be deleted from the sequence 0, …, k. The k-th homology group of Δ is the quotient group $H_{k} (Δ) = Ker \partial_{k} / Im \partial_{k + 1},$ where Ker ∂_k and Im ∂_k+1 are the groups of simplicial k-cycles and k-boundaries, respectively. The rank of k-th homology group H_k (Δ) is known as k-th Betti number, given by $β_{k} (Δ) = rank (Ker \partial_{k}) - rank (Im \partial_{k + 1}) .$ (2) The Betti numbers are used to classify topological spaces. The k-th Betti number β_k represents the number of k-dimensional holes on a topological space. see [11] and [23].

The Jahangir graph $J$ _m,n on mn + 1 vertices is a graph consisting of a cycle C_mn with one additional vertex which is adjacent to n vertices of C_mn at distance m to each other on C_mn, as shown in Figure 3. It consists of a cycle C_mn which is further divided into n consecutive cycles C_j of equal length m + 2 such that all these cycles have one vertex common and every pair of consecutive cycles has exactly one edge common [16].

Fig. 3

Jahangir Graph $J$ _m,n.

The following result gives us a combinatorial buildup of the line simplicial complex of Jahangir graph $J$ _m,n.

Lemma 5.1. Let $J_{m, n}$ be Jahangir graph on mn + 1 vertices with labeling of edges given in Figure 3. The line simplicial complex of Jahangir graph $J$ _m,n is given by $Δ_{L} (J_{m, n}) = 〈 F_{1, 2, 3}, F_{2, 3, 4}, \dots, F_{mn, 1, 2}, F_{1, m + 1, mn + 1}, F_{1, 2 m + 1, mn + 1}, \dots, F_{1, m (n - 1) + 1, mn + 1}, F_{m + 1, 2 m + 1, mn + 1}, F_{m + 1, 3 m + 1, mn + 1}, \dots, F_{m + 1, m (n - 1) + 1, mn + 1}, \dots, F_{m (n - 2) + 1, m (n - 1) + 1, mn + 1}, F_{m, m + 1, mn + 1}, F_{2 m, 2 m + 1, mn + 1}, \dots, F_{mn, 1, mn + 1}, F_{1, 2, mn + 1}, F_{m + 1, m + 2, mn + 1}, \dots, F_{m (n - 1) + 1, m (n - 1) + 2, mn + 1} 〉$ .

Proof. By Definition 2.3, the line simplicial complex $Δ_{L} (J_{m, n})$ can be constructed into the following steps.

(i) $F_{i, i + 1, i + 2} \in Δ_{L} (J_{m, n})$ for 1 ≤ i ≤ mn-2;

(ii) $F_{i - 1, i, 1}, F_{i, 1, 2}, F_{i, 1, i + 1} \in Δ_{L} (J_{m, n})$ for i = mn;

(iii) $F_{m (i) + 1, m (j) + 1, mn + 1} \in Δ_{L} (J_{m, n})$ for 0 ≤ i < j ≤ n-1;

(iv) $F_{m (i), m (i) + 1, mn + 1} \in Δ_{L} (J_{m, n})$ for 1 ≤ i ≤ n-1;

(v) $F_{m (i) + 1, m (i) + 2, mn + 1} \in Δ_{L} (J_{m, n})$ for 0 ≤ i ≤ n-1. Hence the result.□

We find now the f-vector of line simplicial complex $Δ_{L} (J_{m, n})$ .

Lemma 5.2. Let $Δ_{L} (J_{m, n})$ be line simplicial complex associated to Jahangir graph $J_{m, n}$ on the vertex set [mn + 1] with n ≥ 2 and m ≥ 3. Then, the f-vector (f₀, f₁, f₂) of $Δ_{L} (J_{m, n})$ is $(mn + 1, \frac{4 mn + n^{2} + 5 n}{2}, \frac{2 mn + n^{2} + 3 n}{2}) .$

Proof. The line simplicial complex $Δ_{L} (J_{m, n})$ is pure of dimension 2, see Lemma 5.1. One can easily see that f₀ = mn + 1. The number of 2-dimensional faces of $Δ_{L} (J_{m, n})$ can be counted into the following steps.

(1) ∣ {F_i,i+1,i+2 : 1 ≤ i ≤ mn-2} ∣ = mn-2;

(2) ∣ {F_mn-1,mn,1, F_mn,1,2, F_mn,1,mn+1} ∣ =3;

(3) $∣ {F_{m (i) + 1, m (j) + 1, mn + 1} : 0 \leq i < j \leq n - 1} ∣ = \frac{n (n - 1)}{2}$ ;

(4) ∣ {F_{m(i),m(i)+1,mn+1} : 1 ≤ i ≤ n-1} ∣ = n-1;

(5) ∣ {F_{m(i)+1,m(i)+2,mn+1} : 0 ≤ i ≤ n-1} ∣ = n. Therefore, $f_{2} = \frac{2 mn + n^{2} + 3 n}{2}$ .

Now, we count the number of edges of $Δ_{L} (J_{m, n})$ into the following steps.

(1) ∣ {F_i,i+1 : 1 ≤ i ≤ mn-1} ∣ = mn-1;

(2) ∣ {F_i,i+2 : 1 ≤ i ≤ mn-2} ∣ = mn-2;

(3) $∣ {F_{m (i) + 1, m (j) + 1} : 0 \leq i < j \leq n - 1} ∣ = \frac{n (n - 1)}{2}$ ;

(4) ∣ {F_m(i)+1,mn+1 : 0 ≤ i ≤ n-1} ∣ = n;

(5) ∣ {F_m(i)+2,mn+1 : 0 ≤ i ≤ n-1} ∣ = n;

(6) ∣ {F_m(i),mn+1 : 1 ≤ i ≤ n} ∣ = n;

(7) ∣ {F_mn,j : j = 1, 2} ∣ =2;

(8) ∣ {F_mn-1,1} ∣ =1 . Therefore, $f_{1} = \frac{4 mn + n^{2} + 5 n}{2}$ . Hence proved.□

In the following result, we give formula for Euler characteristic of line simplicial complex of Jahangir graph $J$ _m,n by presenting an algorithm.

Theorem 5.3. The Euler characteristic of line simplicial complex Δ_L ( $J$ _m,n) is 1-n for n ≥ 2 and m ≥ 3.

Proof. We take n ≥ 2 and m ≥ 3. The other cases may be treated separately.

By Lemma 5.1, the line simplicial complex $Δ_{L} (J_{m, n})$ is pure of dimension 2. Therefore, the chain complex of Δ_L ( $J$ _m,n) can be written as $0 \overset{\partial_{3}}{\to} Z f_{2} \overset{\partial_{2}}{\to} Z f_{1} \overset{\partial_{1}}{\to} Z f_{0} \overset{\partial_{0}}{\to} 0,$ where f_i with i = 0, 1, 2 are given in Lemma 5.2.

By Eq. (1), the boundary homomorphisms ∂_k are matrices of order f_k-1 × f_k with k = 1, 2.

Now, we present an algorithm to find ranks of ∂_k with k = 1, 2 using successive steps of Lemmas 5.1 and 5.2.

1. Begin

2. Input the value of n ≥ 2

3. Input the value of m ≥ 3

4. Store the boundaries of edges e_ij in the form of

5. alternating sum of vertices v_j-v_i,

6. //see Equation (1).

7. AlternatingSum1=[]

8. do i from 1 to m

9. equation= v [i + 1]-v [i]

10. AlternatingSum1[i] =equation

11. end do

12. AlternatingSum2=[]

13. do i from 1 to m * n-2

14. equation= v [i + 2]-v [i]

15. AlternatingSum2[i] =equation

16. end do

17. AlternatingSum3=[]

18. do i from m to m * n-m

19. if rem(i, m) =0, then

20. equation= v [m * n + 1]-v [i]

21. AlternatingSum3[i] =equation

22. end if

23. end do

24. AlternatingSum4=[]

25. do i from 2 to m * (n-1) +2

26. if rem(i, m) =2, then

27. equation= v [m * n + 1]-v [i]

28. AlternatingSum4[i] =equation

29. end if

30. end do

31. AlternatingSum5=[]

32. do i from 1 to m * (n-1) +1

33. do j from i + m to m * n + 1

34. if rem(i, m) =1 and rem(j, m) =1,

35. then equation= v [j]-v [i]

36. AlternatingSum5[i] =equation

37. end if

38. end do

39. end do

40. AlternatingSum6=[]

41. do i from 1 to 2

42. equation= v [m * n]-v [i]

43. AlternatingSum6[i] =equation

44. end do

45. AlternatingSum7= v [m * n-1]-v [1]

46. Create matrix of coefficients from

47. AlternatingSum1 to AlternatingSum7 and

48. store it in matrix ∂₁

49. Compute rank (∂₁)

50. //Store the boundaries of 2-dimensional faces

51. //F_ijk in the form of alternating sum of edges

52. //e_jk-e_ik + e_ij, see Equation (1).

53. AlternatingSum8=[]

54. do i from 1 to m * n-2

55. equation= e [i + 1, i + 2]-e [i, i + 2] + e [i, i + 1]

56. AlternatingSum8[i] =equation

57. end do

58. AlternatingSum9=[]

59. do i from 1 to m * (n-2) +1

60. do j from i + m to m * (n-1) +1

61. if rem(i, m) =1 and rem(j, m) =1,

62. then equation= e [j, m * n + 1]-

63. e [i, m * n + 1] + e [i, j]

64. AlternatingSum9[i] =equation

65. end if

66. end do

67. end do

68. AlternatingSum10=[]

69. do i from 1 to m * (n-1) +1

70. if rem(i, m) =1, then

71. equation=e [i + 1, m * n + 1]-

72. e [i, m * n + 1] + e [i, i + 1]

73. AlternatingSum10[i] =equation

74. end if

75. end do

76. AlternatingSum11=[]

77. do i from m to m * (n-1)

78. if rem(i, m) =0, then

79. equation= e [i + 1, m * n + 1]-

80. e [i, m * n + 1] + e [i, i + 1]

81. AlternatingSum11[i] =equation

82. end if

83. end do

84. AlternatingSum12=[]

85. do i from m * n-1 to m * n

86. equation= e [i, i + 1]-e [1, i + 1] + e [1, i]

87. AlternatingSum12[i] =equation

88. end do

89. AlternatingSum13= e [2, m* n]-e [1, m * n] +

90. e [1, 2]

91. Create matrix of coefficients from

92. AlternatingSum8 to AlternatingSum13 and

93. store it in matrix ∂₂

94. Compute rank (∂₂)

One can see that rank (∂₁) = mn ; rank (∂₂) = f₂ . Note that rank (Ker ∂₀) = f₀ and rank (Im ∂₃) =0. By dimension theorem of vector spaces, we have rank (Ker ∂₁) = f₁-mn and rank (Ker ∂₂) =0 . By Eq. (2), the Betti numbers of Δ_L ( $J$ _m,n) are given by (β₀, β₁, β₂) = (1, n, 0) using Lemma 5.2.

Therefore, χ (Δ_L ( $J$ _m,n)) = β₀-β₁ + β₂ = 1-n for n ≥ 2 and m ≥ 3.□

6 Conclusion

Simplicial complexes have many applications in algebraic topology and commutative algebra. Computing topological invariants has been of great importance in understanding the shape of an arbitrary object. It has been a great development of recent years in applying topological tools to signal processing, data aggregation, sensing, bioinformatics and image processing.

We introduce line simplicial complex Δ_L (G) of a finite simple graph G as a generalization of line graph L (G). The Euler characteristic is a well studied topological and homotopic invariant to classify surfaces. We establish the relation between Euler characteristics of line and Gallai simplicial complexes. Moreover, we present an algorithm to device formula for Euler characteristic of line simplicial complex associated to Jahangir graph $J$ _m,n on mn + 1 vertices. The shellability of a simplicial complex carries strong geometric and algebraic interpretations. We prove that the shellability of line simplicial complexes does not hold in general.

Footnotes

Acknowledgment

Authors are thankful to Higher Education Commission, Pakistan for its partial support.

References

Akram

, Habib

and Koam

A.N.A.

, A Novel Description on Edge-Regular q-Rung Picture Fuzzy Graphs with Application, Symmetry 11 (2019), 489.

Akram

and Adeel

, m-Polar Fuzzy Graphs and m-Polar Fuzzy Line Graphs, Journal of Discrete Mathematical Sciences and Cryptography 20(8) (2017), 1597–1617.

Björner

and Wachs

M.L.

, On Lexicographically Shellable Posets, I Trans Amer Math Soc 277 (1983), 323–341.

Björner

and Wachs

M.L.

, Shellable Nonpure Complexes and Posets, I Trans Amer Math Soc 348(4) (1996), 1299–1327.

Buchstaber

V.M.

and Panov

T.E.

, Toric Topology, Mathematical Surveys and Monographs, 204, American Mathematical Society, Providence, RI, 2015.

Chen

and Rong

, Digital Topological Method for Genus and Betti Numbers, Topology and Its Applications 157 (2010), 1931–1936.

Dress

, A New Algebraic Criterion for Shellability, Beitr Algebr Geom 34(1) (1993), 45–55.

Eagon

J.A.

and Reiner

, Resolution of Stanley-Reisner Rings and Alexander Duality, J Pure Appl Algebra 130(3) (1998), 265–275.

Gallai

, Transitiv Orientierbare Graphen, Acta Math Acad Sci Hung 18 (1967), 25–66.

10.

Harary

and Norman

R.Z.

, Some Properties of Line Digraphs, Rend Circ Mat Palermo 9(2) (1960), 161–168.

11.

Hatcher

, Algebraic Topology, Cambridge University Press, (2002).

12.

Hemminger

R.L.

, Line Digraphs, Graph Theory and Applications, Lecture Notes in Mathematics, 303 Springer, Berlin, Heidelberg, (1972).

13.

Herzog

and Popescu

, Finite Filtrations of Modules and Shellable Multicomplexes, Manusccripta Math 121(3) (2006), 385–410.

14.

Kaczynski

, Michaikow

and Mrozek

, Computational Homology, Applied Mathematics Sciences 157 Springer, (2004).

15.

V.B.

, Gallai Graphs and Anti-Gallai Graphs, Discrete Math 159 (1996), 179–189.

16.

Lourdusamy

, Jeyaseelan

S.S.

and Mathivanan

, On Pebbling Jahangir Graph, Gen Math Notes 5(2) (2011), 42–49.

17.

Lü

and Xu

J.M.

, Super Connectivity of Line Graphs and Digraphs, Acta Math App Sinica 22(1) (2006), 43–48.

18.

Mahmood

, Anwar

, Binyamin

M.A.

and Yasmeen

, On the Connectedness of f-Simplicial Complexes, Journal of Algebra and its Applications 16(1) (2017), 1750017–1750026.

19.

Muhmood

, Ahmed

and Liaquat

, Gallai Simplicial Complexes, Journal of Intelligent and Fuzzy Systems 36(6) (2019), 5645–5651.

20.

Prisner

, Line Graphs and Generalizations - A Survey, Congressus Numerantum 116 (1996), 193–229.

21.

Ray-Chaudhuri

D.K.

, Characterization of Line Graphs, Journal of Combinatorial Theory 3 (1967), 201–214.

22.

Rehmati-Asghar

, k-Shellable Simplicial Complexes and Graphs, Mathematica Scandinavica 122(2) (2018), 161–178.

23.

Rotman

J.J.

, An Introduction to Algebraic Topology, Springer-Verlag, New York, (1998).

24.

Stanley

R.P.

, Combinatorics and Commutative Algebra, Second edition, Progress in Mathematics, 41 Birkhuser Boston, MA, 1996, ISBN:0-8176-3836-9.