The scattering number of strictly chordal graphs: linear time determination

DOI10.1007/S00373-022-02498-8MaRDI QIDQ2144221zbMATH OpenOpenAlexFDO

Authors Lilian Markenzon, Christina F. E. M. Waga

Publication date 1 June 2022

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

Full work available at URL https://doi.org/10.1007/s00373-022-02498-8

zbMATH Keywords

toughnessscattering numberminimal vertex separatorstrictly chordal graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Connectivity (05C40)

Recommendations

• Scattering number in graphs
• A polynomial algorithm for weighted scattering number in interval graphs
• A measure of graph vulnerability: Scattering number
• Scattering number and Cartesian product of graphs
• Scattering number of the product of some special classes of graphs

Cites work

• scientific article; zbMATH DE number 4053662 (Why is no real title available?)
• scientific article; zbMATH DE number 554762 (Why is no real title available?)
• scientific article; zbMATH DE number 861347 (Why is no real title available?)
• scientific article; zbMATH DE number 6117076 (Why is no real title available?)
• scientific article; zbMATH DE number 7075896 (Why is no real title available?)
• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• 1-tough cocomparability graphs are hamiltonian
• A Characterization of Block-Graphs
• A measure of graphs vulnerability: edge scattering number
• A polynomial algorithm for weighted scattering number in interval graphs
• Algorithmic graph theory and perfect graphs
• Algorithms and Computation
• Block duplicate graphs and a hierarchy of chordal graphs
• Characterising \((k,\ell )\)-leaf powers
• Computing the Scattering Number of Graphs
• Core-satellite graphs: clustering, assortativity and spectral properties
• Domination integrity in trees
• Linear-time algorithms for scattering number and Hamilton-connectivity of interval graphs
• Measuring the vulnerability for classes of intersection graphs
• New results on Ptolemaic graphs
• Non-inclusion and other subclasses of chordal graphs
• On a class of posets and the corresponding comparability graphs
• On isolated rupture degree of graphs
• One-phase algorithm for the determination of minimal vertex separators of chordal graphs
• Recognizing tough graphs is NP-hard
• Relationships between scattering number and other vulnerability parameters
• Rupture degree of graphs
• Strictly interval graphs: characterization and linear time recognition
• Structure and linear time recognition of 3-leaf powers
• The binding number of a graph and its Anderson number
• The efficiency of AC graphs
• Topics in algorithmic graph theory
• Tough graphs and Hamiltonian circuits.
• Toughness and Hamiltonicity of strictly chordal graphs
• Toughness in graphs -- a survey

Cited in

(2)

• Linear-Time Algorithms for Scattering Number and Hamilton-Connectivity of Interval Graphs
• A polynomial algorithm for weighted scattering number in interval graphs

This page was built for publication: The scattering number of strictly chordal graphs: linear time determination

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