A characterization of line graphs that are squares of graphs

DOI10.1016/J.DAM.2014.03.021zbMATH Open1298.05279OpenAlexW2156723548MaRDI QIDQ400504FDOQ400504

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

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

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)

Cites Work

• Graph Classes: A Survey
• 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
• Bipartite roots of graphs
• Recognizing Powers of Proper Interval, Split, and Chordal Graphs
• Algorithms for Square Roots of Graphs
• Characterizations of derived graphs
• The square of a block graph
• Distance-hereditary graphs
• Dominating cliques in \(P_ 5\)-free graphs
• On metric properties of certain clique graphs
• Hardness Results and Efficient Algorithms for Graph Powers
• Structure and linear-time recognition of 4-leaf powers
• Graphs of diameter 3 with the minimum number of edges
• Large-girth roots of graphs
• Powers of cycles, powers of paths, and distance graphs

Cited In (11)

• The square of a block graph
• On perfect linegraph squares
• Finding cactus roots in polynomial time
• Title not available (Why is that?)
• A linear-time algorithm for finding a paired 2-disjoint path cover in the cube of a connected graph
• Algorithms for outerplanar graph roots and graph roots of pathwidth at most 2
• Graph square roots of small distance from degree one graphs
• A linear kernel for finding square roots of almost planar graphs
• Computing square roots of graphs with low maximum degree
• Finding Cactus Roots in Polynomial Time
• Squares of low clique number

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)