A characterization of line graphs that are squares of graphs

DOI10.1016/J.DAM.2014.03.021MaRDI QIDQ400504zbMATH OpenOpenAlexFDO

Authors Martin Milanič, Andrea Oversberg, Oliver Schaudt

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

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

Recommendations

• The square of a block graph
• scientific article; zbMATH DE number 6027233
• Complexity of finding graph roots with girth conditions
• A good characterization of squares of strongly chordal split graphs
• A unified approach to recognize squares of split graphs

Cites work

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

Cited in

(13)

• Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2
• scientific article; zbMATH DE number 637320 (Why is no real title available?)
• On perfect linegraph squares
• Finding cactus roots in polynomial time
• A linear kernel for finding square roots of almost planar graphs
• A linear-time algorithm for finding a paired 2-disjoint path cover in the cube of a connected graph
• Finding cactus roots in polynomial time
• Computing square roots of graphs with low maximum degree
• A linear time algorithm to compute square of interval graphs and their colouring
• On chordal graph and line graph squares
• Squares of low clique number
• Graph square roots of small distance from degree one graphs
• The square of a block graph

This page was built for publication: A characterization of line graphs that are squares of graphs

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