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.

اخر الاخبار

اخبار العتبة العباسية المقدسة

المجمَع العلمي يقيم مسابقة الكوثر الخاصة بترتيل القرآن الكريم في كربلاء

قسم الشؤون الفكرية والثقافية يُصدر العدد الثالث والعشرين من مجلّة (أوراق معرفية)

قسم التربية والتعليم يُطلق الموسم التدريبيّ الصيفيّ لملاكات مجموعة العميد التربوية

المجمَع العلمي يُطلق المرحلة الثالثة من مشروع أمير القرّاء الوطني

المزيد

الآخبار الصحية

اختراق علمي.. دواء يؤخر ظهور السكري من النوع الأول لسنوات

هذا ما يحدث لجسمك إن أهملت نظافة فراشك

لماذا تعتبر النساء أكثر عرضة للإصابة بألزهايمر من الرجال؟

لماذا يحذر الخبراء من الإفراط في تناول الفراولة؟

المزيد

الآخبار التكنلوجية

السيارات الكهربائية أنظف بنسبة 73% من سيارات الوقود

سيارة لوسِد الكهربائية تدخل "غينيس" بأطول مدى في العالم

نظرية جديدة تنسف كل ما نعرفه عن تشكل أول قارة في الأرض

منذ 37 ألف عام.. دراسة تكشف "أقدم أمراض" أصابت البشر

المزيد

مواضيع ذات صلة

Minimum Spanning Tree

Maximum Leaf Number

Lobster Graph

Labeled Tree

Internal Path Length

Red-Black Tree

Pseudotree

Pseudoforest

Prüfer Code

Planted Tree

Planted Planar Tree

Graph Strength