Fact-checked by Grok 2 weeks ago

Lattice graph

In graph theory, a lattice graph, also known as a mesh graph or grid graph, is a graph whose vertices correspond to the points of a regular lattice in Euclidean space \mathbb{R}^n and whose edges connect lattice points that are nearest neighbors according to the lattice's geometry, forming a regular tiling of the space.^[1] These graphs generalize grid structures to any dimension, with the embedding ensuring that the graph's structure mirrors the periodic, symmetric arrangement of the lattice points.^[1] The most studied lattice graphs are the two-dimensional square grid graphs, defined as the Cartesian product P_m \square P_n of two path graphs with m and n vertices, respectively, resulting in mn vertices and $2mn - m - n edges.^[2] Square grid graphs are bipartite, admitting a 2-coloring where adjacent vertices receive different colors (e.g., a chessboard pattern), and thus have chromatic number 2 (except for the trivial 1×1 case).^[2] They are Hamiltonian if at least one dimension is even, meaning they contain a cycle visiting each vertex exactly once, and exhibit graceful labelings under certain conditions.^[2] Higher-dimensional lattice graphs, such as the three-dimensional cubic lattice, extend these properties while maintaining regularity and bipartiteness.^[2] Lattice graphs serve as foundational models in various fields, including percolation theory, where they model the connectivity of random subgraphs to study phase transitions in disordered systems like fluid flow through porous media.^[3] They also appear in statistical mechanics for analyzing phenomena such as the Ising model on grids and in computer science for algorithms on multidimensional data structures, such as pathfinding in meshes or quantum circuit simulations.^[4]

Definition and Fundamentals

Formal Definition

A lattice graph is a graph whose vertices correspond to points in a regular tiling of Euclidean space \mathbb{R}^n, with edges connecting nearest neighbors according to the tiling's structure.^[1] In the standard d-dimensional integer lattice graph, the vertex set is \mathbb{Z}^d, the set of all points with integer coordinates, and two vertices u, v \in \mathbb{Z}^d are adjacent if they differ by exactly 1 in precisely one coordinate (i.e., \|u - v\|_1 = 1), forming edges of unit length in the \ell_1 (Manhattan) metric. This construction embeds the graph as a regular grid tiling, where each vertex has degree $2d. The translation group \mathbb{Z}^d acts on the lattice graph by shifting vertices via integer vectors, preserving the edge structure and acting transitively on the vertices, meaning any vertex can be mapped to any other via such a translation; the full automorphism group also includes reflections and rotations consistent with the tiling's symmetries. In the simplest case is the 1-dimensional lattice graph, where vertices are the integers \mathbb{Z} and edges connect consecutive integers i and i+1 (or i-1), forming the infinite path graph.^[5]

Finite and Infinite Variants

Infinite lattice graphs are unbounded structures isomorphic to the integer lattice \mathbb{Z}^d, consisting of vertices at all points with integer coordinates in d-dimensional Euclidean space and edges connecting pairs of vertices that are nearest neighbors, specifically those at Euclidean distance 1.^[6] In the two-dimensional case, the square lattice L_2 (or \mathbb{Z}^2) has vertices at all points (m, n) where m, n \in \mathbb{Z}, with edges between points differing by exactly one unit horizontally or vertically.^[7] Every vertex in such infinite lattices has regular degree $2d, reflecting the uniform nearest-neighbor connectivity without boundaries.^[6] Finite variants arise as induced subgraphs restricted to bounded regions of these infinite lattices, such as the m \times n grid graph G_{m,n}, whose vertices form an m-by-n array and edges connect adjacent vertices horizontally and vertically within the bounds.^[8] These can incorporate open boundaries, where the perimeter lacks connections beyond the region, or other configurations like cylindrical wraps in one dimension. In finite lattice graphs with open boundaries, boundary effects manifest as degree deficiencies compared to the infinite case: interior vertices retain full degree (4 in 2D square lattices), but non-corner edge vertices have reduced degree 3 due to one missing neighbor, and the four corner vertices have degree 2 from two missing neighbors.^[8] These irregularities influence properties like connectivity and eigenvalue spectra, deviating from the translation-invariant behavior of infinite lattices.^[9] To better approximate the uniformity of infinite lattices while remaining computationally tractable, periodic boundary conditions are applied by identifying opposite edges of the bounded region, yielding toroidal graphs where the structure wraps around like a torus, ensuring all vertices achieve the full degree $2d.^[9] Such constructions derive from the periodic nature of the underlying infinite lattice, partitioning vertices into equivalence classes modulo the period vectors.^[9] The square lattice provides a prototypical example, where finite m \times n toroidal grids eliminate boundary deficiencies.^[9]

