TOPICS
Search

Gear Graph


GearGraphs

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 G_n has 2n+1 nodes and 3n edges.

The gear graphs G_n are a special case J_(2,n) of the Jahangir graph.

GearGraphsUnitDistance

Gear graphs are unit-distance and matchstick graphs, as illustrated in the embeddings shown above.

GearGraphDerivedUnitDistanceGraphs

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 n=3, 6, 12, and 18, illustrated above, with the n=3 case corresponding to the wheel graph W_7.

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).

For n>=4, the simplex graph of the cycle graph C_n is the gear graph G_n.

Precomputed properties of gear graphs are given in the Wolfram Language by GraphData[{"Gear", n}].

The gear graph has chromatic polynomial, independence polynomial, matching polynomial, rank polynomial, and reliability polynomial given by

pi_n(z)=z[z-2+(3-3z+z^2)^n]
(1)
I_n(x)=x(x+1)^n+((1-t+2x)^n+(1+t+2x)^n)/(2^n)
(2)
mu_n(x)=((n+tx)(-2-tx+x^2)^n+(-n+tx)(-2+tx+x^2)^n)/(2^nt)
(3)
R_n(x,y)=1/x(x[x^2(y+4)+3x+1-s]^n+x[x^2(y+4)+3x+1+s]^n-2^(n+1)x^(2n+1)+2^nyx^(2n))
(4)
C(p)=((p-1)^(2n)[(-t+3p+1)^n+(t+3p+1)^n-2^(n+1)p^n])/(2^n),
(5)

where t=sqrt(x^2-4). These have recurrence equations

pi_n(z)=(z^2-3z+4)pi_(n-1)(z)-(z^2-3z+3)pi_(n-2)(z)
(6)
I_n(x)=(3x+2)I_(n-1)(x)-(3x^2+3x+1)I_(n-2)(x)+(x+1)x^2I_(n-3)(x)
(7)
mu_n(x)=2(x^2-2)mu_(n-1)(x)-(x^4-4x^2+6)mu_(n-2)(x)+2(x^2-2)mu_(n-3)(x)-mu_(n-4)(x)
(8)
R_n(x,y)=(1+3x+5x^2+x^2y)R_(n-1)(x,y)-x^2(2+5x+5x^2+y+2xy+2x^2y)R_(n-2)(x,y)+(x^4(1+x)^2(1+y))R_(n-3)(x,y)
(9)
C(p)=(4p+1)(p-1)^2C_(n-1)(p)-p(3p+2)(p-1)^4C_(n-2)(p)+p^2(p-1)^6C_(n-3)(p).
(10)

See also

Crossed Prism Graph, Cycle Graph, Helm Graph, Jahangir Graph, Ladder Graph, Prism Graph, Web Graph, Wheel Graph

Explore with Wolfram|Alpha

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 Q_2(n) Are Harmonious Graphs." Hunan Annals Math. 16, 125-128, 1996.

Referenced on Wolfram|Alpha

Gear Graph

Cite this as:

Weisstein, Eric W. "Gear Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/GearGraph.html

Subject classifications