# Omega Index of Line and Total Graphs

Authors: Musa Demirci; Sadik Delen; Ahmet Sinan Cevik; Ismail Naci Cangul
Journal: Journal of Mathematics
 (2021)

---

## Abstract

A derived graph is a graph obtained from a given graph according to some predetermined rules. Two of the most frequently used derived graphs are the line graph and the total graph. Calculating some properties of a derived graph helps to calculate the same properties of the original graph. For this reason, the relations between a graph and its derived graphs are always welcomed. A recently introduced graph index which also acts as a graph invariant called omega is used to obtain such relations for line and total graphs. As an illustrative exercise, omega values and the number of faces of the line and total graphs of some frequently used graph classes are calculated.


---

## Body

## 1. Introduction

LetG be a simple graph with VG=v1,v2,…,vn and EG=e1,e2,…,em as the vertex and edge sets. n and m are called the order and size of G, respectively, and are the most important graph parameters. If e=uv∈EG, we say that u and v are adjacent and e is incident to u and v. The number of edges incident to a vertex v is called the degree of v and denoted by dGv, or by dv if there is no confusion. A vertex of degree 1 is named as the pendant vertex. The set of degrees,(1)1a1,2a2,…,ΔaΔ,of all vertices where Δ is the biggest vertex degree in G, is called the degree sequence of the graph.A graph which is connected and has no cycles is called a tree. A graph is called acyclic, unicyclic, bicyclic, tricyclic, etc. according to the number of cycles it has as 0, 1, 2, 3, etc. As usual, the path, cycle, star, complete, complete bipartite, and tadpole graphs are denoted byPn,Cn,Sn,Kn,Kr,s, and Tr,s, respectively. For other graph theoretical notions used in this paper, see, e.g., [1–3].Given a graphG, the line graph LG of G is the graph whose vertex set is EG with two vertices of LG being adjacent iff corresponding edges in G are adjacent. For some applications of the line graph, see, e.g., [4, 5]. Similarly, the total graph TG of G is the graph whose vertex set is VG∪EG with two vertices of TG being adjacent iff the corresponding elements of G are either adjacent or incident. Line graphs and total graphs are two examples of derived graphs. Minimal doubly resolving sets and strong metric dimension of the layer sun graph and the line graph of this graph are calculated in [4]. The classical meanness property of some graphs based on line graphs was considered in [5]. For some recent applications of the total graphs, see, e.g., [6–8].According to definitions, the degree sequences of the line and total graphs are(2)DSLG=dGu+dGv−2:uv∈EG=dGe:e∈EG,DSTG=dTGv:v∈VG∪dTGe:e∈EG.


## 2. Omega Index and Fundamentals

