تسجيل الدخول

تسجيل

Graph Skewness

المؤلف:  Chia, G. L. and Sim, K. A

المصدر:  "On the Skewness of the Join of Graphs." Disc. Appl. Math. 161

الجزء والصفحة:  ...

24-4-2022

2196

Graph Skewness

The skewness of a graph  is the minimum number of edges whose removal results in a planar graph (Harary 1994, p. 124). The skewness is sometimes denoted  (Cimikowski 1992).

A graph  with  has toroidal crossing number . (However, there exist graphs with  that still have .)

 satisfies

(1)

where  is the vertex count of  and  its edge count (Cimikowski 1992).

The skewness of a disconnected graph is equal to the sum of skewnesses of its connected components.

The skewness of a complete graph  is given by

{0 for n<=4; 1/2(n-3)(n-4) otherwise, " src="https://mathworld.wolfram.com/images/equations/GraphSkewness/NumberedEquation2.svg" style="height:57px; width:245px" />

(2)

of the complete bipartite graph  by

(3)

and of the hypercube graph  by

{0 for n<=3; 2^n(n-2)-n·2^(n-1)+4 otherwise " src="https://mathworld.wolfram.com/images/equations/GraphSkewness/NumberedEquation4.svg" style="height:53px; width:278px" />

(4)

(Cimikowski 1992).

---

REFERENCES

Chia, G. L. and Sim, K. A. "On the Skewness of the Join of Graphs." Disc. Appl. Math. 161, 2405-2409, 2013.

Cimikowski, R. J. "Graph Planarization and Skewness. In Proceedings of the Twenty-third Southeastern International Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1992). Congr. Numer., 88, 21-32, 1992.

Harary, F. Problem 11.24 in Graph Theory. Reading, MA: Addison-Wesley, p. 124, 1994.