Price of connectivity for the vertex cover problem and the dominating set problem: conjectures and investigation of critical graphs

DOI10.1007/s00373-018-1981-xzbMath1409.05156OpenAlexW2619504389WikidataQ123334753 ScholiaQ123334753MaRDI QIDQ1733857

Eglantine Camby

Publication date: 21 March 2019

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00373-018-1981-x

zbMATH Keywords

dominating setvertex coverextremal graphconnected dominating setforbidden induced subgraphconnected vertex cover

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Connectivity (05C40) Software, source code, etc. for problems pertaining to combinatorics (05-04)

Related Items (3)

Minimum connected transversals in graphs: new hardness results and tractable cases using the price of connectivity ⋮ On the price of independence for vertex cover, feedback vertex set and odd cycle transversal ⋮ On cycle transversals and their connected variants in the absence of a small linear forest

Uses Software

• GraphsInGraphs

Cites Work

• Unnamed Item
• The price of connectivity for dominating set: upper bounds and complexity
• On graphs for which the connected domination number is at most the total domination number
• The price of connectivity for feedback vertex set
• A note on an induced subgraph characterization of domination perfect graphs
• The price of connectivity for cycle transversals
• Connected vertex covers in dense graphs
• Forbidden Induced Subgraphs and the Price of Connectivity for Feedback Vertex Set
• Hereditary Domination in Graphs: Characterization with Forbidden Induced Subgraphs
• On Hadwiger's Number and the Stability Number
• A characterization of domination perfect graphs
• A semi-induced subgraph characterization of upper domination perfect graphs
• Perfect connected-dominant graphs
• A note on the characterization of domination perfect graphs
• An induced subgraph characterization of domination perfect graphs
• The Price of Connectivity for Vertex Cover

This page was built for publication: Price of connectivity for the vertex cover problem and the dominating set problem: conjectures and investigation of critical graphs