التفاصيل البيبلوغرافية
| العنوان: |
On the k-dominating set polytope of web graphs. |
| المؤلفون: |
Argiroffo, Gabriela R., Ugarte, Maria E., Escalante, Mariana S. |
| المصدر: |
Electronic Notes in Discrete Mathematics; Aug2010, Vol. 36, p1161-1168, 8p |
| مصطلحات موضوعية: |
DOMINATING set, POLYTOPES, GRAPH theory, POLYHEDRA, CONVEX sets, MATHEMATICAL inequalities, PATHS & cycles in graph theory |
| مستخلص: |
Abstract: In this work we present some results on the polyhedral structure of the convex hull of integer points in polyhedra of the form , for a 0, 1 matrix M and a positive integer number k. In particular, we consider the k-dominating set problem in a graph. Given a graph , a set is a k-dominating set if every vertex in V is adjacent to at least k vertices of D. The k-dominating set problem consists in finding a k-dominating set of minimum cardinality. The k-dominating set polytope is the convex hull of the incidence vectors of k-dominating sets in G and it is a natural generalization of the well-known dominating set polytope of a graph. We apply our results for general problems to the k-dominating set polytope of some particular families of web graphs. [ABSTRACT FROM AUTHOR] |
|
Copyright of Electronic Notes in Discrete Mathematics is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.) |
| قاعدة البيانات: |
Supplemental Index |