In this paper, we study the line and total graphs in relation with omega index and the number of faces known as the cyclomatic number. Omega index is an additive quantity defined for a given degree sequence (1) or for a graph with(3)ΩG=∑i=1Δaidi−2.It is shown thatΩG=2m−n and therefore it is always an even number. It is shown that the omega characteristic gives us very powerful information about cyclicness and connectedness of all the realizations of a given degree sequence (see, e.g., [9]). In brief, it is shown that all realizations of a degree sequence D with ΩD≤−4 must be disconnected; each connected realization of a degree sequence D with ΩD=−2 must be a tree; each connected realization of a degree sequence D with ΩD=0 must be a unicyclic graph; each connected realization of a degree sequence D with ΩD=2 must be a bicyclic graph, etc. Also, the number of faces of a graph or all the realizations of a given degree sequence is formulated as(4)rG=ΩG2+cG,where cG is the number of components of G. For more properties of the omega index, see [10, 11]. The effect of edge and vertex deletion on the omega index is studied in [9]. Next, we obtain the number of pendant vertices of a caterpillar tree which consists of a main path so that all vertices are having maximum distance 1 from the path.Theorem 1.
LetG be a caterpillar tree. Let the nonpendant vertices of G be v1,v2,…,vk so that v1 has unique nonpendant neighbor v2; vk has unique nonpendant neighbor vk−1; and vi has two nonpendant vertices vi−1 and vi+1 for i=2,3,…,k−1. The following relation holds:(5)a1G=∑i=1kdGi−2k−1,where dGi is the degree of vi.Proof.
By counting,v1 has only one nonpendant neighbor and hence dG1−1 pendant neighbors, vk has only one nonpendant neighbor and hence dGk−1 pendant neighbors, and similarly, for i=2,3,…,k−1, the vertex vi has dGi−2 pendant neighbors. Therefore,(6)a1G=dG1−1+∑i=2k−1dGi−2+dGk−1=∑i=1kdGi−2−2k−2,thus giving the result.Corollary 1.
For any treeT, we have(7)a1T+k−mT=1.For a caterpillar tree, the degree sequence of its line graph can be stated more deterministically.Theorem 2.
LetT be a caterpillar tree. Let the degrees of the nonpendant vertices of T be dG1,dg2,…,dGk. The degree sequence of the line graph of T is(8)DSLT=dG1−1dG1−1,dG2−1dG2−2,…,dGk−1−1dGk−1−2,dGk−1dGk−1,dG1+dG2−21,dG2+dG3−21,…,dGk−1+dGk−21.Proof.
By Theorem5 in [11], there exists a complete graph KdGi in LT around each nonpendant vertex vi∈VG of degree dTi in T. Also, vi∼vj iff KdTi and KdTj have a common vertex. Therefore, KdT1 has dT1−1 vertices of degree dT1−1; KdTk has dTk−1 vertices of degree dTk−1; and each of other complete graphs KdTi for i=2,3,…,k−1 has dTi−2 vertices of degree dTi−1. Also, the intersection vertex of KdTi and KdTi+1 is of degree dTi−1+dTi+1−1 for i=2,3,…,k−1. Hence, the result follows.The next result gives the relation between the edge numbers ofG and LG by means of the first Zagreb index of G:Lemma 1.
For a given graphG, we have(9)mLG=12M1G−mG.Proof.
By definition, we have(10)mLG=12∑e∈EGde=12∑e=uv∈EGdu+dv−2=12∑u∈VGdu2−∑e∈EG1=12M1G−mG.In the following result, we calculate the omega index of the line graph ofG when G is k-cyclic by means of triangular numbers Tn=nn+1/2.Corollary 2.
For a given graphG with k−cycles, we have(11)ΩLG=2∑i=3ΔaiTi−2−1+k.The following results are about the omega index of the line graph.Theorem 3.
For a graphG, we have(12)ΩLG=M1G−4mG.Proof.
AsDSLG=de1,de2,…,dem and dei=dui+dvi−2, we have(13)ΩLG=∑ei∈EGdei−2=∑uivi∈EGdui+dvi−4=∑u∈VGdu2−4mG=M1G−4mG.Corollary 3.
For a graphG, we have(14)ΩLG=∑i=1ndidi−2.Proof.
By Theorem3,(15)ΩLG=M1G−4mG=∑i=1ndi2−2∑i=1ndi,thus giving the result.Corollary 4.
For a graphG, we have(16)ΩLG=M1G−2ΩG−4nG.Proof.
It follows fromΩG=2mG−nG.Now, we obtain some results on the omega index of the total graphs.Corollary 5.
For a connectedk−cyclic graph G, we have(17)ΩTG=M1G+2k−2.Corollary 6.
For a connectedk−cyclic graph G, we have(18)ΩTG=ΩLG+4mG+2k−2.Proof.
It follows by Corollary5 and Theorem 3.Corollary 7.
For any graphG, we have(19)ΩTG−ΩLG=3ΩG+4nG.Proof.
It follows by the definition of omega index.This means that for every graphG, ΩTG−ΩLG−3ΩG is fixed and is equal to 4nG.In [11], the number of faces of the line graph of a tree T was given by(20)rLT=∑i=3ΔaiTi−2,where Tn=nn+1/2 is the n−th triangular number. In [?], this number for a tricyclic graph G was given by(21)rLG=3+∑i=3ΔaiTi−2.These suggest the following generalization.Theorem 4.
LetG be a simple, connected, and k−cyclic graph with degree sequence (1). The number of faces of the line graph LG is(22)rLG=k+∑i=3ΔaiTi−2.Proof.
For acyclic part ofG, the formula is given in equation (20). For each t−cycleC in G, LG has another t-cycle C′ formed by joining the midpoints of the edges of C. Hence, the number of cycles in G must be added to ∑i=3ΔaiTi−2 giving the result.Inverse problems in mathematics are quite important due to their applications. In graph theory, the inverse problem is the one which deals with finding the values of a given topological graph index. Here, we solve a similar problem for the number of faces of the line graph.Theorem 5.
LetG be a connected graph. Then, rLG can take any positive integer value.Proof.
By Theorem4, we have equation (22) for a simple, connected, k-cyclic graph G. This gives us the following linear equality:(23)rLG=k+a3+3a4+6a5+10a6+⋯+Δ−2Δ−12aΔ.
Asai≥0 are integers and as a3 has coefficient 1, rLG can take any positive integer value.Some special cases are as follows.Corollary 8.
LetT be a tree with no vertices of degree 3. Then, rLT can take all positive integers except 1, 2, 4, 5, 7, 8, 11, 14, and 17.Proof.
By the equality in Theorem 11 in [12], we have(24)rLT=3a4+6a5+10a6+⋯+Δ−2Δ−12aΔ.
Asai≥0 are integers, the result follows.Corollary 9.
LetT be a tree with no vertices of degree 3 or 4. Then, rLT can take all positive integer values except 1,2,3,4,5,7,8,9,11,13,14,17,19,23, and 29.Proof.
Note that(25)rLT=6a5+10a6+15a7+⋯+Δ−2Δ−12aΔ.
After easy observations, we find that the class10+10n has all integers ≥10 ending with 0; 6+10n has all integers ≥6 ending with 6; 2⋅6+10n has all integers ≥12 ending with 2; 3⋅6+10n has all integers ≥18 ending with 8; 21+10n has all integers ≥21 ending with 1; 21+2⋅6+10n has all integers ≥33 ending with 3; 6⋅4+10n has all integers ≥24 ending with 4; 15+10n has all integers ≥15 ending with 5; 15+2⋅6+10n has all integers ≥27 ending with 7; and finally, 21+3⋅6+10n has all integers ≥39 ending with 9. This implies that only the values given above cannot be attainable by rLG.Then, we obtain the following result.Corollary 10.
We have(26)ΩLG−ΩG=2∑ΔaiTi−2.The following variation of this result has useful applications related to cyclicness.Corollary 11.
We have(27)rLG=ΩG2+1+∑i=3ΔaiTi−2.By Corollary11, we have the following cases:(i)
IfG is acyclic, then rLG=∑i=3ΔaiTi−2(ii)
IfG is unicyclic, then rLG=1+∑i=3ΔaiTi−2(iii)
IfG is bicyclic, then rLG=2+∑i=3ΔaiTi−2(iv)
IfG is k-cyclic, then rLG=k+∑i=3ΔaiTi−2


