Pancyclicity and NP-completeness in planar graphs (Q1962068): Difference between revisions
From MaRDI portal
Created a new Item |
Created claim: Wikidata QID (P12): Q56235005, #quickstatements; #temporary_batch_1704714147019 |
||
Property / Wikidata QID | |||
Property / Wikidata QID: Q56235005 / rank | |||
Normal rank |
Revision as of 13:51, 8 January 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Pancyclicity and NP-completeness in planar graphs |
scientific article |
Statements
Pancyclicity and NP-completeness in planar graphs (English)
0 references
29 June 2000
0 references
A graph is called {\(v\)-pancyclic} if it contains a cycle of length \(l\) containing a given vertex \(v\) for \(3\leq l\leq n\), and a graph \(G\) is called vertex pancyclic if \(G\) is \(v\)-pancyclic for all \(v\). The authors show that it is NP-complete to determine whether a 3-connected cubic planar graph is \(v\)-pancyclic for given vertex \(v\), it is NP-complete to determine whether a 3-connected cubic planar graph is pancyclic, and it is NP-complete to determine whether a 3-connected planar graph is vertex pancyclic. They also show that every maximal outplanar graph is vertex pancyclic.
0 references
NP-completeness
0 references
complexity
0 references
vertex pancyclicity
0 references
planar graphs
0 references