Characterizing and recognizing probe block graphs

DOI10.1016/J.TCS.2014.12.014MaRDI QIDQ2513611zbMATH OpenOpenAlexFDO

Authors Van Bang Le, Sheng-Lung Peng

Publication date 28 January 2015

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2014.12.014

zbMATH Keywords

block graphgraph modificationprobe block graphprobe graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph designs and isomorphic decomposition (05C51)

Recommendations

• Good characterizations and linear time recognition for 2-probe block graphs
• scientific article; zbMATH DE number 6432456
• Probe Ptolemaic Graphs
• Two characterizations of chain partitioned probe graphs
• Probe split graphs

Cites work

• scientific article; zbMATH DE number 3632548 (Why is no real title available?)
• Algorithmic graph theory and perfect graphs
• Block-graph width
• Chordal probe graphs
• Graph Classes: A Survey
• Graph Sandwich Problems
• On probe permutation graphs
• On the bi-enhancement of chordal-bipartite probe graphs
• On the complexity of DNA physical mapping
• Probe threshold and probe trivially perfect graphs
• Two characterizations of chain partitioned probe graphs

Cited in

(7)

• Characterizing block graphs in terms of their vertex-induced partitions
• An observation on block graphs
• A characterization of block graphs
• A note proving the nullity of block graphs is unbounded
• The \((k, \ell)\) partitioned probe problem: NP-complete versus polynomial dichotomy
• Good characterizations and linear time recognition for 2-probe block graphs
• Betti numbers of edge ideals of some split graphs

This page was built for publication: Characterizing and recognizing probe block graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2513611)