## 3. Omega andr of the Line Graphs of Some Special Graphs

Now, we consider the omega andr values of some frequently used graph classes. First, we give a new proof of the fact that the line graph of Pn is Pn−1.Lemma 2.
We have(28)LPn=Pn−1.Proof.
Recall thatDSPn=12,2n−2. We then have(29)DSLPn=00,10,…,10,00,11,21,…,21,11=12,2n−3=DSPn−1.Hence,ΩLPn=ΩPn−1=−2 as path graphs are acyclic. Also, rLPn=0.Secondly, it is obvious thatLCn=Cn. Therefore, ΩLCn=ΩCn=0 and rLCn=1.Next, we consider the line graph of the star graphSn. By the definition of the line graph, LSn=Kn−1. Hence,(30)ΩLSn=ΩKn−1=n−1n−4,rLSn=rKn−1=n−3n−22.For a complete graphKn, we have DSLKn=2n−2nn−1/2 implying that ΩLKn=nn−1/2⋅2n−6=nn−1n−3 and rLKn=n−2n2−2n−1. In Figure 1, we illustrated the case of K4.Figure 1
Line graph ofK4.For a complete bipartite graphKr,s, LKr,s is a regular graph of degree r+s−2. Its degree sequence is r+s−2rs. Hence, ΩLKr,s=rsr+s−4 and rLKr,s=rsr+s−4/2+1.Finally, consider the tadpole graphTr,s. LTr,s has degree sequence 11,2r+s−4,33. Hence, ΩLTr,s=3−1=2, and therefore, rLTr,s=2.


## 4. Omega andr of the Total Graphs of Some Special Graphs

In this section, we calculate the omega andr values of some frequently used graphs. We first give an important property.Lemma 3.
LetG be a connected graph. Then, TG cannot have any pendant vertex.Proof.
Letv∈VG. Let e be an edge incident to v. As G is connected, there is at least one adjacent vertex say u, to v. In the total graph TG, the vertex v will be adjacent to u and e implying the result.The proof alternatively follows from the fact thatDSTG consists of integers in the form of either 2di or ej+2, where di,ej≥1.Next, we give the relation between omega ofG and omega of TG.Theorem 6.
For a connected graphG, we have(31)ΩTG=ΩG+M1G.Proof.
Recall thatDSTG consists of ai times 2di for every vi∈VG and dej+2’s for every ej=ujvj∈EG. As dej=duj+dvj−2, we can deduce that DSTG consists of ai times 2di for every vi∈VG and duj+dvj’s for every ej=ujvj∈EG. Hence,(32)ΩTG=∑vi∈VGai2di−2+∑ej=ujvj∈EGduj+dvj−2=2mG+ΩG+∑v∈VGdv2−2mG=ΩG+M1G.Corollary 11.
For a connected graphG, we have(33)ΩTG=ΩG+ΩLG+4mG.Proof.
As in Theorem6, we can write(34)ΩTG=∑vi∈VGai2di−2+∑ej∈EGdej=2mG+ΩG+ΩLG+2mG=ΩG+ΩLG+4mG.Corollary 12.
IfG is an acyclic graph, then(35)ΩTG=M1G−2,and if G is a unicyclic graph, then(36)ΩTG=M1G.Finally, we give the following result for the omega indices of the total graphs of some frequently used graph classes:Theorem 7.
The omega index of the total graphs of some well-known graph classes is as follows:(37)ΩTPn=4n−8,ΩTCn=4n,ΩTSn=n+1n−2,ΩTKn=nn+1n−2,ΩTKr,s=r+srs−2+2rs,ΩTTr,s=4r+s+2.


## 5. Conclusion

Derived graphs are graphs obtained from a given graph according to some rules. In this paper, two of the most frequently used derived graphs, the line and total graphs, are studied. Calculating some properties of a derived graph helps to calculate the same properties of the original graph. Here, by means of omega index and several results in recent papers, new relations for line and total graphs are obtained. Also, omega values and the number of faces of the line and total graphs of some frequently used graph classes are calculated. In the future works, similar ideas can be applied to establish several relations for other derived graphs.



---

*Source: 5552202-2021-09-27.xml*