Main Types of Lattice Graphs

Square Lattice Graph

The square lattice graph, also known as the grid graph, is a fundamental structure in graph theory constructed as the Cartesian product of two path graphs, P_m \square P_n, where P_m and P_n are paths on m and n vertices, respectively.^[10] This yields a finite m \times n grid with vertex set \{(i,j) \mid 1 \leq i \leq m, 1 \leq j \leq n\}, where edges connect vertices that differ by exactly one in either the i- or j-coordinate (horizontal or vertical adjacency) but not both.^[10] Interior vertices in this graph have degree 4, while boundary vertices have lower degrees depending on their position.^[7] The infinite square lattice graph extends this construction to the integer lattice \mathbb{Z}^2, with vertices at all integer coordinate pairs (i,j) \in \mathbb{Z} \times \mathbb{Z} and edges between (i,j) and (i',j') if |i - i'| + |j - j'| = 1.^[7] Every vertex in this graph is 4-regular, reflecting the uniform four-directional connectivity in the plane.^[7] The square lattice is bipartite, as its vertices can be partitioned into two sets via a checkerboard coloring where adjacent vertices receive opposite colors.^[11] Special cases of the finite square lattice include the $1 \times n grid, which is isomorphic to the path graph P_n with n vertices and n-1 edges. The $2 \times n grid corresponds to the ladder graph L_n, consisting of two parallel paths of length n connected by n rungs, resulting in $2n vertices and $3n-2 edges.^[12]

Triangular Lattice Graph

The triangular lattice graph is an infinite regular graph embedded in the Euclidean plane, arising from the tiling of the plane by equilateral triangles. Its vertex set consists of all points generated by integer linear combinations of the basis vectors \vec{a_1} = (1, 0) and \vec{a_2} = \left( \frac{1}{2}, \frac{\sqrt{3}}{2} \right), with edges connecting pairs of vertices at Euclidean distance 1, corresponding to the six nearest neighbors for each vertex.^[13] This structure ensures that every vertex has exactly six adjacent vertices, making the graph 6-regular.^[14] As the primal graph of the triangular tiling, the triangular lattice graph is dual to the hexagonal lattice graph, where the vertices of the hexagonal graph correspond to the triangular faces, and edges reflect adjacency between faces.^[15] The coordination number of 6 reflects the local geometry, with each site surrounded by six equivalent neighbors at 60-degree intervals. The graph is naturally embedded within the triangular lattice group, the abelian group \mathbb{Z} \vec{a_1} + \mathbb{Z} \vec{a_2} under vector addition, which captures the translational symmetries of the structure. Finite versions of the triangular lattice graph are constructed by restricting to bounded portions of the infinite tiling, such as an n \times n grid of sites, preserving as much of the local 6-coordination as possible along the boundaries. These finite approximations are commonly employed in modeling hexagonal packing configurations, where the vertices represent the centers of packed disks or particles in a dense arrangement.^[16]

Hexagonal Lattice Graph

The hexagonal lattice graph is a three-regular infinite graph embedded in the Euclidean plane, commonly referred to as the honeycomb lattice. It corresponds to the 1-skeleton of the regular hexagonal tiling of the plane, in which three hexagons meet at each vertex, resulting in hexagonal faces bounded by six edges each.^[14] This structure forms a bipartite graph, with vertices partitioned into two equal-sized sublattices connected exclusively between the parts.^[17] The vertex set consists of points derived from the hexagonal tiling, where each vertex connects to exactly three neighbors separated by angles of 120 degrees. These positions can be embedded using basis vectors \mathbf{v_1} = (1,0) and \mathbf{v_2} = \left(\frac{1}{2}, \frac{\sqrt{3}}{2}\right), with every other point selected from the generated lattice to yield the characteristic honeycomb arrangement of two interpenetrating triangular sublattices.^[18] Finite variants of the hexagonal lattice graph are obtained as induced subgraphs of finite hexagonal grids, often with periodic boundary conditions to approximate the infinite case. These finite models are widely used in simulations of two-dimensional materials, such as graphene, where the lattice captures the atomic connectivity essential for electronic and mechanical properties.^[19] The hexagonal lattice graph is the dual of the triangular lattice graph, sharing the same embedding but with reversed primal-dual roles.^[20]

