The square of a block graph

DOI10.1016/j.disc.2009.09.004zbMath1214.05145OpenAlexW1988461769MaRDI QIDQ965949

Van Bang Le, Nguyen Ngoc Tuy

Publication date: 27 April 2010

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disc.2009.09.004

zbMATH Keywords

graph algorithmsgraph powersgood characterizationssquares of block graphstree squares

Mathematics Subject Classification ID

Graph operations (line graphs, products, etc.) (05C76)

Related Items (15)

Edge ideals of squares of trees ⋮ 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 ⋮ Extremes of Markov random fields on block graphs: max-stable limits and structured Hüsler-Reiss distributions ⋮ Computing square roots of trivially perfect and threshold graphs ⋮ Polynomial time recognition of squares of Ptolemaic graphs and 3-sun-free split graphs ⋮ 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 ⋮ Induced Embeddings into Hamming Graphs. ⋮ Parameterized leaf power recognition via embedding into graph products ⋮ Parameterized algorithms for finding square roots

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A linear time algorithm to list the minimal separators of chordal graphs
• Minimal vertex separators of chordal graphs
• Computing roots of graphs is hard
• Efficient graph representations
• Interval numbers of powers of block graphs
• Bipartite roots of graphs
• Tree Powers
• Recognizing Powers of Proper Interval, Split, and Chordal Graphs
• Algorithms for Square Roots of Graphs
• Structure and linear-time recognition of 4-leaf powers
• Simplicial Powers of Graphs
• The square root of a graph
• The Two-Triangle Case of the Acquaintance Graph
• Depth-First Search and Linear Graph Algorithms
• Linear-Time Algorithms for Tree Root Problems

This page was built for publication: The square of a block graph