The Neighborhood Polynomial of Chordal Graphs

DOI10.46298/DMTCS.8388MaRDI QIDQ6045410zbMATH OpenFDO

Authors Helena Bergold, Winfried. Hochstättler, Uwe F. Mayer

Publication date 30 May 2023

Published in Discrete Mathematics & Theoretical Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.46298/DMTCS.8388

zbMATH Keywords

anchor widthchordal graphcomparability graphdomination polynomialleafageneighborhood polynomial

Mathematics Subject Classification ID

Graph polynomials (05C31) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• The neighborhood polynomial of chordal graphs
• Polynomial-Time Algorithm for the Leafage of Chordal Graphs
• The leafage of a chordal graph
• On k-trees with given leafages
• Testing isomorphism of chordal graphs of bounded leafage is fixed-parameter tractable (extended abstract)
• k-separator chordal graphs: leafage and subfamilies
• The vertex leafage of chordal graphs
• Determining possible sets of leaves for spanning trees of dually chordal graphs.
• On the chordality of a graph
• scientific article; zbMATH DE number 512817

Cites work

• A Linear Recognition Algorithm for Cographs
• A Linear Time Algorithm for Deciding Interval Graph Isomorphism
• Dominating sets for split and bipartite graphs
• Dominating Sets in Chordal Graphs
• Graph operations and neighborhood polynomials
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• Kneser's conjecture, chromatic number, and homotopy
• Neighborhood and domination polynomials of graphs
• Polynomial-Time Algorithm for the Leafage of Chordal Graphs
• Representing triangulated graphs in stars
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• The leafage of a chordal graph
• The neighbourhood polynomial of a graph

Cited in

(2)

• Neighborhood and domination polynomials of graphs
• Chordal graphs and the characteristic polynomial

This page was built for publication: The Neighborhood Polynomial of Chordal Graphs

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