Key Properties

Combinatorial and Structural Properties

Lattice graphs exhibit several key combinatorial properties that distinguish them from general graphs. The square and hexagonal lattice graphs are bipartite, as all cycles in these structures have even length, allowing the vertices to be partitioned into two independent sets with no edges within each set.^[21] In contrast, the triangular lattice graph is not bipartite due to the presence of odd-length cycles, specifically triangles formed by three mutually adjacent vertices.^[22] Square lattice graphs possess the median graph property: for any three vertices a, b, and c, there exists a unique median vertex m(a, b, c) that lies on some shortest path between each pair among a, b, and c.^[23] This property arises because the square lattice is the Cartesian product of two path graphs, and the Cartesian product of median graphs is itself median.^[24] The unique median ensures a structured interval convexity in the graph, where the set of vertices on shortest paths between any two points forms a convex substructure. A fundamental structural result is the grid minor theorem, which states that every planar graph is a minor of a sufficiently large square lattice graph.^[25] This theorem highlights the expressive power of square lattices in embedding planar structures through contractions and deletions. Regarding Hamiltonicity, finite square grid graphs of dimensions m \times n with m, n \geq 2 admit Hamiltonian paths that visit every vertex exactly once.^[26] Infinite square lattice graphs also possess Hamiltonian paths, such as doubly infinite paths that traverse all vertices without repetition, extending the finite case indefinitely.^[7] Infinite lattice graphs are 4-regular, ensuring high connectivity that supports such paths.

Geometric and Spectral Properties

Lattice graphs, especially the square variant, admit a natural embedding in the Euclidean plane \mathbb{R}^2, where vertices are positioned at integer coordinates (x, y) \in \mathbb{Z}^2 and edges connect nearest neighbors horizontally or vertically, ensuring unit edge lengths and preserving the graph's 4-regular structure for interior vertices.^[1] This embedding maintains the geometric regularity of the lattice, allowing distances in the graph to correspond directly to path lengths along the grid lines. In particular, for the square lattice, the graph distance between two vertices (x_1, y_1) and (x_2, y_2) is given by the Manhattan (L1) distance d((x_1, y_1), (x_2, y_2)) = |x_1 - x_2| + |y_1 - y_2|, which quantifies the minimal number of edge traversals required.^[27] The spectral properties of lattice graphs are derived from the eigenvalues of their adjacency matrices, which reveal structural symmetries and connectivity characteristics. For finite approximations of the infinite square lattice, such as toroidal grids with periodic boundary conditions of dimensions m \times n, the eigenvalues are $2\left(\cos\left(\frac{2\pi k}{m}\right) + \cos\left(\frac{2\pi l}{n}\right)\right) for integers k = 0, \dots, m-1 and l = 0, \dots, n-1.^[28] In the infinite square lattice, the spectrum of the adjacency operator forms the continuous interval [-4, 4], reflecting the bounded degree and translational invariance. Due to the bipartite nature of the square lattice, the spectrum exhibits symmetry around zero, with eigenvalues appearing in \pm \lambda pairs.^[29] Lattice graphs also satisfy specific isoperimetric inequalities that relate the size of a subset's boundary to its volume, providing bounds on expansion. For a finite subset S of vertices in the infinite square lattice, the edge boundary |\partial S| satisfies |\partial S| \geq c \sqrt{|S|} for some constant c > 0, with equality approached by discrete balls in the Manhattan metric; this highlights the suboptimal expansion of lattices compared to expanders, where the constant is independent of |S|. These inequalities underpin the analysis of diffusion and mixing times on lattices, emphasizing their geometric constraints.^[30]

Generalizations and Extensions

Higher-Dimensional Lattice Graphs

