Recognizing Powers of Proper Interval, Split, and Chordal Graphs

DOI10.1137/S0895480103425930zbMath1071.05031OpenAlexW1987143101MaRDI QIDQ4652622

Lap Chi Lau, Derek Gordon Corneil

Publication date: 28 February 2005

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

Full work available at URL: https://doi.org/10.1137/s0895480103425930

zbMATH Keywords

graph algorithmsgraph powersgraph roots

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75) Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (26)

A linear-time algorithm for finding a one-to-many 3-disjoint path cover in the cube of a connected graph ⋮ 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 ⋮ Maximizing the strong triadic closure in split graphs and proper interval graphs ⋮ Complexity of finding graph roots with girth conditions ⋮ A good characterization of squares of strongly chordal split graphs ⋮ On the relation between the positive inertia index and negative inertia index of weighted graphs ⋮ Computing square roots of trivially perfect and threshold graphs ⋮ Polynomial time recognition of squares of Ptolemaic graphs and 3-sun-free split graphs ⋮ On the two largest distance eigenvalues of graph powers ⋮ Squares of low clique number ⋮ The square of a block graph ⋮ Finding cut-vertices in the square roots of a graph ⋮ On the least distance eigenvalues of the second power of a graph ⋮ Finding cactus roots in polynomial time ⋮ Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2 ⋮ A linear-time algorithm for finding a paired 2-disjoint path cover in the cube of a connected graph ⋮ Closest 4-leaf power is fixed-parameter tractable ⋮ Graph square roots of small distance from degree one graphs ⋮ Hardness and structural results for half-squares of restricted tree convex bipartite graphs ⋮ Finding Cactus Roots in Polynomial Time ⋮ Unnamed Item ⋮ Linear-time algorithms for tree root problems ⋮ Parameterized algorithms for finding square roots

This page was built for publication: Recognizing Powers of Proper Interval, Split, and Chordal Graphs