In graph theory, the ladder L n is a planar undirected graph with 2n vertices and n + 2 (n-1) edges [1] .
| Count "Staircase" | |
|---|---|
 | |
| Top | 2n |
| Riber | n + 2 (n-1) |
| Chromatic number | 2 |
| Chromatic Index | 3 for n> 2 2 for n = 2 1 for n = 1 |
| The properties | unit distance graph hamilton planar dicotyledonous |
| Designation | L n |
A staircase can be obtained as a direct product of two paths , one of which has only one edge - L n , 1 = P n × P 1 [2] [3] . If we add two more intersecting edges connecting the four vertices of the ladder with degree two, we get a cubic graph - the Mobius ladder .
By construction, the ladder L n is isomorphic to the lattice G 2, n and looks like a ladder with n beams. The graph is Hamiltonian with girth 4 (if n> 1 ) and chromatic index 3 (if n> 2 ).
The chromatic number of a ladder is 2, and its chromatic polynomial is .
Content
Ring staircase graph
The ring staircase graph CL n is a direct product of a cycle of length n≥3 and an edge [4] . In the symbolic form CL n = C n × P 1 . The graph has 2n vertices and 3n edges. Like stairs, a graph is connected , planar, and Hamiltonian , but a graph is bipartite if and only if n is even.
Gallery
The chromatic number of the stairs is 2.
Notes
- ↑ Weisstein, Eric W. Ladder Graph on the Wolfram MathWorld website.
- ↑ Hosoya, Harary, 1993 , p. 211-218.
- ↑ Noy, Ribó, 2004 , p. 350-363.
- ↑ Chen, Gross, Mansour, 2013 , p. 32-57.
Literature
- H. Hosoya, F. Harary. On the Matching Properties of Three Fence Graphs // J. Math. Chem .. - 1993. - Vol. 12 . - S. 211-218 .
- M. Noy, A. Ribó. Recursively Constructible Families of Graphs // Adv. Appl. Math. - 2004. - Vol. 32 . - S. 350-363 .
- Yichao Chen, Jonathan L. Gross, Toufik Mansour. Total Embedding Distributions of Circular Ladders // Journal of Graph Theory. - 2013 .-- T. 74 , no. 1 . - S. 32–57 . - DOI : 10.1002 / jgt . 21690 .