Lattice graphs extend naturally to higher dimensions, generalizing the structure of the two-dimensional square lattice. The d-dimensional integer lattice graph has the vertex set \mathbb{Z}^d, the set of all d-tuples of integers, with an edge connecting two vertices if they differ by exactly 1 in precisely one coordinate and are equal in the others.^[31] This construction connects each vertex to its 2d nearest neighbors along the positive and negative directions of the d coordinate axes, yielding a regular graph of degree 2d, known as the coordination number.^[31] A prominent finite example in this framework is the hypercube graph Q_d, which serves as the 1-skeleton of the d-dimensional cube (or hypercube). The vertices of Q_d correspond to the points in \{0,1\}^d \subset \mathbb{Z}^d, with edges between those differing by 1 in exactly one position, mirroring the lattice's adjacency rule within this bounded subset.^[32] This graph captures the combinatorial essence of the d-dimensional lattice in a compact form, with $2^d vertices and d \cdot 2^{d-1} edges. Finite d-dimensional grid graphs provide another key variant, defined as the Cartesian product of d path graphs P_{n_1} \times P_{n_2} \times \cdots \times P_{n_d}, where each P_{n_i} is the path on n_i vertices.^[33] The resulting graph has \prod_{i=1}^d n_i vertices arranged in a hyper-rectangular array, with edges following the lattice adjacency in each dimension, adjusted for the finite boundaries where degrees may drop below 2d near the edges. These structures underpin multidimensional data organization in computing, such as in array-based algorithms for spatial indexing and nearest-neighbor searches in high-dimensional datasets.^[34]

Non-Standard Lattice Graphs

Non-standard lattice graphs encompass variants of the traditional regular lattice structures that incorporate irregularities in connectivity, point sets, or neighborhood definitions, often arising in specific combinatorial or geometric contexts. These graphs deviate from uniform tilings by adapting the lattice framework to non-regular configurations or alternative movement rules, providing models for problems in optimization and approximation. The Hanan grid is a lattice graph induced by a finite set of points in the Euclidean plane, formed by drawing all horizontal and vertical lines through each point and connecting their intersection points with edges along these lines.^[35] This construction ensures that the vertices lie at the grid intersections, creating a finite rectilinear grid that contains the original points as a subset. Introduced in the context of rectilinear Steiner trees, the Hanan grid serves as a superset of potential optimal solutions for interconnecting the points with minimal total edge length.^[35] The rook's graph represents a variant of the square lattice where vertices correspond to points on an infinite grid, and edges connect any two points that share the same row or column, effectively forming complete bipartite subgraphs along each horizontal and vertical line.^[36] This connectivity models the unrestricted movement of a rook in chess across rows and columns, resulting in a graph with infinite degree at each vertex. As a superset of the standard square lattice edges, it extends nearest-neighbor connections to all collinear points.^[36] In contrast, the king grid graph modifies the square lattice by including edges to all eight surrounding neighbors (the Moore neighborhood) for each vertex, capturing the possible moves of a king in chess on an infinite chessboard.^[37] This 8-regular structure incorporates both orthogonal and diagonal adjacencies, broadening the local connectivity beyond the 4-regular square lattice. The graph maintains translational symmetry but introduces richer short-range interactions suitable for modeling multi-directional proximities.^[37] The Bethe lattice provides an acyclic approximation to regular lattices, constructed as an infinite tree where each vertex has a fixed coordination number z \geq 2, mimicking the local neighborhood structure of a lattice without introducing cycles. Originating from statistical mechanics, this graph exactly solves models like the Ising model due to its tree-like topology, offering a mean-field-like approximation for phase transitions on periodic lattices by neglecting long-range loop effects. For instance, a Bethe lattice with z=4 approximates the coordination of the square lattice locally while ensuring computational tractability.^[38]

Applications

In Graph Theory and Algorithms

