The thickness of a graph G is the minimum number of planar subgraphs whose union is G. A t-minimal graph is a graph of thickness t which contains no proper subgraph of thickness t. Tutte showed that each t- minimal graph (t\(\geq 2)\) is 2-connected with minimum degree at least t. Hobbs and Grossman showed that each t-minimal graph is t-edge-connected. The authors show, by constructive means, that there exist infinitely many t-minimal graphs having minimum degree t (and thus edge-connectivity t) and whose connectivity is 2.
Recommendations
Cites work
- A class of thickness-minimal graphs
- scientific article; zbMATH DE number 3309921 (Why is no real title available?)
- scientific article; zbMATH DE number 3329635 (Why is no real title available?)
- scientific article; zbMATH DE number 3199421 (Why is no real title available?)
- Note on T-Minimal Complete Bipartite Graphs
- Parallel concepts in graph theory
- Thickness and connectivity in graphs
Cited in
(5)- Representations of graphs and networks (coding, layouts and embeddings)
- The thickness of a minor-excluded class of graphs
- Maximizing the degree of (geometric) thickness-t regular graphs
- Thickness‐two graphs part one: New nine‐critical graphs, permuted layer graphs, and Catlin's graphs
- A class of thickness-minimal graphs
This page was built for publication: A construction of thickness-minimal graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1820166)
