Thinness of product graphs
| Autor: | Flavia Bonomo-Braberman, Fabiano de S. Oliveira, Moysés S. Sampaio, Carolina Gonzalez, Jayme Luiz Szwarcfiter |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2020 |
| Předmět: |
FOS: Computer and information sciences
Discrete Mathematics (cs.DM) genetic structures Quantitative Biology::Tissues and Organs 0211 other engineering and technologies 0102 computer and information sciences 02 engineering and technology G.2.2 01 natural sciences Physics::Fluid Dynamics FOS: Mathematics Discrete Mathematics and Combinatorics Mathematics - Combinatorics natural sciences Representation (mathematics) Time complexity Mathematics Discrete mathematics Applied Mathematics 021107 urban & regional planning Function (mathematics) Graph eye diseases Condensed Matter::Soft Condensed Matter 010201 computation theory & mathematics Bounded function Product (mathematics) Interval (graph theory) Combinatorics (math.CO) sense organs Computer Science - Discrete Mathematics 05C76 |
| Popis: | The thinness of a graph is a width parameter that generalizes some properties of interval graphs, which are exactly the graphs of thinness one. Many NP-complete problems can be solved in polynomial time for graphs with bounded thinness, given a suitable representation of the graph. In this paper we study the thinness and its variations of graph products. We show that the thinness behaves "well" in general for products, in the sense that for most of the graph products defined in the literature, the thinness of the product of two graphs is bounded by a function (typically product or sum) of their thinness, or of the thinness of one of them and the size of the other. We also show for some cases the non-existence of such a function. 45 pages. arXiv admin note: text overlap with arXiv:1704.00379 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|