Lattice graphs, particularly grid graphs, play a pivotal role in the study of graph minors and parameterized complexity. The excluded grid theorem, originally established by Robertson and Seymour in their Graph Minors series, asserts that every graph excluding a fixed-size grid as a minor has bounded treewidth, providing a structural characterization that bounds the complexity of minor-closed graph classes.^[39] This theorem is instrumental in parameterized algorithms, as it enables fixed-parameter tractable (FPT) solutions for problems on graphs with excluded minors; for instance, algorithms for problems like dominating set can run in time exponential only in the treewidth parameter, which is controlled by the grid exclusion size.^[39] Square lattice graphs serve as canonical examples in this context, where the absence of large grid minors implies algorithmic tractability for NP-hard problems when parameterized appropriately. Bidimensionality theory extends these insights, offering a framework for designing efficient parameterized algorithms on planar and minor-closed graphs, including lattices. Introduced by Demaine et al., bidimensionality identifies problems where the solution size scales quadratically with a parameter, such as vertex cover on grid graphs, rendering them FPT with running times like $2^{O(\sqrt{k})} n^{O(1)} for parameter k.^[40] In lattice graphs, this theory leverages the grid structure to kernelize problems to subexponential size, ensuring that vertex cover and similar covering problems admit subexponential FPT algorithms without relying on full treewidth computations. For example, on an n \times n grid, bidimensionality guarantees that optimal solutions for bidimensional parameters are confined to subgrids of size O(k), facilitating dynamic programming approaches.^[40] Shortest path algorithms frequently employ lattice graphs as models for discrete environments, such as mazes or navigation grids. The A* algorithm, with its heuristic-guided search using admissible estimates like Manhattan distance on rectilinear grids, efficiently computes optimal paths in grid graphs by prioritizing promising nodes, achieving optimality in unweighted or weighted settings common to lattice structures. For unweighted cases, breadth-first search (BFS) provides the exact shortest path in maze-solving problems modeled as grid graphs, exploring level by level to guarantee minimality in O(|V| + |E|) time, where |V| and |E| scale linearly with grid dimensions.^[41] These methods are foundational for applications requiring path optimization on lattices, balancing exploration and exploitation in discrete spaces. In VLSI design, lattice graphs underpin routing problems, notably through Hanan grids for rectilinear Steiner trees. The Hanan grid, formed by horizontal and vertical lines through terminal points, contains all optimal rectilinear Steiner minimum trees (RSMTs), reducing the problem to finding minimum spanning trees on this grid subgraph.^[42] Introduced by Hanan, this approach minimizes wirelength in chip layouts by allowing Steiner points only at grid intersections, enabling exact algorithms like dynamic programming for small terminal sets and approximations for larger VLSI instances.^[42] For n terminals, the Hanan grid has O(n^2) points, making it feasible for Steiner tree construction in rectilinear distance metrics prevalent in integrated circuit design.^[43]

In Physics and Materials Science

Lattice graphs provide a natural framework for modeling the periodic atomic arrangements in crystal structures, capturing the connectivity and symmetry of materials. In two-dimensional systems, the hexagonal lattice graph underlies the honeycomb arrangement of carbon atoms in graphene, a prototypical 2D material with exceptional electrical conductivity arising from its Dirac-like band structure. Similarly, triangular lattice graphs describe close-packed layers in certain 2D crystals and interfaces, such as those in hexagonal boron nitride or transition metal dichalcogenides, where the threefold coordination influences phonon modes and mechanical properties.^[44] These 2D lattices extend to three-dimensional generalizations, including the face-centered cubic (FCC) and body-centered cubic (BCC) structures, which model metallic crystals like copper and iron, respectively; the FCC lattice graph features 12 nearest neighbors per vertex, promoting high packing density and ductility, while the BCC variant has 8, contributing to greater strength but lower density.^[45] The Ising model, formulated on lattice graphs, serves as a foundational tool in statistical mechanics to investigate magnetic phase transitions in materials. In this model, spins located at graph vertices interact ferromagnetically with nearest neighbors, mimicking atomic magnetic moments in crystals; the system's behavior exhibits a spontaneous magnetization below a critical temperature, marking the onset of long-range order. On the square lattice graph, Lars Onsager derived the exact partition function and critical point in 1944, revealing a second-order phase transition at finite temperature.^[46] Phase transition properties vary with lattice dimension and type: no transition occurs in one dimension due to thermal fluctuations disrupting order, while two- and three-dimensional lattices, such as square or cubic, support transitions whose critical temperatures depend on coordination number and anisotropy. Percolation theory employs lattice graphs to study connectivity and transport in heterogeneous materials, such as porous media or composites. Site percolation thresholds—the minimum occupation fraction for spanning clusters—differ markedly between lattice types: on the square lattice, it is approximately 0.5927, reflecting balanced duality, whereas on the triangular lattice, self-duality yields an exact value of 0.5, enabling infinite clusters at half occupancy.^[47]^[48] Bond percolation, modeling edge occupations like cracks or conduits, shows analogous lattice-dependent thresholds, informing fracture mechanics and fluid flow in crystalline networks. Diffusion processes on lattice graphs are analyzed through random walks, which simulate particle transport in solids. In low dimensions, such as one- or two-dimensional lattices, simple symmetric random walks are recurrent, returning to the origin with probability 1, as established by Pólya's theorem; this recurrence implies slower effective spreading and anomalous persistence compared to three or higher dimensions, where walks are transient and diffusion normalizes.^[49] Higher-dimensional lattice graphs also appear in quantum field theory, discretizing spacetime for non-perturbative computations in models like lattice quantum chromodynamics.^[50]

