The square root of a graph

DOI10.1016/S0021-9800(67)80030-9MaRDI QIDQ5534027zbMATH OpenOpenAlexFDO

Authors

Publication date 1967

Published in Journal of Combinatorial Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0021-9800(67)80030-9

zbMATH Keywords

topology

Cited in

(21)

• A characterization of competition graphs
• The square of a chordal graph
• Computing roots of graphs is hard
• A good characterization of squares of strongly chordal split graphs
• Linear-time algorithms for tree root problems
• A linear kernel for finding square roots of almost planar graphs
• Computing square roots of graphs with low maximum degree
• Complexity of finding graph roots with girth conditions
• Characterization of n-path graphs and of graphs having n-th root
• Parameterized algorithms for finding square roots
• Finding cactus roots in polynomial time
• Partial characterizations of 1-perfectly orientable graphs
• Finding cut-vertices in the square roots of a graph
• Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2
• On balance and consistency preserving 2-path signed graphs
• Quasi-transitive mixed graphs and undirected squares of oriented graphs
• Finding cactus roots in polynomial time
• A linear-time algorithm for finding a paired 2-disjoint path cover in the cube of a connected graph
• New characterization of efficient closed and open dominated graphs
• Applications of edge coverings by cliques
• The square of a block graph

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

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