A New Algorithm for Computing the Distance and the Diameter in Circulant Graphs
In the present study, we focus on circulant graphs, <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>C</mi><mi>n</mi></msub><mrow><mo>(</mo>&l...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2025-05-01
|
| Series: | Algorithms |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1999-4893/18/5/261 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | In the present study, we focus on circulant graphs, <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mi>C</mi><mi>n</mi></msub><mrow><mo>(</mo><mi>S</mi><mo>)</mo></mrow></mrow></semantics></math></inline-formula>, with set of vertices <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><mo>{</mo><mn>0</mn><mo>,</mo><mn>1</mn><mo>,</mo><mo>…</mo><mo>,</mo><mi>n</mi><mo>−</mo><mn>1</mn><mo>}</mo></mrow></semantics></math></inline-formula> and in which two distinct vertices <i>i</i> and <i>j</i> are adjacent if and only if <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mrow><msub><mrow><mo>|</mo><mi>i</mi><mo>−</mo><mi>j</mi><mo>|</mo></mrow><mi>n</mi></msub><mo>∈</mo><mi>S</mi></mrow></semantics></math></inline-formula>, where <i>S</i> is a generating set. Despite their regularity, there are currently no established formulas to accurately determine the distance and the diameter of circulant graphs. In light of this context, we present in this paper a novel approach, which relies on a simple algorithm, capable of yielding formulas for the distance and the diameter of circulant graphs without implementing any graph. |
|---|---|
| ISSN: | 1999-4893 |