Pancyclicity and NP-completeness in planar graphs (Q1962068): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(5 intermediate revisions by 4 users not shown) | |||
Property / author | |||
Property / author: Q591118 / rank | |||
Property / author | |||
Property / author: Q791541 / rank | |||
Property / author | |||
Property / author: Ming-Chu Li / rank | |||
Normal rank | |||
Property / author | |||
Property / author: Derek Gordon Corneil / rank | |||
Normal rank | |||
Property / Wikidata QID | |||
Property / Wikidata QID: Q56235005 / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4198056 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The Planar Hamiltonian Circuit Problem is NP-Complete / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Pairs of edge-disjoint Hamiltonian circuits / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Revision as of 12:30, 29 May 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