Minimum Edge Cover
المؤلف:
Gallai, T
المصدر:
"Über extreme Punkt- und Kantenmengen." Ann. Univ. Sci. Budapest, Eőtvős Sect. Math. 2
الجزء والصفحة:
...
26-4-2022
1892
Minimum Edge Cover
A minimum edge cover is an edge cover having the smallest possible number of edges for a given graph. The size of a minimum edge cover of a graph is known as the edge cover number of 
and is denoted 
.
Every minimum edge cover is a minimal edge cover (i.e., not a proper subset of any other edge cover), but not necessarily vice versa.
Only graphs with no isolated points have an edge cover (and therefore a minimum edge cover).
A minimum edge cover of a graph can be computed in the Wolfram Language with FindEdgeCover[g]. There is currently no Wolfram Language function to compute all minimum edge covers of a graph.
If a graph 
has no isolated points, then
where 
is the matching number and 
is the vertex count of 
(Gallai 1959, West 2000).
REFERENCES
Gallai, T. "Über extreme Punkt- und Kantenmengen." Ann. Univ. Sci. Budapest, Eőtvős Sect. Math. 2, 133-138, 1959.
Pemmaraju, S. and Skiena, S. Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Cambridge, England: Cambridge University Press, p. 318, 2003.
Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 178, 1990.
West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 2000.
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
