Bounding the search number of graph products

DOI10.5666/KMJ.2019.59.1.175MaRDI QIDQ5215862zbMATH OpenFDO

Authors Nancy E. Clarke, Margaret-Ellen Messinger, Grace Power

Publication date 13 February 2020

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

zbMATH Keywords

pathwidthgraph searchingsweeping

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph operations (line graphs, products, etc.) (05C76)

Abstract: In this paper, we provide results for the search number of the Cartesian product of graphs. We consider graphs on opposing ends of the spectrum: paths and cliques. Our main result determines the pathwidth of the product of cliques and provides a lower bound for the search number of the product of cliques. A consequence of this result is a bound for the search number of arbitrary graphs G and H based on their respective clique numbers.

Recommendations

• scientific article; zbMATH DE number 4037592
• Lower bounds for treewidth of product graphs
• The fast search number of a Cartesian product of graphs
• Fast searching on Cartesian products of graphs
• On dominating the Cartesian product of a graph and K₂

Cites work

• scientific article; zbMATH DE number 4037592 (Why is no real title available?)
• scientific article; zbMATH DE number 4060712 (Why is no real title available?)
• scientific article; zbMATH DE number 4121438 (Why is no real title available?)
• A partial k-arboretum of graphs with bounded treewidth
• Achievable sets, brambles, and sparse treewidth obstructions
• Cleaning a network with brushes
• Eavesdropping games
• Edge Search Number of Cographs in Linear Time
• Graph minors. I. Excluding a forest
• Graph minors. II. Algorithmic aspects of tree-width
• Graph searching and a min-max theorem for tree-width
• Lower bounds on the pathwidth of some grid-like graphs
• On search, decision, and the efficiency of polynomial-time algorithms
• Searching and pebbling
• Searching and sweeping graphs: a brief survey
• The Pathwidth and Treewidth of Cographs
• The complexity of searching a graph
• The vertex separation and search number of a graph
• The vertex separation number of a graph equals its path-width

Cited in

(4)

• Lower bounds for treewidth of product graphs
• scientific article; zbMATH DE number 4037592 (Why is no real title available?)
• Approximate graph products
• On the gonality of Cartesian products of graphs

This page was built for publication: Bounding the search number of graph products

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