Exact distance graphs of product graphs

DOI10.1007/S00373-019-02089-0MaRDI QIDQ2287747zbMATH OpenOpenAlexFDO

Authors Boštjan Brešar, Nicolas Gastineau, Sandi Klavžar, Olivier Togni

Publication date 21 January 2020

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1810.10198

zbMATH Keywords

connectivityexact distance graphgeneralized Johnson graphgeneralized Kneser graphgraph producthypercube

Mathematics Subject Classification ID

Distance in graphs (05C12) Coloring of graphs and hypergraphs (05C15) Graph operations (line graphs, products, etc.) (05C76)

Abstract: Given a graph $G$, the exact distance-$p$ graph $G^{[aturalp]}$ has $V(G)$ as its vertex set, and two vertices are adjacent whenever the distance between them in $G$ equals $p$. We present formulas describing the structure of exact distance-$p$ graphs of the Cartesian, the strong, and the lexicographic product. We prove such formulas for the exact distance-$2$ graphs of direct products of graphs. We also consider infinite grids and some other product structures. We characterize the products of graphs of which exact distance graphs are connected. The exact distance-$p$ graphs of hypercubes $Q_n$ are also studied. As these graphs contain generalized Johnson graphs as induced subgraphs, we use some known and find some new constructions of their colorings. These constructions are applied for colorings of the exact distance-$p$ graphs of hypercubes with the focus on the chromatic number of $Q_n^{[aturalp]}$ for $pinn-2,n-3,n-4$.

Recommendations

• Chromatic numbers of exact distance graphs
• Exact square coloring of graphs resulting from some graph operations and products
• DEGREE DISTANCE OF PRODUCT GRAPHS
• 2-distance coloring of strong product of graphs
• On the distance chromatic number of Hamming graphs

Cites work

• A combinatorical proof of Kneser's conjecture
• A short proof of Kneser's conjecture
• Chromatic numbers of exact distance graphs
• Coloring general Kneser graphs and hypergraphs via high-discrepancy hypergraphs
• Exact distance colouring in trees
• Handbook of product graphs
• scientific article; zbMATH DE number 3834025 (Why is no real title available?)
• scientific article; zbMATH DE number 3515509 (Why is no real title available?)
• scientific article; zbMATH DE number 1775058 (Why is no real title available?)
• scientific article; zbMATH DE number 821271 (Why is no real title available?)
• scientific article; zbMATH DE number 4185639 (Why is no real title available?)
• Kneser's conjecture, chromatic number, and homotopy
• Matroidal bijections between graphs
• Near-optimal conflict-free channel set assignments for an optical cluster-based hypercube network
• New results on two hypercube coloring problems
• On chromatic number of general Kneser graphs
• On chromatic numbers of close-to-Kneser distance graphs
• On low tree-depth decompositions
• On the chromatic number of cube-like graphs
• On the girth and diameter of generalized Johnson graphs
• Self 2-distance graphs
• Sparsity. Graphs, structures, and algorithms
• The Kronecker Product of Graphs

Cited in

(9)

• Approximate graph products
• Addressing graph products and distance-regular graphs
• Exact square coloring of subcubic planar graphs
• Injective coloring of graphs revisited
• DEGREE DISTANCE OF PRODUCT GRAPHS
• Distance formula for direct-co-direct product in the case of disconnected factors
• Exact square coloring of graphs resulting from some graph operations and products
• The clique number of the exact distance t-power graph: complexity and eigenvalue bounds
• Products of unit distance graphs

This page was built for publication: Exact distance graphs of product graphs

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