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.

اخر الاخبار

اخبار العتبة العباسية المقدسة

عباس.. طفل فقد والده فوجد في خدمة زائري عاشوراء وطنًا آمنًا

شعبة الخطابة النسوية تواصل إقامة مجالس العزاء في شهر المحرم الحرام

لليوم الخامس.. العتبة العباسية المقدسة تقيم مجلس عزاء في صحن مرقد أبي الفضل العباس (عليه السلام)

قسم الشؤون الفكرية يقيم مجلس عزاء حسيني في العاصمة التنزانية دار السلام

المزيد

الآخبار الصحية

لمن تجاوز الستين.. عليك بشرب 4 أكواب من القهوة يوميا ؟

الحليب مع العسل.. مزيج يمنحك 7 فوائد صحية

لا تبالغ في التنظيف.. قليل من "الاتساخ" قد يحمي عائلتك

دراسة تكشف علاقة خطيرة بين عمر الأم وصحة مولودها

المزيد

الآخبار التكنلوجية

هل هاتفك مراقب؟.. 5 علامات خطيرة تكشف التجسس عليك

دبي تطلق أول رحلة تجريبية للتاكسي الجوي

كيف تساعد الصيانة الوقائية في الحفاظ على كفاءة التكييف في سيارتك ؟

في ظاهرة غريبة حيرت العلماء.. كوكبنا قد يسجل أقصر يوم في التاريخ هذا الصيف!

المزيد

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength