A good characterization of squares of strongly chordal split graphs

DOI10.1016/j.ipl.2010.11.003zbMath1259.05168OpenAlexW1994156213MaRDI QIDQ1944051

Van Bang Le, Ngoc Tuy Nguyen

Publication date: 4 April 2013

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2010.11.003

zbMATH Keywords

graph algorithmsgraph powersgood characterizationssquares of split graphsstrongly chordal split graphs

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (14)

Edge ideals of squares of trees ⋮ A unified approach to recognize squares of split graphs ⋮ A linear kernel for finding square roots of almost planar graphs ⋮ Computing square roots of graphs with low maximum degree ⋮ A characterization of line graphs that are squares of graphs ⋮ Computing square roots of trivially perfect and threshold graphs ⋮ Polynomial time recognition of squares of Ptolemaic graphs and 3-sun-free split graphs ⋮ Squares of low clique number ⋮ Finding cut-vertices in the square roots of a graph ⋮ Finding cactus roots in polynomial time ⋮ Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2 ⋮ Graph square roots of small distance from degree one graphs ⋮ Finding Cactus Roots in Polynomial Time ⋮ Parameterized algorithms for finding square roots

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Characterizations of strongly chordal graphs
• Computing roots of graphs is hard
• Efficient graph representations
• Doubly Lexical Orderings of Matrices
• Three Partition Refinement Algorithms
• Recognizing Powers of Proper Interval, Split, and Chordal Graphs
• The square root of a graph

This page was built for publication: A good characterization of squares of strongly chordal split graphs