Bounding the search number of graph products

DOI10.5666/KMJ.2019.59.1.175zbMATH Open1432.05087arXiv1604.04509MaRDI QIDQ5215862FDOQ5215862

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

Publication date: 13 February 2020

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.

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

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₂

zbMATH Keywords

pathwidthgraph searchingsweeping

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (4)

• On the gonality of Cartesian products of graphs
• Approximate graph products
• Lower bounds for treewidth of product graphs
• Title not available (Why is that?)

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)