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.

اخر الاخبار

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

سماحة السيد الصافي يكرم عددًا من عوائل الشهداء ضمن فعاليات مهرجان روح النبوة النسوي العالمي الثامن

إحدى أمهات الشهداء: نعتز بتضحيات أبنائنا ونفتخر بشهادتهم دفاعًا عن الدين والمقدسات

ضمن فعاليات مهرجان روح النبوة… عرض فيلم يوثق نشاطات الشعب النسوية في العتبة العباسية المقدسة

فعاليات مهرجان روح النبوة الثقافي تشهد تقديم أوبريت الثقلين القرآني

المزيد

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

ماذا يحدث لجسمك عند تناول الوجبات السريعة يوميا؟

لصحة عظام المرأة.. الشاي أفضل أم القهوة؟

لبناء العضلات وإنقاص الوزن.. ما أفضل توقيت لتناول البيض؟

أطعمة صحية تساعد على التعافي من "الإنفلونزا الخارقة"

المزيد

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

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

تجربة جديدة: الأسفلت المدعوم بالطحالب يقاوم الحفر ويقلل الانبعاثات الكربونية

تسريبات تكشف ملامح أول هاتف قابل للطي من "أبل"

رصد نوع نادر من القطط في تايلاند للمرة الأولى منذ عقود

المزيد

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

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