TY - GEN

T1 - On the conjunctive capacity of graphs

AU - Chlebik, M.

AU - Chlebikova, Janka

PY - 2013

Y1 - 2013

N2 - The investigation of the asymptotic behaviour of various graph parameters in powers of a fixed graph G=(V,E) is motivated by problems in information theory and extremal combinatorics. Considering various parameters and/or various notions of graph powers we can arrive at different notions of graph capacities, of which the Shannon capacity is best known.
Here we study a related notion of the so-called conjunctive capacity of a graph G, C_AND(G), introduced and studied by Gargano, K\"orner and Vaccaro. To determine C_AND(G) is a convex programming problem. In this paper we show that the optimal solution to this problem is unique and describe the structure of the solution in any (simple) graph. We show that its reciprocal value vc_C(G):=1/C_AND(G is an optimal solution of the newly introduced problem of Minimum Capacitary Vertex Cover that is closely related to the LP-relaxation of the Minimum Vertex Cover Problem. We also describe its close connection with the binding number/binding set of a graph, and with the strong crown decomposition of graphs.

AB - The investigation of the asymptotic behaviour of various graph parameters in powers of a fixed graph G=(V,E) is motivated by problems in information theory and extremal combinatorics. Considering various parameters and/or various notions of graph powers we can arrive at different notions of graph capacities, of which the Shannon capacity is best known.
Here we study a related notion of the so-called conjunctive capacity of a graph G, C_AND(G), introduced and studied by Gargano, K\"orner and Vaccaro. To determine C_AND(G) is a convex programming problem. In this paper we show that the optimal solution to this problem is unique and describe the structure of the solution in any (simple) graph. We show that its reciprocal value vc_C(G):=1/C_AND(G is an optimal solution of the newly introduced problem of Minimum Capacitary Vertex Cover that is closely related to the LP-relaxation of the Minimum Vertex Cover Problem. We also describe its close connection with the binding number/binding set of a graph, and with the strong crown decomposition of graphs.

U2 - 10.1007/978-3-642-38768-5_26

DO - 10.1007/978-3-642-38768-5_26

M3 - Conference contribution

SN - 9783642387678

VL - 7936

T3 - Lecture notes in computer science

SP - 280

EP - 291

BT - Computing and combinatorics: 19th International Conference, COCOON 2013, Hangzhou, China, June 21-23, 2013, proceedings

A2 - Du, D-Z.

A2 - Zhang, G.

PB - Springer

CY - Berlin

ER -