k-Cyclic Graph
المؤلف:
Alon, N.; Yuster, R.; and Zwick, U
المصدر:
"Finding and Counting Given Length Cycles." Algorithmica 17
الجزء والصفحة:
...
1-3-2022
1633
k-Cyclic Graph
Graphs corresponding to closed walks of length 
are known as 
-cyclic graphs, or 
-graphs for short. 
-graphs are connected by definition. The numbers of 
-graphs for 
, 4, ... are 1, 3, 3, 10, 12, 35, 58, 160, 341, 958, 2444, 7242, 21190, 67217, 217335, ... (OEIS A081809; FlowProblems), the first few of which are illustrated above.
It appears that every connected simple graph on more than one node is 
for some value of 
. For example, every connected graph on six or fewer nodes with the exception of the complete graph 
is 
for some 
.
These graphs are important when counting graph cycles. This is because the number of (undirected) closed 
-walks in a graph with adjacency matrix 
is given by 
, where 
denotes the matrix trace, but in order to compute the number 
of 
-cycles, all closed 
-walks that are not cycles must be subtracted.
REFERENCES
Alon, N.; Yuster, R.; and Zwick, U. "Finding and Counting Given Length Cycles." Algorithmica 17, 209-223, 1997.
FlowProblem. "
-Graphs." http://flowproblem.ru/cycles/explicit-formulae/ck-graphs.
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
