On the skewness of graphs resulting from various graph operations

Subject Areas : Statistics

Zahra Barati ^{1 *} , Mojgan Afkhami ² , Kazem Khashyarmanesh ³

1 - Department of Mathematics, Kosar University of Bojnord, Bojnord, Iran
2 - Department of Mathematics, University of Neyshabur
3 - Department of Pure Mathematics, Ferdowsi University of Mashhad

Received: 2022-01-07 Accepted : 2023-01-28 Published : 2024-09-25

Keywords: -خمیده, الحاق دو گراف, کرونای رأسی, کرونای یالی, خمیدگی, &pi,

Abstract :

We say a graph G=(V,E) is planar when we can draw it on the plane in such a way that its edges only intersect with each other at their ends. Also, the skewness of a graph G, denoted by sk(G), is equal to the minimum number of edges that by deleting them from G, the resulted graph is planar. In graph theory, this number is used as a parameter that measures how close a graph is to planarity. In this paper, the skewness of the join of graphs with paths and cycles is studied. At first, we calculate the skewness of the generalized fans and the n-fold wheels. Then, we prove some results concerning the skewness for the join of graphs with paths and use these results to determine completely the skewness of the join of complete graphs, star graphs and complete bipartite graphs with paths. At the end, some useful formulas are presented for calculating the skewness of vertex corona product and edge corona product of two graphs.

References:

[1] A. Liebers, Planarizing graphs–a survey and annotated bibliography, Journal of Graph Algorithms and Applications, 5: 1-17 (2001).

[2] P. C. Liu, R. C. Geldmacher, On the deletion of nonplanar edges of a graph, Congressus Numerantium, 24: 727–738 (1979).

[3] M. Yannakakis, Edge-deletion problems, SIAM Journal on Computing, 10: 297–309 (1981).

[4] G. L. Chia, K. A. Sim, On the skewness of the join of graphs, Discrete Applied Mathematics, 161: 2405–2408 (2013).

[5] G.L. Chia, C.L. Lee, Crossing numbers and skewness of some generalized Petersen graphs, in: Lecture Notes in Computer Science, Vol. 3330, Springer-Verlag, 80–86 (2005).

[6] G.L. Chia, C.L. Lee, Skewness of some generalized Petersen graphs and related graphs, Frontiers of Mathematics in China, 7: 427–436 (2012).

[7] G.L. Chia, C.L. Lee, Skewness and crossing numbers of graphs, Bulletin of the Institute of Combinatorics and its Applications, 55: 17–32 (2009).

[8] R.J. Cimikowski, Graph planarization and skewness, Congressus Numerantium, 88: 21–32 (1992).

[9] Z.D. Ouyang, F.M. Dong, R.X. Zhang, E.G. Tay, Properties of -skew Graphs with Applications, Acta Mathematica Sinica, English Series, 37: 641–656 (2021).