Singlecross Graph
المؤلف:
Sloane, N. J. A
المصدر:
Sequences A307071 and A in "The On-Line Encyclopedia of Integer Sequences."
الجزء والصفحة:
...
3-4-2022
2275
Singlecross Graph
There appears to be no term in standard use for a graph with graph crossing number 1. Furthermore, the terms "almost planar" and "1-planar" are used in the literature for other concepts. Therefore, in this work, the term "singlecross graph" is used to mean a graph with graph crossing number 1.
Möbius ladders are singlecross by construction.
Checking if a graph is singlecross is straightforward using the following algorithm (M. Haythorpe, pers. comm., Apr. 16, 2019). First, confirm that the graph is nonplanar. Then, for all non-adjacent pairs of edges 
and 
, delete the two edges and create a new vertex 
. Finally, check if any one of the four new graphs obtained from adding any one of the edges 
, 
, 
, and 
is planar. If so, then the original graph is singlecross.
The numbers of singlecross simple graphs on 
nodes are 0, 0, 0, 0, 1, 12, 162, 3183, 74696, 1892122, ... (A307071), and the numbers of connected graphs are 0, 0, 0, 0, 1, 11, 149, 3008, 71335, 1814021, ... (A307072).
REFERENCES
Sloane, N. J. A. Sequences A307071 and A in "The On-Line Encyclopedia of Integer Sequences."
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
