Gear Graph
المؤلف:
Brandstädt, A.; Le, V. B.; and Spinrad, J. P.
المصدر:
Graph Classes: A Survey. Philadelphia, PA: SIAM
الجزء والصفحة:
...
20-3-2022
2125
Gear Graph
The gear graph, also sometimes known as a bipartite wheel graph (Brandstädt et al. 1987), is a wheel graph with a graph vertex added between each pair of adjacent graph vertices of the outer cycle (Gallian 2018). The gear graph 
has 
nodes and 
edges.
The gear graphs 
are a special case 
of the Jahangir graph.
Gear graphs are unit-distance and matchstick graphs, as illustrated in the embeddings shown above.
Attractive derived unit-distance graph are produced by taking the vertex sets from the matchstick embeddings and connecting all pairs of vertices separate by a unit distance for 
, 6, 12, and 18, illustrated above, with the 
case corresponding to the wheel graph 
.
Ma and Feng (1984) proved that all gear graphs are graceful, and Liu (1996) showed that if two or more vertices are inserted between every pair of vertices of the outer cycle of the wheel, the resulting graph is also graceful (Gallian 2018).
Precomputed properties of gear graphs are given in the Wolfram Language by GraphData[![<span style=]()
{" src="https://mathworld.wolfram.com/images/equations/GearGraph/Inline9.svg" style="height:22px; width:6px" />"Gear", n![<span style=]()
}" src="https://mathworld.wolfram.com/images/equations/GearGraph/Inline10.svg" style="height:22px; width:6px" />].
The gear graph has chromatic polynomial, independence polynomial, matching polynomial, rank polynomial, and reliability polynomial given by
where 
. These have recurrence equations
REFERENCES
Brandstädt, A.; Le, V. B.; and Spinrad, J. P. Graph Classes: A Survey. Philadelphia, PA: SIAM, p. 19, 1987.
Gallian, J. "Dynamic Survey of Graph Labeling." Elec. J. Combin. DS6. Dec. 21, 2018.
https://www.combinatorics.org/ojs/index.php/eljc/article/view/DS6.Ma, K. J. and Feng, C. J. "On the Gracefulness of Gear Graphs." Math. Practice Theory, No. 4, 72-73, 1984.
Liu, Y. "The Gracefulness of the Star Graph with Top Sides." J. Sichuan Normal Univ. 18, 52-60, 1995.
Liu, Y. "Crowns Graphs 
Are Harmonious Graphs." Hunan Annals Math. 16, 125-128, 1996.
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
