Characterizing and recognizing exact-distance squares of graphs

DOI10.1016/J.DISC.2023.113493MaRDI QIDQ6416211zbMATH OpenOpenAlexFDO

Authors Yandong Bai, Pedro P. Cortés, Reza Naserasr, Daniel A. Quiroz

Publication date 4 November 2022

Full work available at URL https://doi.org/10.1016/j.disc.2023.113493

Mathematics Subject Classification ID

Trees (05C05) Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: For a graph $G=(V,E)$, its exact-distance square, $G^{[sharp2]}$, is the graph with vertex set $V$ and with an edge between vertices $x$ and $y$ if and only if $x$ and $y$ have distance (exactly) $2$ in $G$. The graph $G$ is an exact-distance square root of $G^{[sharp2]}$. We give a characterization of graphs having an exact-distance square root, our characterization easily leading to a polynomial-time recognition algorithm. We show that it is NP-complete to recognize graphs with a bipartite exact-distance square root. These two results strongly contrast known results on (usual) graph squares. We then characterize graphs having a tree as an exact-distance square root, and from this obtain a polynomial-time recognition algorithm for these graphs. Finally, we show that, unlike for usual square roots, a graph might have (arbitrarily many) non-isomorphic exact-distance square roots which are trees.

Recommendations

• scientific article; zbMATH DE number 6469239
• Bipartite roots of graphs
• scientific article; zbMATH DE number 6027233
• Complexity of finding graph roots with girth conditions
• A unified approach to recognize squares of split graphs

Cited in

(1)

• Exact square coloring of certain classes of graphs: complexity and algorithms

This page was built for publication: Characterizing and recognizing exact-distance squares of graphs

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