Connection between conjunctive capacity and structural properties of graphs

Miroslav Chlebik; Janka Chlebikova

doi:10.1016/j.tcs.2014.04.035

Connection between conjunctive capacity and structural properties of graphs

Miroslav Chlebik, Janka Chlebikova

School of Computing

University of Sussex

Research output: Contribution to journal › Article › peer-review

127 Downloads (Pure)

Abstract

The investigation of the asymptotic behaviour of various graph parameters in powers of a graph 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örner and Vaccaro. To determine C_AND(G) is a convex programming problem. We show that the optimal solution to this problem is unique and describe the structure of the solution in any (simple) graph. We prove 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.

Original language	English
Pages (from-to)	109-118
Journal	Theoretical Computer Science
Volume	554
Early online date	10 May 2014
DOIs	https://doi.org/10.1016/j.tcs.2014.04.035
Publication status	Published - 16 Oct 2014

Keywords

Graph capacities
compound channel
Shannon capacity for graph families
fractional vertex cover
binding number
strong crown decomposition

Access to Document

10.1016/j.tcs.2014.04.035

capacity-tcs
“NOTICE: this is the author’s version of a work that was accepted for publication in 'Theoretical computer science'. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in 'Theoretical computer science', [554, 16/10/2014] DOI: 10.1016/j.tcs.2014.04.035"
Accepted author manuscript (Post-print), 317 KB

Cite this

@article{0998a92ffc0348238ab88cae8fc0cf27,

title = "Connection between conjunctive capacity and structural properties of graphs",

abstract = "The investigation of the asymptotic behaviour of various graph parameters in powers of a graph 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, CAND(G), introduced and studied by Gargano, K{\"o}rner and Vaccaro. To determine CAND(G) is a convex programming problem. We show that the optimal solution to this problem is unique and describe the structure of the solution in any (simple) graph. We prove that its reciprocal value vcC(G):=1/CAND(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.",

keywords = "Graph capacities, compound channel, Shannon capacity for graph families, fractional vertex cover, binding number, strong crown decomposition",

author = "Miroslav Chlebik and Janka Chlebikova",

note = "“NOTICE: this is the author{\textquoteright}s version of a work that was accepted for publication in 'Theoretical computer science'. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in 'Theoretical computer science', [554, 16/10/2014] DOI: 10.1016/j.tcs.2014.04.035{"}",

year = "2014",

month = oct,

day = "16",

doi = "10.1016/j.tcs.2014.04.035",

language = "English",

volume = "554",

pages = "109--118",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

}

TY - JOUR

T1 - Connection between conjunctive capacity and structural properties of graphs

AU - Chlebik, Miroslav

AU - Chlebikova, Janka

N1 - “NOTICE: this is the author’s version of a work that was accepted for publication in 'Theoretical computer science'. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in 'Theoretical computer science', [554, 16/10/2014] DOI: 10.1016/j.tcs.2014.04.035"

PY - 2014/10/16

Y1 - 2014/10/16

N2 - The investigation of the asymptotic behaviour of various graph parameters in powers of a graph 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, CAND(G), introduced and studied by Gargano, Körner and Vaccaro. To determine CAND(G) is a convex programming problem. We show that the optimal solution to this problem is unique and describe the structure of the solution in any (simple) graph. We prove that its reciprocal value vcC(G):=1/CAND(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 graph 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, CAND(G), introduced and studied by Gargano, Körner and Vaccaro. To determine CAND(G) is a convex programming problem. We show that the optimal solution to this problem is unique and describe the structure of the solution in any (simple) graph. We prove that its reciprocal value vcC(G):=1/CAND(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.

KW - Graph capacities

KW - compound channel

KW - Shannon capacity for graph families

KW - fractional vertex cover

KW - binding number

KW - strong crown decomposition

U2 - 10.1016/j.tcs.2014.04.035

DO - 10.1016/j.tcs.2014.04.035

M3 - Article

SN - 0304-3975

VL - 554

SP - 109

EP - 118

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -

Connection between conjunctive capacity and structural properties of graphs

Abstract

Keywords

Access to Document

Fingerprint

Cite this