The scattering number of strictly chordal graphs: linear time determination

DOI10.1007/S00373-022-02498-8zbMATH Open1490.05254OpenAlexW4281562755MaRDI QIDQ2144221FDOQ2144221

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

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

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)

Cites Work

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

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)