References

[1]
Lattice Graph -- from Wolfram MathWorld
A lattice graph, also known as a mesh graph or grid graph, is a graph possessing an embedding in a Euclidean space R^n that forms a regular tiling.
[2]
Grid Graph -- from Wolfram MathWorld
... lattice graph that is the graph Cartesian product P_m square P_n of path ... Graph Theory. Reading, MA: Addison-Wesley, p. 194, 1994. Harary, F ...
[3]
Percolation Theory -- from Wolfram MathWorld
Percolation theory deals with fluid flow (or any other similar process) in random media. If the medium is a set of regular lattice points, then there are two ...
[4]
[2402.08752] Edge coloring lattice graphs - arXiv
Feb 13, 2024 · This paper develops a theory for edge coloring infinite lattice graphs, finding minimal colorings, and relates it to quantum circuits.<|control11|><|separator|>
[5]
Vertex-Transitive Graph -- from Wolfram MathWorld
Informally speaking, a graph is vertex-transitive if every vertex has the same local environment, so that no vertex can be distinguished from any other based on ...<|control11|><|separator|>
[6]
Lattice embeddings of trees - ScienceDirect.com
Every vertex in a lattice Z k has k coordinates, two vertices u , v being adjacent if they differ by +1 or −1 in exactly one coordinate. If this is the i -th ...Missing: nearest | Show results with:nearest
[7]
[PDF] Spanning trees in subgraphs of lattices - UCSD Math
We will introduce the zeta function of a graph and derive its relation to the heat kernel and the number of spanning trees of a graph. In the second part of the ...
[8]
[PDF] A mini course on percolation theory
(In site percolation, the sites of the graph are independently declared to be white or black with probability p and one asks for the existence of an infinite.
[9]
[PDF] Chapter 3. Circuits and Cycles - Section 3.3. Infinite Lattice Graphs
Nov 23, 2022 · In Graph Theory 1 (MATH 5340), infinite graph L2 is called the “square lattice”; see my online note for Graph Theory 1 on Section 1.6.
[10]
[PDF] arXiv:1712.00150v1 [math.CO] 1 Dec 2017
Dec 1, 2017 · The cardinality of a smallest dominating set is called the domination number of G and is denoted δ(G). We let Gm,n denote the finite grid graph ...
[11]
Note Perfect matchings in pruned grid graphs - ScienceDirect.com
A (finite) grid graph G n , m , sometimes called a complete grid graph, has ... Perfect matchings in bipartite graphs are characterized by Hall's Theorem, which ...
[12]
Spectra of toroidal graphs - ScienceDirect
An n -fold periodic locally finite graph in the Euclidean n -space may be considered the parent of an infinite class of n -dimensional toroidal finite graphs.
[13]
[PDF] Optimal Tile-Based DNA Self-Assembly Designs for Lattice Graphs ...
in [1]. 2. Square Lattices. We follow the convention given in [1] that an m × n square lattice graph is the graph Cartesian product Pm × Pn of path graphs on ...
[14]
Agglomerative percolation on bipartite networks: Nonuniversal ...
A square lattice is bipartite (as illustrated by the black and white colors of a checkerboard), but a triangular lattice is not. Following this example, we will ...
[15]
Ladder Graph -- from Wolfram MathWorld
The n-ladder graph, L_n, is defined as P_2 square P_n, where P_n is a path graph, and is equivalent to the 2x n grid graph. It resembles a ladder with two ...Missing: lattice | Show results with:lattice
[16]
[PDF] Solid State Theory Solution 4
Figure 1: Left: Lattice vectors of a triangular lattice. Right: The reciprocal lattice to triangular lattice is a triangular lattice.
[17]
[PDF] Coloring problems in graph theory by Kevin Moss
The triangular lattice T is the 6-regular graph corresponding to a triangular tiling of the plane, and the hexagonal lattice H is the 3-regular graph ...
[18]
[PDF] Exploring the HP Model for Protein Folding - Digital WPI
Apr 24, 2012 · First, the triangular lattice graph and the hexagonal lattice graphs are duals of each other, which means if we take the vertex set to be ...Missing: dual | Show results with:dual
[19]
Force distributions in a triangular lattice of rigid bars | Phys. Rev. E
We study the distribution of bond strengths on an n × n triangular lattice corresponding to the contacts in a hexagonal packing of monodisperse circular grains.
[20]
[PDF] arXiv:1701.07092v2 [math.CO] 27 Jan 2017
Jan 27, 2017 · Let H denote the set of vertices and edges obtained from this tiling (H is often referred to as the hexagonal lattice, see Figure 3, left). Let ...
[21]
[PDF] Tutorial 1 - Graphene
Remember that a honeycomb lattice is actually an hexagonal lattice with a basis of two ions in each unit cell. If a is the distance between nearest ...
[22]
[PDF] arXiv:2008.08231v2 [cond-mat.mes-hall] 20 Aug 2020
Aug 20, 2020 · As schematically shown in Fig. 1(a), the line graph. of the honeycomb lattice is the Kagome lattice. A split graph. S(X) is constructed from a ...
[23]
[PDF] Microstructural Descriptors where I(1)(x)
Thus, the triangular-lattice graph is the dual of the honeycomb-lattice graph. (Observe that the Delaunay tessellation of the honeycomb lattice is not a ...
[24]
A note on S-packing colorings of lattices - ScienceDirect.com
Mar 31, 2014 · The infinite hexagonal lattice, denoted by H , is the 3-regular infinite plane graph where every face is a hexagon. Fiala et al. [6] showed that ...
[25]
Classical dimers on the triangular lattice | Phys. Rev. B
Dec 13, 2002 · We study the classical hard-core dimer model on the triangular lattice. Following Kasteleyn's fundamental theorem on planar graphs, this problem is soluble ...<|separator|>
[26]
[PDF] On median graphs and median grid graphs - UNI-Lj
We also characterize median grid graphs in several different ways, for instance, they are the grid graphs with m − n + 1 squares. To obtain these results we.
[27]
On median graphs and median grid graphs - ScienceDirect
We also characterize median grid graphs in several different ways, for instance, they are the grid graphs with m−n+1 squares. To obtain these results we ...Missing: reference | Show results with:reference
[28]
[PDF] Graph Minors
Thomassen, Highly connected sets and the excluded grid theorem, J. Comb ... Chuzhoy, Polynomial bounds for the grid-minor theorem,. J. ACM 63 (2016), 1 ...
[29]
Hamilton Paths in Grid Graphs | SIAM Journal on Computing
This paper presents sufficient conditions for a grid graph to be Hamiltonian. It is proved that all finite grid graphs of positive width have Hamiltonian line ...
[30]
Kleinberg's grid unchained - ScienceDirect.com
Jul 24, 2020 · A graph instance is built from a square lattice of n × n nodes endowed with the Manhattan distance d: if u and v are two nodes with respective ...
[31]
[PDF] Math 778S Spectral Graph Theory Handout #3: Eigenvalues of ...
The eigenvalues of the adjacency matrix of a graph G are λ1,...,λn. The eigenvalues of the Cartesian product GDH are λi + µj for 1 ≤ i ≤ n and 1 ≤ j ≤ m.Missing: grid | Show results with:grid
[32]
[PDF] Spectra of graphs - CWI
graph Γ ⊗ K2 is bipartite with bipartite halves U1 and U2, say. Fix a ... point and its neighbors from a lattice graph, the result is a smaller lattice graph,.
[33]
[PDF] Discrete Isoperimetric Inequalities - UCSD Math
Our focus here is to derive such extremal graph properties as direct consequences of spectral bounds. The applications include the forcing of long paths and ...
[34]
[PDF] Discrete functional inequalities on lattice graphs - arXiv
Mar 15, 2024 · Definition 4.2. The lattice graph is defined as a graph on Zd, such that two vertices x, y ∈ Zd are connected by an edge if and only if ∥x ...
[35]
Hypercube Graph -- from Wolfram MathWorld
The n-hypercube graph has vertices with 2^k symbols, where two vertices are adjacent if they differ in exactly one coordinate.
[36]
[PDF] arXiv:2010.11023v2 [math.CO] 15 Nov 2021
Nov 15, 2021 · Definition 6. Let the d-dimensional grid graph with side lengths (n1,n2,...,nd) be the Cartesian product of d paths.
[37]
[PDF] Lattice-Based High-Dimensional Gaussian Filtering and the ...
Sep 8, 2012 · The aim of this paper is to rigorously analyze the use of a lattice as the underlying data structure for high dimensional Gaussian filtering, ...
[38]
On Steiner's Problem with Rectilinear Distance
We consider Steiner minimal trees in the plane with rectilinear distance. The rectilinear distance d ⁡ ( p 1 , p 2 ) between two points p 1 , p 2 is | x 1 − x 2 ...
[39]
Rook Graph -- from Wolfram MathWorld
The graph K_m square K_n has mn vertices and mn(m+n)/2-mn edges. It is regular of degree m+n-2, has diameter 3, girth 3 (for max(m,n)>=3), and chromatic
[40]
King Graph -- from Wolfram MathWorld
A king graph has mn vertices, each representing a square on an m x n chessboard, with edges corresponding to legal king moves.
[41]
Bethe Lattice - an overview | ScienceDirect Topics
The Bethe lattice is defined as a graph of infinite points each connected to z neighbors (the coordination number) such that no closed loops exist in the ...Recent Advances In... · Mathematical Statistical... · 2 The Tap Equations
[42]
Excluded Grid Theorem: Improved and Simplified - ACM Digital Library
We study the Excluded Grid Theorem of Robertson and Seymour. This is a fundamental result in graph theory, that states that there is some function f:Z + → Z +
[43]
[cs/0502070] Bidimensionality, Map Graphs, and Grid Minors - arXiv
Feb 16, 2005 · In this paper we extend the theory of bidimensionality to two families of graphs that do not exclude fixed minors: map graphs and power graphs.
[44]
https://www.nature.com/articles/s41467-017-00329-6
[45]
Construction of All Rectilinear Steiner Minimum Trees on the Hanan ...
In this paper, we develop an algorithm to build a database of all RSMTs on the Hanan grid for up to nine pins. The database will be able to help minimize ...Missing: original | Show results with:original
[46]
https://link.aps.org/doi/10.1103/PhysRev.65.117
[47]
Probing the crystallographic orientation of two-dimensional atomic ...
Aug 29, 2017 · Besides hexagonal 2D materials with threefold symmetry, we also explored the correlations between the nanoribbon orientations and the lattice ...
[48]
Deformation pathway and defect generation in crystals - NIH
In this paper, we establish a theoretical foundation to describe the symmetry breaking associated with LID using a combination of group theory and graph theory.
[49]
Crystal Statistics. I. A Two-Dimensional Model with an Order ...
The partition function of a two-dimensional ferromagnetic with scalar spins (Ising model) is computed rigorously for the case of vanishing field.
[50]
[2204.01517] Exact percolation probabilities for a square lattice - arXiv
Mar 31, 2022 · We have found analytical expressions (polynomials) of the percolation probability for site percolation on a square lattice of size L \times L sites.
[51]
Site percolation thresholds on triangular lattice with complex ...
Dec 9, 2020 · In this paper we try to fill this gap by estimating values of the percolation thresholds for several complex neighborhoods on triangular lattice.
[52]
[2311.11326] On Pólya's random walk constants - arXiv
Nov 19, 2023 · A celebrated result in probability theory is that a simple symmetric random walk on the d-dimensional lattice \mathbb{Z}^d is recurrent for d=1,2 and transient ...
[53]
[2302.00467] Review on Quantum Computing for Lattice Field Theory
Feb 1, 2023 · In these proceedings, we review recent advances in applying quantum computing to lattice field theory.