A characterization of line graphs that are squares of graphs

DOI10.1016/j.dam.2014.03.021zbMath1298.05279OpenAlexW2156723548MaRDI QIDQ400504

Andrea Oversberg, Oliver Schaudt, Martin Milanič

Publication date: 22 August 2014

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

Full work available at URL: https://doi.org/10.1016/j.dam.2014.03.021

zbMATH Keywords

line graphlinear time algorithmthe square of a graph

Mathematics Subject Classification ID

Distance in graphs (05C12) Graph algorithms (graph-theoretic aspects) (05C85) Graph operations (line graphs, products, etc.) (05C76)

Related Items

A linear kernel for finding square roots of almost planar graphs, Computing square roots of graphs with low maximum degree, Squares of low clique number, 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, Graph square roots of small distance from degree one graphs, Finding Cactus Roots in Polynomial Time

Cites Work

• Powers of cycles, powers of paths, and distance graphs
• The square of a block graph
• Distance-hereditary graphs
• Dominating cliques in \(P_ 5\)-free graphs
• On metric properties of certain clique graphs
• Computing roots of graphs is hard
• A good characterization of squares of strongly chordal split graphs
• A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
• Complexity of finding graph roots with girth conditions
• Computing square roots of trivially perfect and threshold graphs
• Graphs of diameter 3 with the minimum number of edges
• Bipartite roots of graphs
• Large-Girth Roots of Graphs
• Graph Classes: A Survey
• Recognizing Powers of Proper Interval, Split, and Chordal Graphs
• Algorithms for Square Roots of Graphs
• Structure and linear-time recognition of 4-leaf powers
• Characterizations of derived graphs
• Hardness Results and Efficient Algorithms for Graph Powers