The nine-vertex Paley graph is locally linear. One of its six triangles is highlighted in green.
In graph theory, a locally linear graph is an undirected graph in which every edge belongs to exactly one triangle. Equivalently, for each vertex of the graph, its neighbors are each adjacent to exactly one other neighbor, so the neighbors can be paired up into an induced matching.[1] Locally linear graphs have also been called locally matched graphs.[2] Their triangles form the hyperedges of triangle-free 3-uniform linear hypergraphs and the blocks of certain partial Steiner triple systems, and the locally linear graphs are exactly the Gaifman graphs of these hypergraphs or partial Steiner systems.
Many constructions for locally linear graphs are known. Examples of locally linear graphs include the triangular cactus graphs, the line graphs of 3-regular triangle-free graphs, and the Cartesian products of smaller locally linear graphs. Certain Kneser graphs, and certain strongly regular graphs, are also locally linear.
The question of how many edges locally linear graphs can have is one of the formulations of the Ruzsa–Szemerédi problem. Although dense graphs can have a number of edges proportional to the square of the number of vertices, locally linear graphs have a smaller number of edges, falling short of the square by at least a small non-constant factor. The densest planar graphs that can be locally linear are also known. The least dense locally linear graphs are the triangular cactus graphs.
^Cite error: The named reference f was invoked but never defined (see the help page).
^Cite error: The named reference lpv was invoked but never defined (see the help page).
and 20 Related for: Locally linear graph information
In graph theory, a locallylineargraph is an undirected graph in which every edge belongs to exactly one triangle. Equivalently, for each vertex of the...
regular graph is a distance-regular graph with diameter 2 whenever μ is non-zero. It is a locallylineargraph whenever λ = 1. A strongly regular graph is...
local linearity of manifolds and create a mapping that preserves local neighbourhoods at every point of the underlying manifold. Locally-linear Embedding...
piecewise linear or segmented function is a real-valued function of a real variable, whose graph is composed of straight-line segments. A piecewise linear function...
In graph theory, the Games graph is the largest known locallylinear strongly regular graph. Its parameters as a strongly regular graph are (729,112,1...
Y} are Hausdorff locally convex spaces with Y {\displaystyle Y} finite-dimensional then this list may be extended to include: the graph of F {\displaystyle...
in random graphs. The Paley graph of order 9 is a locallylineargraph, a rook's graph, and the graph of the 3-3 duoprism. The Paley graph of order 13...
as being cactus graphs the triangular cacti are also block graphs and locallylineargraphs. Triangular cactuses have the property that they remain connected...
topology). Any continuous function into a Hausdorff space has a closed graph. Any linear map, L : X → Y , {\displaystyle L:X\to Y,} between two topological...
domain. A differentiable function is smooth (the function is locally well approximated as a linear function at each interior point) and does not contain any...
graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject...
his axioms to prove the Garnir–Wright closed graph theorem which states, among other things, that any linear map from an F-space to a TVS is continuous...
are Souslin spaces. The Borel graph theorem states: Let X {\displaystyle X} and Y {\displaystyle Y} be Hausdorff locally convex spaces and let u : X →...
coloring tries to assign the same color in the graph-coloring to live range that are copy related. Linear scan is another global register allocation approach...
cubic symmetric graphs included this graph. The bipartite half of the Foster graph is a distance-regular graph and a locallylineargraph. It is one of...
lengths in cubic graphs The Erdős–Hajnal conjecture on large cliques or independent sets in graphs with a forbidden induced subgraph The linear arboricity conjecture...
In the mathematical field of graph theory, a graph homomorphism is a mapping between two graphs that respects their structure. More concretely, it is a...
nonlinear techniques include manifold learning techniques such as Isomap, locallylinear embedding (LLE), Hessian LLE, Laplacian eigenmaps, and methods based...
Global Information