Path Covering Number

The path covering number (or path-covering number; Slater 1972) of a graph , variously denoted as summarized below, is the minimum number of vertex-disjoint paths that cover the vertices of .

notation	reference
	Boesch et al. (1974)
	Slater (1979)
	DeLa Vina and Waller (2002)
	Goedgebeur et al. (2019)
	Lu and Zhou (2013)

In order for the path covering number to be well-defined (for example, in the case of the claw graph , for which one or two vertices are "left over" after covering with paths of length 2 or 1, respectively), "paths" consisting of a single point must be allowed (Boesch et al. 1974).

A graph therefore has path covering number 1 iff it is traceable (Boesch et al. 1974).

A disconnected graph has a path covering number equal to the sum of the path covering numbers of its connected components.

Boesch (et al. 1974) gives values for a number of parametrized classes of graphs.

Lovasz (1979, p. 55) showed that when  is the independence number,

with equality for only complete graphs (DeLa Vina and Waller 2002).

---

REFERENCES

Boesch, F. T.; Chen, S.; and McHugh, J. A. M. "On Covering the Points of a Graph with Point Disjoint Paths." In Graphs and Combinatorics (Ed. R. A. Bari and F. Harary). Berlin: Springer-Verlag, pp. 201-212, 1974.

DeLa Vina, E. and Waller, B. "Independence, Radius and Path Coverings in Trees." Congr. Numer. 156, 155-169, 2002.

Goedgebeur, J.; Ozeki, K.; van Cleemput, N.; and Wiener, G. "On the Minimum Leaf Number of Cubic Graphs." Disc. Math. 342, 3000-3005, 2019.

Lovasz, L. Combinatorial Problems and Exercises. Academiai Kiado, 1979.Lu, C. and Zhou, Q. "Path Covering Number and -Labeling Number of Graphs." Disc. Appl. Math. 161, 2062-2074, 2013.

Ore, Ø. "Arc Coverings of Graphs." Ann. Mat. Pura Appl. 55, 315-332, 1961.

Slater, P. J. "Path Coverings of the Vertices of a Tree." Disc. Math. 25, 65-74, 1979.

اخر الاخبار

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

قسم الصناعات والحرف الفنية ينفذ أعمالًا تطويرية في جامعة الكفيل

قسم الشؤون الطبية يناقش تحضيراته لحفل التخرج المركزي لطالبات الجامعات العراقية العاشر

مركز الكفيل للإعلان والتسويق يباشر تنفيذ الأعمال الطباعية لحفل تخرج طالبات الجامعات العراقية العاشر

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

المزيد

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

خصوصا مع تقدم السن.. 6 سلوكيات يومية قد تدمّر صحتك

فاكهة خضراء.. علاج طبيعي فعّال للإمساك واضطرابات الهضم

روسيا تبدأ أولى التجارب السريرية للقاح واعد ضد السرطان

كنز غذائي على طبقك.. ماذا تفعل السبانخ بجسمك؟

المزيد

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

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

روسيا تخطط لإقامة محطة نووية في القمر خلال العقد المقبل

كيف قاد إيلون ماسك حملة "غروك" لاختراق عرش الذكاء الاصطناعي

ألتمان: الذكاء الاصطناعي سيتجاوز البشر في 2026 !

المزيد

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

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